Цифровой 2018 - часть 4. О деньгах.

Previous Entry Поделиться Next Entry
14 декабря, 2017
e_kaspersky
Отлично получается! Совершенно необычные и удивительно красивые решения выдают на-гора наши самые мат-продвинутые читатели. Спасибо и поздравляю! Ещё посылка с ценными призами будет незамедлительно отправлена sir_derryk - отличная идея про последовательность единиц и остатки от деления! Ура самым сообразительным!

Но пора всех порадовать ещё задачками-2018. И у меня есть вот какая ->

Однажды настоящий честный русский программист был схвачен непонятной внешности кибер-гос-джиннами и заточён навечно в подземные неведомые скально-пещерные скрепы... И всё на этом. Как вы бы могли подумать, что через сто-пятьсот-тысяч-столетий найдут его, согбенного мумифицированного, в пещере и без клавиатуры.

Ан нет! Настоящий русский программист везде найдёт багу в чужом коде! И вот, есть такая!

Откопал он в неведомой пещере чудесный клад, а там - аж целых 2018 биткоинов золотых монет! Но есть одна засада... Одна монета - фальшивая, она отличается по весу от остальных. Легче или тяжелее - неизвестно. Но другая. На вид, вкус и запах такая же. Но чуть другого веса.

Короче. У настоящего русского программиста есть 2018 монет, одна из которых "левая" и отличается по весу. Есть охранник, дверь и весы. Весы самые простые - насыпаешь на левую лапу, на правую лапу = они показывают ниже-больше или же просто равенство тяжести. Русскому программисту нужно выйти наружу без палева - чтобы никаких фальшивок на руках не было.

Ценник в пещере следующий:
- Каждое взвешивание стоит один биткоин одну золотую монету.
- Выход из пещеры через коррумпированного стражника стоит ещё пять золотых монет, но если среди них найдётся хоть одна фальшивая, то будет русскому программисту exception, несовместимый с продолжением его трудовой истории.
- Если фальшивая монета найдётся "в багаже", то будет та же самая история.

Короче, ему нужно найти фальшивую монету и избавиться от неё.

Так вот: хороший программист - сколько он гарантированно вынесет голда с этой фармы? По максимуму - сколько? И чтобы 100% гарантия результата, то есть без жертв и разрушений.

У меня получилось... много. Целых 2003 штуки. Как так получилось? Дерзайте - вдруг получится ещё больше? :)



P.P.S. Уже поправил, приношу извинения за приченённые неудобства... Извините.
P.S. Ой-ой-ой, я облажался с постановкой задачи. Конечно же, требуется вычленить фальшивую монету за оптимальное количество взвешиваний. А потом уже за пять монет покинуть помещение. Приношу извинения, но задача формулируется немного более изощрённо.
Метки:
Previous Entry Поделиться Next Entry

Записи из этого журнала по тегу «chtogdekogda»


> Чтобы найти фальшивку, нужно 8 взвешиваний.

Не верю.
Минимум 9.

Интересно! У меня получилось 10 и даже 11 взвешиваний. А вы фальшивую не пытались вынести?

Выше уже написали решение, только как-то сумбурно.

Идея в том, чтобы каждый раз делить монеты на 3 примерно равные кучки и взвешивать две из них. Если бы мы знали, тяжелее фальшивка или легче, достаточно было бы 7 взвешиваний:

1. 2018 = 672 + 672 + 674
2. 674 = 225 + 225 + 224
3. 225 = 75 + 75 + 75
4. 75 = 25 + 25 + 25
5. 25 = 8 + 8 + 9
6. 9 = 3 + 3 + 3
7. 3 = 1 + 1 + 1

Чтобы узнать, легче или тяжелее фальшивка, нужно после первого дизбаланса весов провести одно дополнительное взвешивание, поменяв на одной из чаш все монеты на заведомо настоящие.

Допустим, равновесие нарушилось на самом первом шаге, причём левая чаша оказалась легче. Значит, 674 монеты, что были отложены в сторону -- все настоящие, а фальшивка -- где-то на весах.

Сваливаем монеты с правой чаши в отдельную кучу, и вместо них кладём 672 проверенные монеты. Если неравенство сохранилось, то фальшивка -- в левой чаше, и она легче. Если весы уравновесились -- фальшивка тяжелее и находится в той кучке, что была снята с правой чаши.

> Допустим, равновесие нарушилось на самом первом шаге

Допустим, равновесие НЕ нарушилось на самом первом шаге (а это вероятность примерно 1/3). Что делать?

Думайте дальше..

Если равновесие не нарушилось ни разу, то через 7 взвешиваний остаётся одна невзвешенная монета, она и есть фальшивка.

А если нарушилось, неважно на каком шаге, то после него и проводим дополнительное взвешивание, поменяв монеты на одной из чаш на заведомо настоящие и оставив на другой какие были. Оно и покажет, на какой из чаш изначально была фальшивка, и в какую сторону отличается её вес.

После первого взвешивания, имеем либо 674 настоящих монеты (что больше 672, необходимых для дополнительного взвешивания, даже если одну отдать), либо аж 1344. При последующих взвешиваниях, число монет в чашах уменьшается, а число заведомо настоящих растёт, поэтому всегда есть возможность набрать нужное для дополнительного взвешивания количество.

А зря не верите:) Написал ниже. 8 взвешиваний, если повезет - 4 (но если повезет, то и не надо искать фальшивку).

?

Log in

No account? Create an account