nullemotion Sep 18 2018 at 17:47

Задача с небоскрёбом и яйцами — не бином Ньютона?

8 min

27K

Python*Mathematics*

From sandbox

+42

Comments 35

algotrader2013 Sep 18 2018 at 22:15

Можно было что-то быстрое типа С использовать? Может тогда удалось бы и в лоб уложиться по скорости?

rafuck Sep 19 2018 at 00:00

Там, как ни странно, тоже не больше 64 бит в целом числе.

nullemotion Sep 19 2018 at 11:25

Можно, но суть была в решении именно на питоне, раз уж я его осваиваю. К тому же, как пишут выше, там тоже int64 и пришлось бы дополнительно решать и эту проблему.

AngReload Sep 19 2018 at 12:35

В Rust есть тип u128, вот где можно было бы посмотреть производительность.

khim Sep 19 2018 at 14:32

Нельзя. Числа по экспоненте растут, так что быстренько переполнят любой фиксированный размер. А вот их длина в цифрах растёт линейно, так что в память компьютера ответ влазит спокойно.

AngReload Sep 19 2018 at 18:20

Да уж, посмотрел на число height(9477, 10000):

Спойлер тык

1995063116880758384883742162683585083823496831886192454852008949852943
8830221946631919961684036194597899331129423209124271556491349413781117
5937859320963239578557300467937945267652465512660598955205500869181933
1154250860846061810468550907486608962488809048989483800925394163325785
0621568309473902556912388065225096643874441046759871626985453222868538
1616943157756296407628368807607322285350916414761839563814589694638994
1084096053626782106462142733339403652556564953060314268023496940033593
4316651459297773279665775606172582031407994198179607378245683762280037
3028854872519008344645814546505579296014148339216157345881392570953797
6911927780082695773567444412306201875783632550272832378927071037380286
6393031428133241401624195671690574061419654342324638801248856147305207
4319922596117962501309928602417083408076059323201612684922884962558413
1284406153673895148711425631511108974551420331382020293164095759646475
6010405845841566072044962867016515061920631004186422275908670900574606
4178569519114560550682512504060075198422618980592371180544447880729063
9524254833922198270740447316237676084661303377870603980341319713349365
4622700563169937455508241780972810983291314403571877524768509857276937
9264332215993998768866608083688378380276432827751722736575727447841122
9438973381086160742325329197481312019760417828196569747589816453125843
4135959862784130128185406283476649088690521047580882615823961985770122
4070443305830758690393196046034049731565832086721059133009037528234155
3974539439771525745529051021231094732161075347482574077527398634829849
8340756937955646638621874569499279016572103701364433135817214311791398
2229838458473344402709641828510050729277483645505786345011008529878123
8947392869954083434615880704395911898581514577917714361969872813145948
3783202081474982171858011389071228250905826817436220577475921417653715
6877256149045829049924610286300815355833081301019876758562343435389554
0917562340084488752616264356864883351946372037729324009445624692325435
0400678027273837755376406726898636241037491410966718557050759098100246
7898801782719259533812824219540283027594084489550146766683896979968862
4163631337639390337345364705210334946992807695424998015434554419604972
0110441880956939571653303125965015135210943821418326301263747755849915
3903118496006204058391848066965740116387712238766843083935461543570078
7919717627857701089777687150929331227144630832591520741168358116286487
7565099831828100966285215817182861422299916721214461558309048173509038
7001441410929356271067299623058736038309381606539418756332546492084862
4754106309445450000766614442658986590440294410056543425216164145405957
4448959059378469034843694065251975339636452128242737679086169540365161
2611037813018425887181517759521244936929012753512804535668290997304117
4260741570366091288999689339228166640991291393437748914268878423534395
4049469043333120897248862080530937185907276885584072254792345533781517
7531513208181025079503071945162015474124959831456142524021378338539846
5907754354237669900827718865044859993016353612300104712648588594547564
4

Такое без BigNumber не прокатит.

Certik Sep 19 2018 at 19:44

Обычно для более быстрых языков и лимиты по времени меньше. Так что нет никакого смысла их использовать.

MikailBag Sep 20 2018 at 10:17

Обычно лимита равные для всех языков. Ни разу не видел обратного.

Certik Sep 20 2018 at 14:56

На HackerRank (кажется так пишется) точно разные. Ну и если лимит одинаковый, то на некоторых языках оптимизация будет не нужна совсем, а на других, возможно, и с оптимизацией с трудом получится влезть в лимит. И тогда не вполне понятен смысл упражнения.
Покажите лучше, где они одинаковые.

MikailBag Sep 22 2018 at 15:10

CodeForces, всероссийская олимпиада школьников, московская олимпиада школьников, открытая олимпиада школьников, московская командная олмпиада — видел лично. Еще вроде ACM ICPC, например.

Taus Sep 19 2018 at 00:34

Как только вы получили рекуррентную формулу, то можно попробовать получить замкнутую или сильно упростить себе вычисления. Например, для такой рекуррентной формулы легко получить производящую функцию, домножив на x^n y^m и просуммировав. А дальше дело алгебраических преобразований и вы получите, что коэффициент в производящей функции перед x^n y^m равен сумме биномиальных коэффициентов.

Dmitri-D Sep 19 2018 at 03:05

типичная задача динамического программирования

Tinsane Sep 19 2018 at 07:24

Просто оставлю тут ссылки на ту же задачу, но в немного другой формулировке:
acm.timus.ru/problem.aspx?space=1&num=1223
acm.timus.ru/problem.aspx?space=1&num=1597

kmorozov Sep 19 2018 at 08:15

f(1,m) скорее 2m-1 или 2m-2. Если с первого не разбилось, тогда надо пробовать третий. Если разобьётся — то ответ 2, если нет — идём на пятый.

TheRexx Sep 19 2018 at 09:15

Если разобьется — то ответ 1, мы не можем проверить разобьется ли со 2 этажа. Так что правильней измерять при n=1 каждый этаж снизу.

MaximChistov Sep 19 2018 at 09:43

если все яйца разбиваются с одного этажа, что мешает вам использовать бинарный поиск?

Tyusha Sep 19 2018 at 10:18

Вы не вникли в алгоритм, вернее в задачу. Бинарный поиск не даст решения, когда много этажей и мало яиц.

berez Sep 19 2018 at 10:21

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

ЗЫ: А, понял — недобитые яйца можно переиспользовать!

ipodman Sep 19 2018 at 11:17

У вас два яйца и 100 этажей, яйца разобьются с 10-го этажа.
Вы сбросили с 50-го этажа, яйцо разбилось, у вас осталось одно яйцо.
Вы сбросили с 25-го этажа, яйцо разбилось. У вас не осталось яйц и вы не решили задачу.

wilerat Sep 21 2018 at 22:22

Бросаешь яйца с делением оставшихся этажей на 2, пока не останется одно яйцо.
И это последнее яйцо бросаешь с нижней границы добавляя по 1 этажу.

ipodman Sep 22 2018 at 15:42

У вас два яйца и 100 этажей, яйца разобьются с 49-го этажа.
Вы сбросили с 50-го этажа, яйцо разбилось, у вас осталось одно яйцо.
Вы начинаете бросать с первого этажа до 49-го, всего уйдет 50 попыток. При этом существует решение, в котором задача решается в худшем случае за 14, вы проиграли.

wilerat Sep 23 2018 at 23:10

Да, действительно. Мне кажется в статье не очень понятно излагалась суть и решение первоначальной задачи. Перечитал ещё раз всю статью заново. Классное решение.
Однако, если имеется несколько яиц (больше двух), мне кажется (просто сугубо личное мнение), что первоначальный бинарный поиск очень сильно сократит время и количество попыток для поиска этажа.
То есть, если, например, яйца начинают биться с 51 этажа, то бинарным поиском это определится с 3 попытки, а в оригинальном решении потребуется больше бросков.
То есть, если яйца могут разбиться с равной вероятностью с любого этажа, ведь логично сразу отбросить 50% вариантов.
Однако не могу ручаться, что это действительно так, нужно провести тесты и смотреть, действительно ли, если половину (или какой то первоначальный процент) попыток отвести на бинарный поиск, общее количество попыток уменьшится.

khim Sep 24 2018 at 02:45

Жуть какая. Дожили. Уже элементарную математическую задачу тестами решают. Бинарный поиск эффективен тогда, когда у вас достаточно яиц, чтобы его довести до конца. В противном же случае неразбившиеся яйца становятся ценным ресурсом, который вам нужно экономить — а вы его транжирите, кидая из с этажай, откуда они, скорее всего разобьются. Причём этот эффект от «потери яйца» заметнее всего вначале, а не в конце.

Оптимальный этаж, откуда нужно кидать яйцо, находится ниже середины, причём чем меньше у нас яиц — тем ниже.

stu5002 Sep 19 2018 at 11:17

Их ограниченное количество

achekalin Sep 19 2018 at 10:27

Вы бы хоть исходную задачу написали в начале нормально, а потом уже свою вариацию.

На случай, для тех, кто не знал ее:

Дано 100-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с любого меньшего этажа, оно не разобьется. У вас есть два яйца. Найдите N за минимальное количество бросков.

UFO just landed and posted this here

ipodman Sep 19 2018 at 11:29

Конечно

malkovsky Sep 19 2018 at 14:31

По поводу постановки задачи: «максимальный этаж, с которого можно бросить яйцо, не разбив» — это не ваша функция f(n, m). Если яйцо не разбивается с этажа k, но разбивается с этажа k+1, то f(n, m) — это максимальное такое число h, что с запасом n яиц и m попыток мы можем гарантировано найти k, если известно, что k<=h.

В финальном коде есть строчка
h += t
Быть может там имелось в виду
h += bk
?

nullemotion Sep 21 2018 at 22:24

Да, конечно. Исправил, спасибо.

lggswep Sep 19 2018 at 17:00

Друзья, если я захочу решить эту задачу, то кто(что) решает разбилось яйцо или нет? Это какая-то функция или файл со этажами? Не бейте сильно за столь глупый вопрос, но у меня часто возникаю такие вопрос в подобных задачах

khim Sep 19 2018 at 17:22

Странный вопрос. Что значит «кто решает»? Что это вообще значит? Задача ведь в том, чтобы найти максимальное количество этажей в небоскрёбе, при котором задача разрешима, а не эмулировать процесс кидания яйца! Вам дают два числа на вход, вы выдаёте одно на выход… и… всё.

lggswep Sep 20 2018 at 10:20

Верно, так а как я узнаю что задача решаемая для данных параметров входа? Пример из статьиб есть 1 яйцо и 10 этажей. Почему ответ 10? Как узнать когда оно разобьеться, какая здесь закономерность?

khim Sep 20 2018 at 14:37

Потому что если у вас есть только одно яйцо — то у вас нет выбора, кроме как кидать его с 1го этажа по 10й. Ибо если вы кинете его с 6го этажа и с 8го и оно переживёт первое падение, но не второе — то вы не сможете сказать: ответ — это 7 этажей или 8. Пропуски недопустимы. Но если в небоскрёбе 11 этажей, яйцо одно и попыток 10, то как бы вы ни кидали — а всегда есть шанс, что ответ вы дать не сможете… ибо если яйцо останется целым на 10м этаже, то, снова, неясно — ответ 10 или 11…

Вы вообще статью-то читали? Там это упоминается…

slonopotamus Sep 20 2018 at 10:56

def height(n, m):
    arr = [0]*(n+1)
    while m > 0:
        arr = [0] + list(map(lambda x,y: x+y+1, arr[:-1], arr[1:]))
        m-=1
    return arr[n]

Думаю что это решение тормозит потому что истерично занимается копированием arr вместо того чтобы делать что-то полезное. Я вижу примерно четыре копирования на одну итерацию цикла.

mk2 Sep 22 2018 at 15:25

Большие числа в задаче на ДП — это странно.
Как правило, в таких случаях просят результат по модулю большого простого, 10^9 + 7 например.

Show the best of all time