Цифровой 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»


Исходим из предположения, что расплатиться за взвешивания можно будет потом (иначе риск погореть прямо на первом взвешивании явно ненулевой).
Делим на 4 группы - три по 672, последняя 2. Взвешиваем первую со второй и первую с третьей. Таким образом, задача сводится либо к 672 монетам, и известно, легче она или тяжелее, либо к 2 монетам, но тогда неизвестно, легче она или тяжелее. Итого либо 2 взвешивания, 672 монеты и известно, легче фальшивая или нет, либо осталось две монеты, одна из которых фальшивая.
Во втором случае выкидываем нахрен обе эти монеты (чтобы найти фальшивку, надо заплатить 2 монеты, а если выкинуть, то теряем всего одну настоящую). Итого 2 взвешивания, 2 монеты выкинуто и 5 стражнику. Выносим 2009.
Далее по стандартной схеме делим на три части. 224, 75, 25, 9, 3, 1. Шесть взвешиваний.
В сумме 8 взвешиваний = 8 монет. 1 фальшивая, выкинуть. 5 за выход. На кармане - 2004 монеты.
Итого если сильно повезет, то 2009. Если нет - 2004.

А, поправка. Если после первых двух взвешиваний три большие кучи равны, то выделить фальшивку из двух монет можно за одно взвешивание. Но все равно смысла нет - ту же самую монету и заплатим, так что проще выкинуть.

А, кстати, ниже заметили, что формального запрета на расплату за взвешивания фальшивкой нет. Тогда минимум 2005, максимум (если повезет) 2010.
Но мне почему-то кажется, что это читерство:) Хотя по формулировке задачи: "ему нужно найти фальшивую монету и избавиться от неё" - допустимо.

> Далее по стандартной схеме делим на три части.
> Шесть взвешиваний.

Шесть ПАР взвешиваний!
Итого в сумме = 14 взвешиваний.

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

Нет. Шесть взвешиваний. Процитирую себя:
>>задача сводится либо к 672 монетам, и известно, легче она или тяжелее
Подчеркну: после двух взвешиваний кучек по 672 монеты мы УЖЕ ЗНАЕМ, легче или тяжелее фальшивка. Да, именно это критично.
Соответственно:
1. Делим на три. В первом случае - 224 монеты в кучке.
2. Взвешиваем первую и вторую кучку. Если они не равны - то мы знаем, где фальшивка (ибо мы ЗНАЕМ, легче она или тяжелее). Если они равны - то фальшивка в третьей.
3 и далее. Повторяем предыдущие шаги. 75, 25, 9, 3, 1.

Поскольку мы знаем, тяжелее или легче фальшивка, взвешивать достаточно две кучки из трех - это ОДНО взвешивание.

?

Log in

No account? Create an account