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

  • Adventures и «адвенчуристы» 20-го века.

    Мальчики и девочки, те из вас, кто прочитал мой предыдущий пост до самого конца, знают - я уже несколько дней на совершенно замечательной…

  • Ответы о мячах.

    Всем привет! То ли моя недавняя задачка о мячах была слишком сложной, то ли слишком простой, а может быть просто не было достойной мотивации типа…

  • Задача о мячах.

    В эфире регулярная рубрика "О физико-математическом" - лучшая зарядка для ума, чтобы извилины были гладкими и шелковистыми, а серое вещество самой…


Исходим из предположения, что расплатиться за взвешивания можно будет потом (иначе риск погореть прямо на первом взвешивании явно ненулевой).
Делим на 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