Цифровой 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. На примере стопки из 27-и момент: мы можем взвесить 2 по 13 и, если они равны, то оставшаяся будет фальшивкой. Таким образом сэкономим больше.
2. Не сказано, можно ли заплатить за взвешивание фальшивой монетой.
3. Охранник знает, какая из монет фальшивая. Раз мы можем его подкупить, то я заплачу в 2 раза больше. И уйду с 2007-ью монетами.

Мой вариант решения:
Делим 2018 монет на 8 стопок (6х252+2х253).
Делаем 2(4) контрольных взвешивания, чтоб понять легче или тяжелее фальшивка.
Выбираем нужную стопку, платим 2(4) монеты.
Остается 252 шт. (для удобства).

Разбиваем на 3 стопки по 84 шт.
Взвешиваем, выбираем, платим 1 монету.
Остается 84-1=83 шт.

Делим на 3 стопки (2х28+27). Взвешиваем, выбираем, платим 1 монету.
Остается 26 шт.

Делим на 2 стопки (2х13). Взвешиваем, выбираем, платим 1 монету.
Остается 12 шт.

Делим на 3 стопки (3х4). Взвешиваем, выбираем, платим 1 монету.
Остается 4-1=3шт.

Взвешиваем, находим фальшивую монету, платим 1 монету.

Итого: 7(9) монет платим за взвешивание, 1 фальшивую оставляем, 5 платим стражнику. 2018-7(9)-1-5=2005(2003) монеты можно унести с собой.

> Делим 2018 монет на 8 стопок (6х252+2х253).
> Делаем 2(4) контрольных взвешивания, чтоб понять легче или тяжелее фальшивка.
> Выбираем нужную стопку, платим 2(4) монеты.

Обоснуйте. И непонятно какой вывод от взвешивания стопок 252 и 253. Наверное, в стопку 252 надо докинуть монетку из соседней? Но тогда на шаге 2 будет не 252 монет в кучке, а 253. И алгоритм получается на 10 шагов.

> Взвешиваем, выбираем, платим 1 монету.
> Остается 84-1=83 шт.

Платим монетой из подозрительной стопки? За это секир-башка с вероятностью 1/84-я.

Ответ сына:)

2 контрольных взвешивания, если найдём стопку с разницей в весе из первых 4-ёх стопок, а если нет - то нужно взвесить еще 2 и потом 2.
252 и 253 между собой взвешивать не будем.

Докидывать ничего не нужно, если их будет 252 в стопке, то мы поделим поровну, если 253, то так же, просто останется одна монета.

Для безопасности платим из "чистой" стопки, тогда 84 делим на 28х4 и это никак не влияет

?

Log in

No account? Create an account