decimal record contains only the lucky digits 4 and 7

13 лет назад, # ^ |

Хорошо, что меня разбудили.

→ Ответить

Sultan

13 лет назад, # ^ |

Утро добрым не бывает, поэтому я просыпаюсь днём. Но сегодня и день начался неудачно.

→ Ответить

imslavko

13 лет назад, # |

-52

все фиолетовые сейчас открыли емакс статью о дереве отрезков

→ Ответить

13 лет назад, # ^ |

+21

Интересно, это можно расценивать как обсуждение задач во время раунда, или нет?

→ Ответить

imslavko

13 лет назад, # ^ |

-42

хм, за последние 10 минут фиолетовые могут прочитать эту идею и накодить все правильно? Я явно недооцениваю среднестатистического фиолетового

→ Ответить

13 лет назад, # ^ |

+24

Как бы то ни было, обсуждать задачи во время раунда - очень плохо.

→ Ответить

Thomas_Ahle

13 лет назад, # |

Arg, was div2 E Newtons Identities?

It only struck me in the last minute that that might be fast enough, since there are much less than 10^5 lucky numbers less than 10^5..

→ Ответить

ketzer

13 лет назад, # |

Объясните дураку почему число 444477777774747

в задаче D (div2) не ответ на условия 4 7 3 1 ?

→ Ответить

13 лет назад, # ^ |

Нет, тут 2 раза встречается 74. Посмотри внимательно.

→ Ответить

ketzer

13 лет назад, # ^ |

Ах ты ж леший! Точно! вот ступил )))

→ Ответить

Vladimir.Del

13 лет назад, # ^ |

Четверок у тебя 6, а не 4.

→ Ответить

13 лет назад, # ^ |

Да и семерок многовато...

→ Ответить

cmd

13 лет назад, # ^ |

74 два раза встречается

→ Ответить

zhkxdl

13 лет назад, # ^ |

Твое число соответствует условию 6 9 3 2, пересчитай.

→ Ответить

maslowmw

13 лет назад, # ^ |

← Rev. 2 →

(бред)

→ Ответить

ilya.korovin

13 лет назад, # ^ |

← Rev. 2 →

в любом случае много семерок надо ставить в конце.

upd: то есть конечно же, если в конце должно стоять 7.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Два вхождения 74 вместо одного.

UPD: огого, как активно ответили :)

→ Ответить

evgeny11

13 лет назад, # ^ |

для 444477777774747
a1=6
a2=9
a3=3
a4=2
(шесть шестёрок, девять семёрок, 3х47, 2х74)

→ Ответить

13 лет назад, # |

А решение для С див2, когда находим отдельно колличество несовпадений в строках для четверок и семерок, после чего выводим максимум из этих двух значений, корректно? Я так и не придумал контрпример, похоже, его нет.

→ Ответить

EarlOfDitches

13 лет назад, # ^ |

← Rev. 2 →

Я вот тоже не уверен правильно у меня или нет =\
По сути тоже максимум :D

→ Ответить

13 лет назад, # ^ |

Корректно. Это можно объяснить так: давайте заменим сначала все и посчитаем, сколько у нас заменено 4 и сколько - 7. Ясно, что то, что у них минимум, менять не надо, а нужно лишь свопать с другим. В таком случае другого сколько нам нужно заменить? Вот сколько его было минус то что мы уже посвопали. Но это и есть требуемое.

→ Ответить

CHarm

13 лет назад, # ^ |

С халявнее B в много раз)

→ Ответить

Atmo

13 лет назад, # |

Поправьте, если я ошибаюсь, но у очень многих из див 2 сейчас упадёт А из-за лидирующих нулей =(

→ Ответить

InvincibleUZ

13 лет назад, # ^ |

Думаю да, упадет

→ Ответить

ilona

13 лет назад, # ^ |

ну если делать строками, то нет. А большинство решений(у меня в комнате) были строки.

→ Ответить

Schullz

13 лет назад, # ^ |

← Rev. 2 →

Я думаю, немного

Там же длина номера билета n (2 ≤ n ≤ 50) большая - намекает, что строки нужны.

Неужели кто-то длинной арифметикой решал?

→ Ответить

Atmo

13 лет назад, # ^ |

Всё ясно. Я думал, если есть ведущие нули, то их учитывать не надо, и следует проверять счастливость числа без ведущих нулей. Похоже, это не так, да и в таком случае не гарантируется чётность его длины.

→ Ответить

Fox235

13 лет назад, # |

-23

вот что за утро... проснулся думаю, сейчас буду решать задачки )).
сел в 10.50... запускаю VS ... и, ###, лицензия кончилась.... ну думаю: "эх... буду по старинки в Notepad"..
Запустил начал... 1 задачку написал, думаю норм.. а поотм началось... не могу сделать это, не могу сделать то.... в итоге результат плачевный, вместо того чтобы спокойно решать 4-5 задач, я сидел и боролся со всеми вредностями. Обидно, раунд примитивный... на нем только рейт улучшать, а в итоге получу большой минус. :(

→ Ответить

13 лет назад, # ^ |

Не решив всех задач, называть раунд примитивным, ~~да еще и будучи зеленым~~, мягко говоря, странно.

→ Ответить

Fox235

13 лет назад, # ^ |

-23

хм. я понимаю ваше высказывание ). Я не решаю задачи, абы сдать. К тому же я медленно программирую. Задачи я все прочитал, и все решения у меня записаны, надо только их запрогать. Еще вопросик, что такого чтобы быть зеленым?? да, контексты решаю относильено статистики плохо. Но я для себя не ставлю задачу решить все, главное это понять, что и как и оточить азы алгоритмистики.

→ Ответить

13 лет назад, # ^ |

Тогда я с трудом понимаю, зачем решать ACM-подобные контесты вместо прорешки архивов и IOI-подобных контестов.

→ Ответить

Fox235

13 лет назад, # ^ |

все очень просто. Стараюсь еще и скорость развить. С архивом, я неограничен по времени.

→ Ответить

13 лет назад, # ^ |

Как можно развивать скорость не кодируя решения? Взаимоисключающие параграфы детектед.

→ Ответить

ilona

13 лет назад, # ^ |

iama, а Вы сами недалеко от зеленых ушли, чтобы так писать..

→ Ответить

13 лет назад, # ^ |

+21

Я не называл раунд примитивным.

→ Ответить

13 лет назад, # ^ |

>> решать 4-5 задач

А почему ты все еще зеленый тогда?

→ Ответить

nic11

13 лет назад, # ^ |

если бы для тебя раунд был бы примитивным, задачи 1-3 даже в блокнотике сделал бы ;)

→ Ответить

Amir.bh

13 лет назад, # |

Hi there,

Can someone explain me how to calculate C(n,k) MOD P as fast as possible? It is what I didn't know about Problem E.

Thanks a lot.

→ Ответить

13 лет назад, # ^ |

-16

Pascal triangle?

→ Ответить

13 лет назад, # ^ |

+11

as fast as possible:)

→ Ответить

Amir.bh

13 лет назад, # ^ |

We can do it using Pascal triangle.

But the Problem wanted it Modulu a prime number, so there will be a faster solution

→ Ответить

al13n

13 лет назад, # ^ |

← Rev. 2 →

+24

As n!/k!/(n-k)!. Modulo division can be performed with multiplication by inverse (http://en.wikipedia.org/wiki/Modular_multiplicative_inverse). For prime modulo p, the inverse of a can be found using Euler's theorem as a^(p-2). It can be calculated using fast exponentiation in O(log N).

→ Ответить

Amir.bh

13 лет назад, # ^ |

Great man! Thanks a lot! I didn't know about that!

→ Ответить

hacker007

13 лет назад, # ^ |

For this formula: sum([int(k*p/q) for k in range(1,(q+1)/2)]) where p and q are both prime numbers and not equal to 2. How to calculate it fast?

→ Ответить

nic11

13 лет назад, # ^ |

← Rev. 2 →

If you need to calculate your formula many times, you can use particular sums (sorry if it wrong. in russian the popular name for it is частичная сумма) for unchanging var p. Like precalculating. e.g. for array: a = [1,2,3,5,6,12,4]. for each element we calculate s[i]. s[i] = a[0] + a[1] + ... + a[i]. So we can use formula: s[0] = a[0], s[i] = s[i - 1] + a[i] (i > 0) to calculate it. i.e. after calculating, we have s = [1, 3, 6, 11, 17, 29, 33]. So if you want to calculate a[l + 1] + ... + a[r - 1] + a[r], just use s[r] - s[l].

P.S. you can change the line sum([int(k*p/q) for k in range(1,(q+1)/2)]) to sum(k*p//q for k in range(1,(q+1)//2)). I think it will be faster than the first one.

P.P.S. I didn't check it for python2.7, but for python3.2 it should work.

→ Ответить

VArtem

13 лет назад, # ^ |

Choose(n, m) = (n!) / ((k!) * (n-k)!)

We can precalculate k! % mod for all k = 0..n, then

Choose(n, m) = (n! % mod) * ((k! % mod) * ((n-k)! % mod)) ^ (-1) % mod, where a^(-1) % mod is such a number, that a * a^(-1) = 1 % mod. Calculating a^(-1) % mod requires O(log(mod)) time and can be done with Extended Euclidean Algorithm, or using standard function (such as BigInteger.modInverse in Java).

→ Ответить

PattS

13 лет назад, # ^ |

becuase mod is prime( 1000000007 is prime)

so we can use pow(a, 1000000005 ) to find inverse

→ Ответить

doraemon

13 лет назад, # ^ |

use multiplicative inverse

→ Ответить

13 лет назад, # |

+26

Где там Хаустов со своим счетчиком? КФ за этот раунд жирный +

→ Ответить

cmd

13 лет назад, # |

В этом раунде треть всех решений было послано в первые 10 минут? =) Или от чего считается процент в статусе?

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

+13

А почему бы и нет. А - тупость, а все остальное не совсем приятные техники и разборы случаев, которые в большом количестве валились на претестах и взломах.

→ Ответить

LesyaPhoenix

13 лет назад, # |

← Rev. 2 →

Это считается ок если в сатусе посылок задача С до сих пор выполняется на 6-ом претесте, в списке задач горит зеленым, и я ее залочила и смотрела посылки других участников.То что я ее сдала в положение ни для кого не отображается. Это вообще как?

→ Ответить

ant.ermilov

13 лет назад, # |

+283

Some moment during system testing

→ Ответить

mkagenius

13 лет назад, # ^ |

← Rev. 2 →

look @ the "up" vote for your post! :) (its +47 )

{lets make it +74)

→ Ответить

13 лет назад, # ^ |

+11

{lets make it +444)

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

+44

And now this comment has +47:

→ Ответить

primorial

13 лет назад, # ^ |

Print screen at the moment, when I saw the comment (click to see full image).

→ Ответить

PavelKunyavskiy

13 лет назад, # |

А на чем ломали по C?

→ Ответить

imslavko

13 лет назад, # ^ |

меня взломали так: я не учитывал что бывают другие счастливые числа помимо 4 и 7

→ Ответить

dzhulgakov

13 лет назад, # ^ |

Еще многие считали биномиальные коэффициенты в массиве 1000*1000, не предусмотрев что может потребоваться С(100000,х)

→ Ответить

http://mirror.codeforces.com/contest/145/submission/1108057

13 лет назад, # |

-15

Ребят, помогите, подскажите где баг. В упор не вижу.

→ Ответить

VArtem

13 лет назад, # ^ |

Лол, счастливые числа - это не только 4 и 7.

→ Ответить

13 лет назад, # ^ |

-21

екараныбабай. Обидно, был бы в первой сотне.

→ Ответить

dzhulgakov

13 лет назад, # ^ |

Нужно рассматривать счастливые числа (состоящие из цифр 4 и 7), а не только счастливые цифры (т.е. числа 4 и 7).

→ Ответить

Venom

13 лет назад, # |

+35

Полагаю стоит поздравить kuniavski как 3 международного гроссмейстера?)

→ Ответить

gskhirtladze

13 лет назад, # ^ |

+11

А так же и hos.lyric !!!

→ Ответить

13 лет назад, # |

← Rev. 2 →

Балин, пора бы мне уже понять, что если в динамике O(N²) состояний, это далеко не всегда означает, что она работает за O(N²)...

→ Ответить

13 лет назад, # ^ |

Где же вы были, взломщики...

→ Ответить

HAPKOMAH

13 лет назад, # |

Спасибо, что дали побыть первым во время контеста первый раз в своей жизни:)

→ Ответить

oversolver

13 лет назад, # |

У кого-нибудь в С проходило O(n * 1022)?

→ Ответить

hadi

13 лет назад, # |

+14

I think the time limit for the last Div 1 problem is a bit strict. My O(N log N) solution using C++ cin timed out, and after contest I used scanf and got accepted in about 2 seconds. This is not a long contest, so I think judge should allow 4x time of the optimized solution, which is currently 1 seconds. Some correct solutions timed out because of this.

→ Ответить

R_R_

13 лет назад, # ^ |

+10

Generally, I think time limit should not be too much, because codeforces server is tooooo fast. In a Codeforces contest long ago, there's a problem with N <= 10^5 and I got accepted with O(N^2) algorithm, with buffered reading to read a few MBs.

Maybe if time limit is increased, some tricky brute force solutions would pass system test. And I think cin is super super slow, even if the time limit is tripled, I don't think it would have much chance to pass

→ Ответить

Barricadenick

13 лет назад, # |

Спасибо, что дали впервые побыть в 50 во время тура)))

→ Ответить

13 лет назад, # |

Не могу понять, почему у меня упала E, да еще на таком большом тесте. Решение.

→ Ответить

sankear

13 лет назад, # ^ |

Первое, что увидел:

res += (C(n - total, k - cnt) * p) % base;

а кто res по модулю брать будет?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Блин :) Ну ладно, все равно бы не прошла. Теперь TLE 25.

→ Ответить

Ibragimov_Bauyrzhan

13 лет назад, # |

-25

В задаче D (div 2) на тесте 12 : 4 7 2 1

у меня выводит правильный ответ 44477777747 а ответ жюри 44474777777 тот и другой ответ, они оба правильные но у меня почему то Wrong answer

Test: #12, время: 10 мс., память: 1368 КБ, код возврата: 0, код возврата чекера: 1, вердикт: WRONG_ANSWER

Ввод

4 7 2 1

Вывод

44477777747

Ответ

44474777777

Протокол тестирования

wrong answer expected 44474777777, found 44477777747

→ Ответить

Ibragimov_Bauyrzhan

13 лет назад, # ^ |

Можете найти мою ошибку?

→ Ответить

yarrr

13 лет назад, # ^ |

+13

Спокойнее, ответ же наименьшим должен быть.

→ Ответить

Ibragimov_Bauyrzhan

13 лет назад, # ^ |

аа я не заметил, спасибо))

→ Ответить

13 лет назад, # ^ |

+13

Не могут оба ответа быть правильными - в задаче просят найти наименьшее число.

→ Ответить

evgentu

13 лет назад, # ^ |

Внимательнее читаем условие: "Петю интересует минимальное счастливое число d"

→ Ответить

Atmo

13 лет назад, # ^ |

разве 44477777747 не больше чем 44474777777? "Петю интересует минимальное счастливое число d, ..."

→ Ответить

EarlOfDitches

13 лет назад, # ^ |

Нужно было найти НАИМЕНЬШЕЕ число

→ Ответить

Schullz

13 лет назад, # ^ |

← Rev. 2 →

Петю интересует минимальное счастливое число d, которое удовлетворяет некоторым условиям.

UPD

Пока писал - столько комментов новых появилось)

→ Ответить

San_Sany4

13 лет назад, # ^ |

← Rev. 2 →

Необходимо найти минимальный ответ. Ваш ответ больше, чем ответ жюри.

UPD: На codeforces тебе помогут, сразу и толпой.

→ Ответить

13 лет назад, # |

Раунд просто супер, если бы еще претесты послабее в A-C div2...

→ Ответить

timus1994

13 лет назад, # |

← Rev. 7 →

Классный раунд. Жаль, что D завалилась из-за опечатки

→ Ответить

13 лет назад, # ^ |

Не зная остального твоего решения, сложно понять смысл этого комментария.

→ Ответить

timus1994

13 лет назад, # ^ |

http://mirror.codeforces.com/submissions/Dmitr94
последние две посылки

→ Ответить

_Vadim_

13 лет назад, # ^ |

i <- a7 - a47

Скорее всего вместо <- нужно было <=

→ Ответить

timus1994

13 лет назад, # ^ |

Ну о чём я и говорю)

→ Ответить

Egor

13 лет назад, # |

+77

Писать раунд из поезда, а дописывать стоя рядом с терминалами по приему платежей на вокзале (там розетка свободная оказалась) - было весело. +3 в рейтинге обозначает, что не зря писал :)

→ Ответить

mastersobg

13 лет назад, # ^ |

Снимаю шляпу. На такое бы я точно не решился в отечественном поезде/вокзале.

→ Ответить

Gantz

13 лет назад, # ^ |

Был раунд, который писал в микроавтобусе на нетбуке через 3G, но смог сдать только 2 задачи. К счастью тот раунд был не рейтинговым =)

→ Ответить

Egor

13 лет назад, # ^ |

Да, я, естественно, тоже использовал tethering 3g/edge с телефона

→ Ответить

JalbaRu

13 лет назад, # ^ |

+11

Писал как-то раунд в дороге с обычного телефона(разрешение экрана 160 на 128). Написал конечно не очень, но несколько задач все же сдал

→ Ответить

sdryapko

13 лет назад, # ^ |

Жесть :)

→ Ответить

k-va

13 лет назад, # ^ |

Вот тоже припоминаю, как Гена из вагона решал один из первых раундов CF. В какой-то момент сдохла батарея, а при попытке подключиться к вагонной розетке проскочила какая-то длинная искра. При этом нетбук не ожил, но и, как позже выяснилось, не умер навсегда. Зато получили истерическое требование от проводницы "больше не пробовать!".
А по поводу +3: по-моему на CF резко изменили систему расчета рейтинга. Гена сейчас за первое место получает втрое большую прибавку, чем ранее. Причем очень похоже, что просто используется формула с TC. Именно там при высокой волатильности не очень страшен такой, как у Вас (не лучший :)), результат у одного из лидеров. Если формула с TC, то это можно только приветствовать. Зачем изобретать велосипед, если есть апробированный метод.

→ Ответить

13 лет назад, # |

-31

Кстати, лучше не писать в английских условиях cnt. Англоязычным участникам это может не очень понравиться.

→ Ответить

sdryapko

13 лет назад, # ^ |

Из-за чего может не понравиться?

→ Ответить

13 лет назад, # ^ |

-29

cnt -> cunt.

→ Ответить

San_Sany4

13 лет назад, # ^ |

-18

А так же count -> cunt, ага. И как быть?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

-20

А на какое из двух слов cnt больше походит?

→ Ответить

San_Sany4

13 лет назад, # ^ |

Ну не знаю, ИМХО «cnt» — уже устоявшееся сокращение.

→ Ответить

ketzer

13 лет назад, # ^ |

лучше б Count написали, нашли на чём сэкономить ))) 21 век на дворе, 2 байта зажали

→ Ответить

Schullz

13 лет назад, # ^ |

+12

При хорошей фантазии почти любое слово может не понравиться =)

→ Ответить

KADR

13 лет назад, # |

← Rev. 3 →

+21

Я один в Е искал подстроку? Мне кажется, стоило добавить претест 3 в условие, или хотя бы в пояснении показать, что возможно не только 747, а и 747.

→ Ответить

package.zaic

13 лет назад, # ^ |

Нет, не один... :(

→ Ответить

cmd

13 лет назад, # ^ |

Я тоже вначале искал подстроку, написал решение, заслал - получил WA на третьем тесте =) Потом перечитал условие и пришлось переписывать часть кода =)

→ Ответить

KADR

13 лет назад, # ^ |

Ну мне надо было удалить строк 10 и 4 штуки еще поменять, что заняло пару минут. Но вот обнаружить на контесте, что решаю не ту задачу так и не успел.

→ Ответить

flashmt

13 лет назад, # |

+15

This is your 3rd contest I participated in (the others are round 77 and 91). Surprisingly, I became red after all of them. In my opinion, they're truly "lucky" contests :-)

→ Ответить

13 лет назад, # |

+29

tourist got +47 to the rating (just another lucky number :)

→ Ответить

mkagenius

13 лет назад, # ^ |

looks like "47" is the luckiest of all the lucky number.
[frequency of its occurrence on this page taken into account]

→ Ответить

sjtu_pigoneand

13 лет назад, # |

I solved the problem E in last 30 seconds, it's a prize for me in Chinese New Year~

Thank you code force ;)

→ Ответить

jonathanirvings

13 лет назад, # |

+19

I got +4 rating increase in this round. It's the lowest lucky number :(

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Your contribution is : +47 which is lucky

Your Registration is 13 month ago. so 1 + 3 = 4 which is lucky sum

Your Rating is: 2023. so 2 + 0 + 2 + 3 = 7 which is lucky sum

So ;you are really lucky in this month.

Wait not finish. Your previous contest rating increase +16. so 1 + 6 = 7. That is also lucky sum.

ha ha ha ha :)

→ Ответить

jonathanirvings

13 лет назад, # ^ |

Thanks. I even didn't notice that :p
I hope I will get +117 rating increase in the next Codeforces Round.
It is lucky multiplication (1 x 1 x 7 = 7), and my rating will be 2023 + 117 = 2140, it is lucky sum (2 + 1 + 4 + 0 = 7).
ha ha ha ha :)

→ Ответить

13 лет назад, # ^ |

welcome. excellent. :(

→ Ответить

map

13 лет назад, # |

Спасибо за контест!
Задачи С и Е понравились.

→ Ответить

13 лет назад, # |

← Rev. 2 →

-7

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

But how can i understand 04,07,044,047,077 are either lucky numbers or not.

I think that those are also lucky numbers.

Because above numbers are equivalent to 4,7,44,47,77.

Can anyone explain me, whether am i wrong or correct?

Thanks.

→ Ответить

SyFy

13 лет назад, # ^ |

← Rev. 2 →

decimal record contains only the lucky digits 4 and 7

0 is not a lucky digit.

→ Ответить