Загадка про банки с таблетками

Обновлено: 02.07.2024

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

Если мы положим на весы одну нормальную таблетку, они покажут 1 грамм, а если испорченную — 1,1 грамма. Давайте посмотрим, что будет, если из каждой банки мы возьмём по одной таблетке и положим их все на весы:

Отсюда можно сделать два важных вывода:

нельзя брать одинаковое количество таблеток из каждой банки, потому что тогда мы не отличим банки друг от друга;

одна испорченная таблетка даёт лишний вес в 0,1 грамма.

Раз нужно из каждой банки брать какое-то своё количество таблеток, попробуем сделать так:

из первой банки возьмём 1 таблетку;

из второй банки — 2 таблетки;

из двадцатой банки — 20 таблеток.

По этой схеме у нас получится всего:

1 + 2 + 3 + . + 19 + 20 = 210 таблеток.

Теперь нам нужно учесть лишний вес в 0,1 грамма, который даёт каждая испорченная таблетка. Получается, что если у нас будет одна такая, то лишний вес составит 0,1 грамма, если две — 0,2 грамма и так далее. Зная общее количество лишнего веса, можно будет вычислить количество испорченных таблеток:

количество испорченных таблеток = лишний вес / 0,1.

Осталось найти лишний вес. Для этого возьмём 210 таблеток по нашей схеме, взвесим их, а от результата отнимем 210 — вес всех таблеток, если бы они были нормальными и весили по одному грамму каждая.

Ps. Хз правильно или нет , в интернете спиздил ответ

раскрыть ветку 10 8 месяцев назад

Ps. Хз правильно или нет , в интернете спиздил ответ

А я уж подумал "Нихуя ты крутан".)) раскрыть ветку 1 8 месяцев назад

8 месяцев назад

Если таблеток в каждой банке сторого определенное количество, то кидаешь все 20 банок на весы и снимаешь по одной.

При изъятии нужной банки вес уменьшиться нехарактерно

8 месяцев назад Вообще похоже на правду, но вскрытая банка с таблетками уже никому не нужна, да и таблеток может быть по 10 например в каждой баночке раскрыть ветку 2 8 месяцев назад

Боже , это задача на логику а не собесодование в аптеку )

8 месяцев назад

Может там экстази? Барыги толкнут))

8 месяцев назад

Кому нужны таблетки, которые ты трогал грязными пакшами?

раскрыть ветку 1 8 месяцев назад 8 месяцев назад

Да, ход решения правильный, только взвешивать надо 19 банок, а не 20

8 месяцев назад

хотел бы посмотреть на процесс взвешивания

8 месяцев назад Считается ли за одно взвешивание выкладывание на весы по одной баночке пока вес не прибавиться на 1.1 г.? раскрыть ветку 1 8 месяцев назад

Я тоже так подумал)

8 месяцев назад

легчайше.
из каждой банки берем разное количество таблеток.
далее смешиваем, и взвешиваем.
превышение массы делим на 0.1 грамм, получаем порядковый номер нужной банки.
если тяжелые в 1 - будет разница в 0.1 грамм. в 14 - 1.4 грамма.

раскрыть ветку 8 8 месяцев назад

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

можно объяснить другими словами?

раскрыть ветку 1 8 месяцев назад

а из моего поста не понятно? нумеруем каждую банку своим номером (от 1 до 20), берем из нее N таблеток, равное номеру.

8 месяцев назад

Если смешать то нихуя не выйдет

раскрыть ветку 5 8 месяцев назад

так ты не ешь, а взвешивай.

раскрыть ветку 4 8 месяцев назад

Если ты смешаешь-то не поймёшь из какой банки таблетки

раскрыть ветку 3 8 месяцев назад

пойму. у нас взято разное количество табл из каждой банки. по разнице общего веса установим нужный нам номер банки.

раскрыть ветку 2 8 месяцев назад

Так, ну я затупил, ок.

А что с кучей тогда делать? Онож не аккуратно(((

раскрыть ветку 1 8 месяцев назад

ну, можно их не вынимая из баночек взвешивать.

8 месяцев назад

Всё просто. Кладём на весы все двадцать банок. Убирая по одной следим за весом и вычисляем самую тяжёлую. Это одно взвешивание.

8 месяцев назад Что то мне кажется что с таким условием - никак. раскрыть ветку 1 8 месяцев назад

Во-во. Сразу вопросы - сколько таблеток в банках? Банки закрыты, открыты? Таблетки из них доставать можно? Если бы в условии это было прописано, было бы от чего плясать.

А так - хуйня, а не задача для ИТ.

8 месяцев назад 8 месяцев назад

легкотня а не задача - ставишь самую тяжелую банку на весы, а еще лучше прочитать этикетки на таблетки, но это для IT

раскрыть ветку 1 8 месяцев назад

точно, всегда нужно читать инструкцию)

8 месяцев назад

Проверить используемый тип. Если вещественный, то банка найдена.

8 месяцев назад Пересыпаем все в две банки и взвешиваем 8 месяцев назад

Тоже думаю, по одной на весы ставить, в задаче не сказано же что все банки разом на весы нужно поставить)

8 месяцев назад

По одной на весы ставь

8 месяцев назад

Попробовать, от тяжелых будет красочней

8 месяцев назад

Повторяю для особо тупых. Предположим , что 19 банок весят по 100 грамм каждая, а одна банка будет весить 110 грамм. Кладём все 20 банок на весы. Убирая по одной банке следим за показаниями весов. Когда весы покажут -110 грамм, это значит, что искомая банка у вас в руках. При этом процесс взвешивания не прекращается.

8 месяцев назад

У нас только одно взвешивание, а это значит, что придется одновременно взвешивать много таблеток. Фактически, мы должны одновременно взвесить 19 банок. Если мы пропустим две (или больше) банки, то не сможем их проверить. Не забывайте: только одно взвешивание!

Если мы возьмем одну таблетку из банки №1 и две таблетки из банки №2, то, что покажут весы? Результат зависит от веса таблеток. Если банка №1 содержит более тяжелые таблетки, то вес будет 3.1 г. Если с тяжелыми таблетками банка №2 — то 3.2 грамма. Подход к решению задачи найден.

Таким образом, номер банки можно узнать по простой формуле: (вес — 210) / 0.1. Если суммарный вес таблеток составляет 211.3 г, то тяжелые таблетки находились в банке №13.

Самопроверка

Прежде чем узнать решение, ответьте на такие вопросы:

Рационально ли выбирать какие-то отдельные бутылки из общей массы или нужно протестировать всё?
Есть ли в условии задачи лимит по количеству введённого лекарства?
Обязаны ли мы тестировать одну мышь только одной пробиркой? Можно ли использовать одно животное несколько раз или дать ему лекарства из нескольких пробирок?

Сначала кажется, что решить задачу нереально — мышей в 100 раз меньше, чем пробирок. Значит, нам нужно как-то научиться быстро сокращать количество элементов, которые нужно проверить.

Мы знаем, что даже капля яда убьёт мышь за сутки. Значит, если мы смешаем эту каплю с настоящим лекарством, яд тоже сработает. Воспользуемся этим так:

Разделим все пробирки на равные группы — по 100 пробирок в каждой.

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

Теперь у нас осталось 100 пробирок и девять мышей. Видите, мы за сутки сократили количество пробирок в 10 раз. Будем использовать этот же приём и дальше: делить сосуды на равные группы и делать смеси. На второй день разделим 100 пробирок на девять групп :

Восемь групп по 11 пробирок и одна группа из 12 пробирок.

Как видите, на совсем равные части поделить не получилось, но это не критично — задача всё равно решается. Теперь даём смеси мышам и через сутки смотрим, какое животное погибнет на этот раз.

Предположим самый сложный случай — яд был в смеси из 12 пробирок. У нас остаётся восемь мышей и 12 пробирок. Их тоже делим на восемь групп:

Четыре группы по две пробирки, и четыре группы по одной пробирке.

Снова даём вещество мышам и через сутки смотрим на результат. Если погибла особь, которая пила только из одной пробирки, — то она и была отравлена, а значит, мы нашли яд за три дня. Если эта мышь дегустировала смесь из двух сосудов, то на следующий день мы берём эти две пробирки, две мыши из тех, что остались, и обеим даём попробовать своё лекарство. Через сутки мы тоже узнаем, где был яд.

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

Ответ: максимум за четыре дня мы найдём сосуд с ядом.

Следующая загадка

Кавер-версия классической головоломки про 1 000 бутылок вина. Проверяет навыки алгоритмического мышления и очень распространена в ИТ-компаниях.

Так как чрезмерное употребление алкоголя вредит вашему здоровью, у нас будет задача про лекарства. Представьте, что вы работаете в лаборатории, которая ищет средство от смертельной болезни. Вам на испытание пришла партия из 1 000 пробирок с лекарством, которое нужно опробовать на людях. Проверка санкционирована Минздравом, у вас имеются все лицензии, но есть проблема. Вы узнаёте, что одну пробирку перепутали и по ошибке отправили вместо лекарства ядовитый реактив. Внешне он ничем не отличается от медикамента.

Вам нужно как можно скорее передать пробирки в больницы для запуска клинического теста, но отправлять отравленную пробирку нельзя: погибнут люди. Тесты всех пробирок займут месяцы, это очень долго. Но у вас есть лабораторные мыши. Вы знаете, что лекарство безвредно для них, а даже капля яда их убьёт за сутки. Но у вас только 10 мышей, а пробирок — 1 000.

Как определить, где яд, как можно быстрее? За какое время можно гарантированно найти пробирку с ядом?

Как это работает на практике

Например, у нас отравлена банка № 14. Раз мы берём из неё по схеме 14 таблеток, которые в сумме весят 14 × 1,1 = 15,4 грамма, то общий вес всех таблеток получится:

196 + 15,4 = 211,4 грамма.

Найдём лишний вес:

211,4 - 210 = 1,4 грамма.

Теперь разделим его на 0,1, чтобы узнать номер отравленной банки:

Как видите, такой способ действительно позволяет за одно взвешивание найти нужную банку с таблетками.

Следующая загадка

Как логика и ограничения помогают найти банку с отравленными таблетками.

Решим ещё одну задачу с тестированием чего-нибудь на мышах! Или на весах! Ещё одна задача из арсенала принимающих на работу и просто правильная гимнастика для мозга. Теперь условия такие:

есть 20 баночек с таблетками;
в одной из них отравленные таблетки;
таблетки из настоящих банок весят по 1 грамму;
таблетки из одной отравленной банки — 1,1 грамма;
все банки выглядят одинаково внутри и снаружи;
есть очень точные весы, на которых можно взвешивать что угодно в любом количестве.

Как за одно взвешивание найти банку с токсичными таблетками?

(19 × 1) + (1 × 1,1) = 20,1.

Отсюда можно сделать два важных вывода:

нельзя брать одинаковое количество таблеток из каждой банки, потому что тогда мы не отличим банки друг от друга;
одна испорченная таблетка даёт лишний вес в 0,1 грамма.

Раз нужно из каждой банки брать какое-то своё количество таблеток, попробуем сделать так:

из первой банки возьмём 1 таблетку;
из второй банки — 2 таблетки;
…
из двадцатой банки — 20 таблеток.

По этой схеме у нас получится всего:

1 + 2 + 3 + . + 19 + 20 = 210 таблеток.

количество испорченных таблеток = лишний вес / 0,1.

На подумать

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

Допустим, у нас был бы бесконечный запас времени и те же 10 мышей. Мы даём каждой по одной капле из одной из пробирок в день. Если яд в районе тридцатой пробирки, мы узнаем об этом через три дня. Если в 1 000-й, то для поиска отравы потребуется 100 дней. Если бы сосудов было 10 тысяч, то понадобилось бы 1 000 дней. Время исполнения алгоритма растёт линейно: чем больше пробирок, тем больше дней.

Теперь посмотрим на наш алгоритм: чтобы проверить 1 000 пробирок, нужно четыре дня. Если бы образцов было 10 тысяч, потребовалось бы пять дней. Возрастание числа пробирок в 10 раз увеличило время исполнения только на 25%.

Это и есть нелинейная скорость выполнения. Представьте, насколько такие алгоритмы более эффективны на больших массивах данных.

Следующая загадка

У нас в распоряжении есть только одно взвешивание. Это значит, что нам надо найти такой алгоритм, который сразу даст нам точный и однозначный ответ.
Если мы положим на весы одну нормальную таблетку, то они покажут 1 грамм, а если испорченную — 1,1 грамма. Давайте посмотрим, что будет, если из каждой банки мы возьмём по одной таблетке и положим их все на весы:
Показать полностью.

(19 * 1) + (1 * 1,1) = 20,1

Отсюда можно сделать 2 важных вывода:

нельзя брать одинаковое количество таблеток из каждой банки, потому что мы не отличим тогда банки друг от друга;

одна испорченная таблетка даёт лишний вес в 0,1 грамма.

Раз нужно из каждой банки брать какое-то своё количество таблеток, попробуем сделать так:

из первой банки возьмём 1 таблетку

из второй банки — 2 таблетки

из двадцатой банки — 20 таблеток

По этой схеме у нас получится всего:

1 + 2 + 3 + … + 19 + 20 = 210 таблеток.

Теперь нам нужно учесть то, что испорченные таблетки дают лишний вес в 0,1 грамма каждая. Получается, что если у нас будет одна такая таблетка, то лишний вес составит 0,1 грамма, если 2 таких таблетки — то 0,2 грамма, и так далее. Зная общее количество лишнего веса, можно будет вычислить количество испорченных таблеток:
количество испорченных таблеток = лишний вес / 0,1
Осталось найти лишний вес. Для этого возьмём 210 таблеток по нашей схеме, взвесим их, а от результата отнимем 210 — вес всех таблеток, если бы все они были нормальными и весили по одному грамму каждая.

Как это работает на практике

Например, у нас отравлена банка №14. Раз мы берём из неё по схеме 14 таблеток, которые в сумме весят 14 * 1,1 = 15,4 грамма, то общий вес всех таблеток получится:

196 + 15,4 = 211,4 грамма

Найдём лишний вес:

211,4 — 210 = 1,4 грамма.

Теперь разделим его на 0,1, чтобы узнать номер отравленной банки:

Как видите, такой способ действительно позволяет за одно взвешивание найти нужную банку с таблетками.

Читайте также: