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


Не программист пытается выбраться на волю

ecolimp

2017-12-14 19:36 (UTC)

Если за взвешивания можо расплатиться в конце процедуры, поступим так.
2018 делим на две кучки по 1009 монет и взвешиваем эти кучки. Они равновесия НЕ покажут из-за фальшивой монеты. Будем делить и все время брать легкую половинку, чтобы не сбиться,при нечетном числе в кучке одну монетку будем убирать (откладывать на вынос). Так же на вынос откладываем кучку монет с более высоким весом. Предположим, что мы не везучие, и на фальшивую монетку мы наткнемся в самом конце.
2. Второе ... десятое взвешивание . При десятом взвешивании на весах лежит по монетке на каждой чашке. Одна чашка легче. Одна из монет - фальшивая. Но какая - мы не знаем, поскольку не знаем, тяжелей она или легче, т.е. фальшивой может оказаться монетка и на левой или на правой чашке. Но одна - точно НЕ фальшивая.
3. Снимаем с весов одну монетку, которая имеет меньший вес. На ее место кладем одну монетку из отложенных кучек (там нет фальшивых!). Если весы покажут равновесие, та мы, значит, оставили на весах НЕ фальшивую, а фальшивую - сняли (она легче не фальшивых, оказывается). Если весы не покажут равновесия, то значит наша монетка осталась на весах. Если фальшивка легче, то чашка с нормальной монеткой перевесит фальшивку, если тяжелее - наоборот, фальшвка тяжелей.
4. Замечание. Если мы вдруг при очередном (втором... девятом) взвешивании увидим равновесие, значитфальшивая монетка в только что отложенной кучке. Это сократит число взвешиваний, а значит и наши потери, на семь ... одну монетку.
Итак мы теряем 10 монет и 5 монет стражнику. А еще наша потеря - фальшивая. Зачем нам она, выбросим. Итого мы можем вынести 2018 - 10 взвешиваний - 5 монет стражнику = 2003 - одну манетку фальшивую выбросить. Итого - 2002 голд!. Но тут я схитрл и замену монетки при последнем взвешивании не посчитал взвешиванием (ведь одна монетка оставалась на весах! Если стражник возмутится, я особе не буду спорить. Ведь я не программист. И тогда я вышесу 2001 монету.

Edited at 2017-12-14 19:47 (UTC)

Re: Не программист пытается выбраться на волю

ostapru

2017-12-14 20:03 (UTC)

А зачем взвешивать половинки после 1го деления, если и так известно, что в куче из 2018ти монет есть фальшивка?

Re: Не программист пытается выбраться на волю

ecolimp

2017-12-15 09:05 (UTC)

Если не взвесить, то не узнаем, где фальшивая 1009+1009, значит, каккую кучку делить пополам для дальнейшего поиска.

Edited at 2017-12-15 10:12 (UTC)

Re: Не программист пытается выбраться на волю

ostapru

2017-12-15 16:14 (UTC)

Делим кучу на 2 по 1008 и 1010 монет, потом ту, что 1008 делим на 2 по 504. Взвешиваем половинки по 504. Если равны, то фальшивка в куче из 1010 монет.

Re: Не программист пытается выбраться на волю

ecolimp

2017-12-15 16:45 (UTC)

А дальше? У меня неверное решение. Первое взвешивание не нужно. Но дальше я не проверил одну из частей в 1009 мон. Это 2 взвешивания. Дальше аналогично надо идти. Но верного я пока не нашел. Все времени не выберу.

Re: Не программист пытается выбраться на волю

ostapru

2017-12-15 16:49 (UTC)

Берём кучу, где фальшивка, делим на 2 части - можно не равные, чтобы полученные части делились на 2. Одну из частей делим на 2 и взвешиваем. И т.д. и т.п.

Re: Не программист пытается выбраться на волю

e_kaspersky

2017-12-15 07:20 (UTC)

Нет, не катит.
> все время брать легкую половинку,

В условии сказано, что легче или тяжелее фальшивка - неизвестно.

Re: Не программист пытается выбраться на волю

ecolimp

2017-12-15 08:56 (UTC)

Но во всех случаях весы когда не уровновешены, одна чашка легче, другая тяжелее. Но это излишнее условие яввел Оно не являетнся необходимым. Можно снимать любую чашку для "выноса" - другую использовать для продолжения поиска.
Как только мы увием равновесие на весах, это значит, что на весах все монеты подлинные. Фальшивая была отложена (так может получиться при 2-м, 5-м, 7-м,9-м,10-м взвешиваниях).
Вот ход идентификации фальшивки:
Делим 2018 на две кучки: 2018:2= 1009 Начинаем взвешивание.
1) 1009 и 1009. Равновесие не возможно. Фальшмонета в одной из кучек по 1009.
2) Откладываем монеты с одной чашки (1009) и делим монеты с другой чашки на две кучки по 504, 1 монетку отложим. взвешиваем. Если равновесие - мы толькро что отложили фальш монетку. Задача решена. Но... невезение: нет равновесия.
3) Делим 504 на две кучки по 252, взвешиваем. Равновесия нет.
4) Делим 252 на две кучки по 126 и взвешиваем. Равновесия нет.
5) Делим 126 на две кучки: 63 и 62 +1 монетку отложим. Взвешиваем по 62. не везет: нет равновесия.
6) Делим 62 на две кучки по 31, взвешиваем. Равновесия не будет.
7) Делим 31 пополам: 15 и 14 +1 отложена. Если равновесие – задача решена. Но… невезуха
8) Делим 14 на две кучки: 7 и7 . Равновесия не будет.
9) Делим 7 на две кучки: 3 и 3 + 1 отложим. Если равновесие – задача решена. Но… невезуха
10) Делим 3 на две кучки: 1 и 1 и 1 откладываем. Если равновесие – задача решена. Но… невезуха
11) Снимаем с более легкой чашки монетку, кладем вместо нее одну из ранее отложенных (они все не фальшивые). Если равновесие, задача решена: значит, отложена фальшивая. Если равновесия нет, то на весах одна только что положенная нами подлинная монета и другая, которую мы не трогали – фальшивая. Эту операцию, поскольку на одной чашке мы не трогали монету, я не счел взвешиванием, стараясь увеличить свою выгоду. Но охранник может настаивать, и я должен оплатить и эту манипуляцию с заменой монеты
Итак, мы провели 10 (11) взвешиваний, 5 монет отдадим охраннику, одну (фальшивую) ывыбросим. У нас останется на вынос:
2018 - -10 (или11) (взвеш.) -5 (охр) – 1(выбросили)= 2002 ( или 2001)


Edited at 2017-12-15 10:27 (UTC)

?

Log in

No account? Create an account