Цифровой 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-го века.

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

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

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

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

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


1. делим на три кучки 672 672 674
взвешиваем первые две
1а если равны, то фальшивка в третьей
1б2 иначе берем взвешиваем первую кучу с третьей без 2х монет

1б2а если равны, то фальшивка во второй
1б2а иначе, фальшивка в первой
(теперь мы уже знаем больше или меньше фальшивка)

Далее так же делим кучку с фальшивой на три по итерации, считая что нам не везет и выпадает кучка с большим количесвом монет
3. 674 на три 224, 224, 226
4. 75, 75, 76
5. 25, 25, 26
6. 8, 8, 10
5. 3, 3, 4
6. 1, 1, 2
7. 1 и 1 (если так же не повезло на 6м шаге)

платим за взвешивания 7
платим за выход 5
итого: 2018 - 5 - 7 = 2006

вроде норм ? )

Не, не норм.
Первые два шага засчитаны как 1 и 2.
Следующие два взвешивания засчитаны как одно (номер 3).
То есть, данный алгоритм = 14 взвешиваний, а не 7.

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

Эх, а вот вычесть 1 фальшивую забыл.

1а - фальшивка в третьей, но мы не знаем, тяжелее она или легче. Поэтому начиная с шага 3 мы не можем при неравенстве определить, где фальшивка. Т.е. перейти от 1а к 3 нельзя.

если от 1a мы переходим к 3му (т.е. делим на три уже третью кучку), то одно взвешивание у нас в резерве (для выяснения легче или тяжелее фальшивка)
Этот резерв мы можем применить на любом из последующих шагов.

Edited at 2017-12-15 17:07 (UTC)

?

Log in

No account? Create an account