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

  • 1+12 ответов про То Самое.

    Итак, мои версии ответов на вопрос "как попасть на Северный (и Южный) полюс". Самый простой и самый дешёвый способ -> C1: купить билет на…

  • 2+15 вопросов про То Самое.

    Прежде чем бежать по рассказам дальше, я сделаю запятую. Вернее будет сказать... уже сделал – она чуть раньше по тексту поставлена. Я бы даже выделил…

  • В условиях стабильного климата.

    Здесь немного ветрено, но в целом климат стабильный и уверенный в себе, что не может не радовать. Приятно осознавать, что ты здесь хозяин себе.…


Думаю, что максимум вынести можно 2010 или 2011 золотых монет + 1 фальшивая.

Определять нужно не "какая из них фальшивая, а "какие 5 из них точно настоящие"
:-)

Обоснуйте - как вынести 2010 или 2011 без риска для жизни?

Взвешиваем 5 монет и ещё 5 монет.

1) Если они равны, то любую из кучек можно отдать охраннику. Итого результат: 2018 - 1 за взвешивание - 5 охраннику - 1 фальшивая = 2012

2) Если они не равны, то берём 5 монет из оставшихся и выплачиваем ими взятку. Результат тоже 2012

если не равны, то отдавать надо 6, но ход ваших мыслей мне нравится :)

При очень большом везении - 2006 и одна фальшивка.

Первое взвешивание - в остатке 1008 - 2018/2-1
Второе - в остатке 502, одну монету придется отложить до взвешивания. И если она окажется фальшивкой, то следующее деление оставит нам равновес по 251, одну отдаем за взвешивание, пять за выход.
Итого 1008+502+250+251-5

оставит нам равновес по 251

ecolimp

2017-12-15 07:41 (UTC)


а если равновеса не будет? Нет решения!

Так и знал. На..ли с зарплатой!

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

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ти монет есть фальшивка?

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.

А сколько стоит дать "на лапу" тем, кто ищет фальшивки в багаже? У них же есть готовое решение!

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

Чтобы найти фальшивку, нужно 8 взвешиваний. Итого: 8 за весы, 5 взятка, 1 фальшивка, остаётся 2004 монеты.

В условии, однако, не сказано, что за весы нельзя заплатить фальшивкой. Тогда последнее взвешивание не нужно -- оставшиеся после 7-го взвешивания монеты, среди которых фальшивка, отдаём за весы. Итого 2006 монет.

Можно сэкономить ещё одно взвешивание. После шестого взвешивания, остаётся не более 9 монет. Платим 6 за весы, 3 сомнительных монеты проглатываем (чтобы не нашли в багаже). Итого 2007 монет, но фальшивка может быть среди них.

> Чтобы найти фальшивку, нужно 8 взвешиваний.

Не верю.
Минимум 9.

Сыну скинул задачу вашу.
Вот его ответ:

Предисловие.
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-я.

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

А, поправка. Если после первых двух взвешиваний три большие кучи равны, то выделить фальшивку из двух монет можно за одно взвешивание. Но все равно смысла нет - ту же самую монету и заплатим, так что проще выкинуть.

2018/2=1009 -1 =1008 одна чистая монета есть
1008/2=504
504/2=252
252/2=136
136/2=63-1=62 вторая чистая
62/2=31-1=30 третья чистая монета
30/2=15-1=14 четвертая чистая
14/2=7 -1=6 пятая чистая
6 на три кучки по две монеты и два контрольных взвешивания
Мы рассчитываемся с охранником чистыми монетами
Берем две монеты из "неправильной" чашки весов, добавляем , расплачиваемся за 10 взвешиваний и идем домой с 2003 монетами. В условии не было указано на расчет за взвешивание правильными монетами


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

> 2018/2=1009 -1 =1008 одна чистая монета есть

Еще раз: тяжелее или легче фальшивка неизвестно. Взвешивание 2018 монет пополам не даёт вообще никакой информации. Ясен пень, что одна половина будет тяжелее другой. И что?

?

Log in

No account? Create an account