Загадка про банки с таблетками
Обновлено: 22.11.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 грамма.
чё? я не вкурил
что значит разное количество? разное на 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 грамма;
- все банки выглядят одинаково внутри и снаружи;
- есть очень точные весы, на которых можно взвешивать что угодно в любом количестве.
Как за одно взвешивание найти банку с токсичными таблетками?
У нас в распоряжении есть только одно взвешивание. Это значит, что надо найти такой алгоритм, который сразу даст точный и однозначный ответ.
Если мы положим на весы одну нормальную таблетку, они покажут 1 грамм, а если испорченную — 1,1 грамма. Давайте посмотрим, что будет, если из каждой банки мы возьмём по одной таблетке и положим их все на весы:
(19 × 1) + (1 × 1,1) = 20,1.
Отсюда можно сделать два важных вывода:
- нельзя брать одинаковое количество таблеток из каждой банки, потому что тогда мы не отличим банки друг от друга;
- одна испорченная таблетка даёт лишний вес в 0,1 грамма.
Раз нужно из каждой банки брать какое-то своё количество таблеток, попробуем сделать так:
- из первой банки возьмём 1 таблетку;
- из второй банки — 2 таблетки;
- …
- из двадцатой банки — 20 таблеток.
По этой схеме у нас получится всего:
1 + 2 + 3 + . + 19 + 20 = 210 таблеток.
Теперь нам нужно учесть лишний вес в 0,1 грамма, который даёт каждая испорченная таблетка. Получается, что если у нас будет одна такая, то лишний вес составит 0,1 грамма, если две — 0,2 грамма и так далее. Зная общее количество лишнего веса, можно будет вычислить количество испорченных таблеток:
количество испорченных таблеток = лишний вес / 0,1.
Осталось найти лишний вес. Для этого возьмём 210 таблеток по нашей схеме, взвесим их, а от результата отнимем 210 — вес всех таблеток, если бы они были нормальными и весили по одному грамму каждая.
На подумать
Чтобы решить эту задачу, нам нужен был циклический алгоритм. В первой части он делил оставшуюся пробу на порции по числу мышей, во второй снимал пробу и в третьей проверял, в какой пробе было лекарство. Кайф алгоритма в том, что его скорость исполнения нелинейна. Что это значит?
Допустим, у нас был бы бесконечный запас времени и те же 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, чтобы узнать номер отравленной банки:
Как видите, такой способ действительно позволяет за одно взвешивание найти нужную банку с таблетками.
Читайте также: