Странно, но в интернете её часто решают неправильно.
Мы любим тупые бессмысленные задачки, но ещё больше — когда их можно взломать и получить неожиданные результаты. Сегодня мы сломаем одну из таких задачек с помощью СИЛЫ КОДА.
Задача
В одном хлебном магазинчике есть 3 сорта булочек. На 10 рублей можно купить либо 1 булочку первого сорта, либо две булочки второго, либо 3 булочки третьего сорта. В магазин зашла группа детей, мальчиков и девочек поровну. Они сложились и получили 70 рублей. Всю сумму они потратили на покупку булочек так, чтобы всем досталось поровну — и по булочкам, и по деньгам.
Сколько было куплено булочек и каких сортов, если ни одна из булочек не была поделена на части?
Короткое решение из интернета
Любопытно, что нигде не приводится сам ход решения, а есть только ответ: в магазин зашли 3 мальчика и 3 девочки и купили по 2 булочки 3-го сорта и по 1 булочке 2-го сорта.
Но это скучно и тупо: просто узнать ответ. Как мы его получили?
Пошаговое решение
Так как мальчиков и девочек зашло поровну, то их получилось чётное количество. Значит, детей могло быть 2, 4, 6, 8, 10 и так далее. Нужно проверить, получится ли разделить покупки на 70 рублей поровну между детьми в каждой группе.
2 человека: им нужно купить просто чётное количество любых одинаковых булочек в любой комбинации:
2 первого сорта (20 р.) и 10 второго сорта (50 р.)
2 первого сорта (20 р.), 2 второго сорта (10 р.) и 12 третьего сорта (40 р.)
2 первого сорта (20 р.), 6 второго сорта (30 р.) и 6 третьего сорта (20 р.)
4 первого сорта (40 р.) и 6 второго сорта (30 р.)
4 первого сорта (40 р.), 2 второго сорта (10 р.) и 6 третьего сорта (20 р.)
6 первого сорта (60 р.) и 2 второго сорта (10 р.)
14 второго сорта (70 р.)
10 второго сорта (50 р.) и 6 третьего сорта (20 р.)
6 второго сорта (30 р.) и 12 третьего сорта (40 р.)
2 второго сорта (10 р.) и 18 третьего сорта (60 р.)
Видно, что уже в группе из двух человек у нас 10 решений. Посмотрим, что будет дальше.
4 человека : условия меняются — нужно, чтобы количество булочек каждого сорта делилось на 4. Попробуем подобрать.
Булочек третьего сорта нам нужно 12, потому что 12 делится на 4, а другое количество таких булочек, которое тоже делится на 4, мы на 70 рублей не купим. Но мы тогда потратим на 12 булочек 40 рублей, и у нас остаётся 30. На эти деньги мы не сможем подобрать одинаковые булки так, чтобы их число делилось на 4. Значит, третьесортные булочки тут не участвуют.
Булочек второго сорта нам нужно 8 (40 рублей) или 4 (20 рублей). Но на оставшиеся 30 или 50 рублей мы можем купить только 3 или 5 булочек первого сорта, а это тоже не делится на 4. Значит, второй сорт тоже мимо.
Но на 70 рублей мы можем купить только 7 булок первого сорта, а это не делится на 4. Значит, детей было не четверо.
6 человек : то же самое — подбираем булочки так, чтобы они делились на 6, и начинаем снова с самых дешёвых.
Булочек третьего сорта нам нужно 6, 12 или 18. Если их будет 6 (20 р.), то у нас остаётся 50 р., а на них мы не сможем набрать булок первого и второго сорта так, чтобы каждое из них делилось на 6. Если булочек третьего сорта будет 12 (40 р.), то у нас остаётся 30 р. как раз на 6 булочек второго сорта. Получаем то самое решение, которое все приводят как единственно правильное:
12 третьего сорта (40 р.) и 6 второго сорта (30 р.)
Если у нас будет 18 булок третьего сорта (60 р.), то на оставшиеся 10 рублей мы купим только 1 или 2 булки, а это нас не устроит.
Допустим, булок третьего сорта нам не нужно, и тогда нам понадобится 6 булок второго сорта (30 р.) или 12 булок второго сорта (60 р.). Первый случай мы только что разобрали, а во втором на 10 рублей мы не сможем купить других одинаковых булок так, чтобы их число делилось на 6.
С булками первого сорта всё просто — 7 булок на 6 не делится.
Далее мы можем в той же логике перебирать все возможные комбинации булок и детей, начиная с самых дешёвых. У нас есть общий делитель (8, 10 и т. д.), понятный бюджет и цены. Просто берём и перебираем.
Стоп! Мы перебираем? А какого рожна мы перебираем вручную?
Программистское решение
Как только на горизонте появляется перебор, мы должны расчехлить ближайшую браузерную консоль и быстро наваять перебирающий скрипт.
Смысл будет такой:
- Мы по очереди перебираем все чётные количества детей, которые зашли в магазин.
- Перебираем все возможные покупки булочек.
- Если получившаяся сумма нас устраивает, то делаем проверку: если количество булочек каждого сорта без остатка делится на общее количество детей, то выводим это как ответ и продолжаем дальше, пока не закончится перебор.
Чтобы хоть как-то ограничить количество детей, которые придут в магазин, узнаем самое большое количество булочек, которое можно купить на 70 рублей. Если даже мы возьмём на все деньги 7 комплектов булочек третьего сорта, то это получится 21 булочка. Если делить по одной на каждого, получим 21 человек — это и будет верхняя граница цикла. Мы помним, что 21 — это нечётное число, но чётность мы проверим в другом месте.
Для перебора булочек будем считать комплекты, а не стоимость. Один комплект — 10 рублей, на который можно купить одну, две или три булочки своего сорта. Получается, что максимум на 70 рублей можно взять 7 комплектов — это и возьмём для границы перебора по количеству булочек.
Теперь у нас есть всё, что нужно для кода:
Если выполнить этот код в консоли браузера, то сразу увидим ответы — 2, 6 и 14 детей. Перебор — это сила.
Итого
Получается, что у задачи не одно правильное решение, как все говорят, а целых двенадцать: десять решений для двоих детей и по одному решению для шестерых и четырнадцати.