Thursday, 17 March 2016

Разбор решений задачки о 24 монетах

С неделю назад я опубликовал в ФБ задачку, и получил ряд решений. Вот о них и расскажу.

Вот условие:

Есть 12 золотых и 12 серебряных монет. Одна из монет фальшивая (неизвестно, золотая или серебряная). Настоящие золотые монеты весят одинаково; настоящие серебряные тоже, но неизвестно, какие тяжелее (золотые или серебряные). Фальшивая золотая монета легче настоящих золотых, а фальшивая серебряная тяжелее серебряных. По виду можно сказать, золотая монета или серебряная, но нельзя сказать, настоящая или фальшивая. Сколько нужно взвешиваний, чтобы заведомо найти фальшивую монету?
Весы чашечные коромысла.


Использую вот эти оценки, находим нижнюю границу шагов: 3 шага. Неизвестно, как много сложностей добавляет дополнительные ограничения и новшества. Так, что если удастся за 3 шага, то это вин!

1) Я эту задачку решил так.
Монеты для шага 1: делим монеты на 3 кучки, в каждой по 4 золотых и серебряных. Взвешиваем любые две, назовем их кучка 1 и кучка 2.
Интерпретация взвешивания шага 1: если кучки равны, то фальшивка в третей кучке
(4 золотых и 4 серебряных). Если не равны, то фальшивка либо в золотых монетах верхней чашки, либо в серебряных нижней чашки, то есть в этом случае мы можем сформировать кучку из 8 монет(4 золотых и 4 серебряных), где гарантированно будет фальшивка.

Монеты для шага 2: Берем нашу кучку с фальшивкой. Делим ее на три кучки: 2 золотых и серебряная, 
2 золотых и серебряная и 2 серебряных. Взвешиваем кучку 1 и кучку 2.
Интерпретация взвешивания шага 2: если кучки равны, то фальшивка в третей кучке
(2 серебряных). Если не равны, то фальшивка либо в золотых монетах верхней чашки, либо серебряная нижней чашки, то есть в этом случае мы можем сформировать кучку из 3 монет(2 золотых и серебряная), где гарантированно будет фальшивка.

Монеты для шага 3: если у нас после второго шага осталась кучка из двух серебряных, то все просто, просто будут две кучки по одной монете. Если у нас кучка из трех монет, (2 золотых и серебряная), то будем взвешивать по золотой монете, а серебряную отложим.
Интерпретация взвешивания шага 3:  если взвешиваем серебро, то фальшивка в нижней чашке. Если взвешиваем золото и чашки равны, то фальшивка из серебра, иначе фальшивка в верхней чашке.

2) Сергей Фролов предложил следующий алгоритм:
Монеты для шага 1: делим монеты на 3 кучки, в каждой по 4 золотых и серебряных. Взвешиваем любые две, назовем их кучка 1 и кучка 2.
Интерпретация взвешивания шага 1: если кучки равны, то фальшивка в третей кучке
(4 золотых и 4 серебряных). Если не равны, то фальшивка либо в золотых монетах верхней чашки, либо в серебряных нижней чашки, то есть в этом случае мы можем сформировать кучку из 8 монет(4 золотых и 4 серебряных), где гарантированно будет фальшивка.

Монеты для шага 2: Берем нашу кучку с фальшивкой. Делим ее на две кучки: 3 золотых и 3 серебряных и 1
 золотая и серебряная. Также выделяем кучку из 3 золотых и 3 серебряных, которые заведомо настоящие. Взвешиваем кучку 1 и кучку 3.
Интерпретация взвешивания шага 2: если кучки равны, то фальшивка в второй кучке
(золотая и серебряная). Если не равны, то фальшивка либо в золотых монетах первой кучки, если чашка вверху, либо в серебряных первой кучки, если чашка внизу.

Монеты для шага 3: если у нас после второго шага осталась кучка из двух монет, то просто взвесим одну из монет с заведомо не фальшивой монетой того же материала. Если у нас кучка из трех монет, то будем взвешивать две монеты из этой кучки.
Интерпретация взвешивания шага 3:  в первом случае, при равенстве чашек, то фальшивкой будет оставшиеся монета, при неравенстве, ее можно будет определить исходя из металла, который мы взвешивали. Во втором случае, если чашки равны, то фальшивкой будет оставшиеся монета, при неравенстве, ее можно будет определить исходя из металла, который мы взвешивали.

3) Способ предложил Руслан Батыров.
Поделим монеты на 12 кучек, по одной золотой и серебряной. Далее решаем задачу, следующим образом:

В качестве ответа мы получим, кучку и ее маркировку: Л или Т. Если Л, то фальшивка золотая, если Т, то серебряная.

4) Способ предложил Руслан Батыров.
Поделим монеты на 12 кучек, по одной золотой и серебряной. Теперь решаем задачу методом Дайсона.

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

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

Есть ли еще способы решить эту задачку? Какой из способов вам кажется наиболее понятным?

Wednesday, 9 March 2016

Котормочу бот!

Накидал тут быстренько бота для Telegram для перевода с кыргызского на русский или наоборот. Встречайте Котормочу(@kotormochubot)!!!

Реализация простейшая, переводы беру с http://tili.kg. Хотел использовать Google Translate API, но оказалось, что он полностью платный. Подсказывают, что можно посмотреть в сторону PhantomJS и таким образом использовать веб-версию переводчик...или может кто нибудь захочет проспонсировать API %)



А может быть tili.kg захочет похостить сервис и дать прямой API, а то на GAE маленькие квоты, а писать распределенный сервис и искать словарь немного лень %))

Кстати, исходники тут: https://github.com/frydaykg/kotormochu-bot
Может кто-то захочет что-то исправить или улучшить. Жду форков и пулл реквестов. Или хотя бы критики и пожеланий)