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

Отлично получается! Совершенно необычные и удивительно красивые решения выдают на-гора наши самые мат-продвинутые читатели. Спасибо и поздравляю! Ещё посылка с ценными призами будет незамедлительно отправлена — отличная идея про последовательность единиц и остатки от деления! Ура самым сообразительным!

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

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

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

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

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

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

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

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

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

Прочитать комментарии 2
Комментарии 2 Оставить заметку

    Дмитрий

    Повторный пост или модерацию проходит первый?
    В любом случаи оочень подробный алгоритм ниже)
    Пошаговый алгоритм :

    1) Откладываем 2 монетки
    2) оставшиеся 2016 делим на 3 кучки — получаем 3 кучки по 672 монетки

    3) теперь у нас большие 3 кучки и 2 монеты. среди этих 4х наборов должна быть фальшивка. Теперь есть два сценария — либо фальшивка в трех больших кучках либо среди 2х отложенных.
    3.1)если фальшивка в трех бОльлших кучках то за 2 взвешивания* этих кучек выясняем а)какая из трех содержит фальшивую, б)в какую сторону отклонение у фальшивой и переходим к шагу 4.
    3.2)если кучки оказались равные то считаем что три кучки по 672 настоящие а 2 монетки содержат фальшивую. Значит добавим к 2м монеткам одну настоящую можем выявить подделку за 2 взвешивания и в целом мы пришли к цели.

    4) кучку из 672х монет содержащую фальшивую делим снова на три по 224 и, имея информацию о перевесе/недовесе фальшивки, за одно взвешивание** выясняем какая из трех содержит фальшивую
    5) в фальшивуб кучку из 224х монет добавляем 1 настоящую монету чтобы снова поделить на 3 кучки и за 1 взвешивание отбираем кучку с фальшивкой из 75 монет
    6) 75 снова делим на 3 кучки и снова за 1 взвешивание подозрительную кучку из 25
    7) добавляем к подозрительной кучке 2 настоящие монеты и вновь в бой — за одно взвешивание — подозиртельная кучка из 9
    8) 1 взвешивание и кучка из 3х
    9) последнее взвешивание и — ура! — фальшивка нашлась

    Считаем — на шаге 3.1 — 2 взвешивания, на шагах с 4 по 9 по 1му — итого 8 взвешиваний в максимальном сценарии (в минимальном сценарии 4 взвешивания, см. шаг 3.2).
    8 взвешиваний = 8 монет + 5 монет за выход = 13 монет «налога». Итого 2018 — 13 — 1(фальшшивка) = 2004.

    * как за 2 взешивания выясним
    а)какая из трех содержит фальшивую,
    б)в какую сторону отклонение у фальшивой
    ?
    Кладем на весы 2 кучки. Если они равны, то это кучки настоящие а третья фальшивка. Значит заменяем, например, правую кучку 3й кучкой (пошло 2е взвешивание) и получаем ответ — легче фальшивка или тяжелее.
    Ежели первые 2 кучки были разные что делаем? Запоминаем в какую сторону отклонились весы и поступаем как в первом случае. Меняем кучку на правой чаше. Ежели весы стали ровные то мы сняли фальшивку и то отклонение которое запомнили скажет нам легче или тяжелее фальшивка. Ежели весы вновь отклонились, то значит фальшивка на левой чаше и текущее положение весов скажет нам о весе фальшивки.

    ** как за 1 взвешивание узнать где фальшивка среди 3х имея информацию об отклонении веса фальшивки? думаю даже объяснять не стоит) но коли взялся — напишу — кладем вде кучки на весы. Если кучки равные — то фальшивка в третьей. Если разные, то по информации о весе фальшивки выбираем кучку с фальшивкой.

    Пухальский Федор

    Монета будет тоньше

Оставить заметку