Если сумма быков и коров равна числу разрядов, все символы ответа найдены. А подсказка «быков 0, а все остальные коровы» говорит ещё и чётко: ни один символ не стоит на своём месте.
Сколько порядков остаётся?
Допустим, для 4 цифр попытка «0123» дала 0 быков и 4 коровы. Ответ — перестановка цифр 0, 1, 2, 3, причём ни одна цифра не стоит на прежнем месте. Если посчитать, таких порядков 9:
1032 1230 1302 2031 2301 2310 3012 3201 3210
Всего перестановок из 4 символов 24, но таких, где никто не остался на месте, только 9. Для каждого числа разрядов получается так (всё проверено перебором ответов):
| Разрядов | Всего перестановок | Никто не на своём месте |
|---|---|---|
| 3 | 6 | 2 |
| 4 | 24 | 9 |
| 5 | 120 | 44 |
| 6 | 720 | 265 |
| 7 | 5040 | 1854 |
Для 3 цифр, если «012» дало 0 быков и 3 коровы, ответ только один из двух: «120» или «201».
Как найти место среди 9 порядков для 4 цифр
Чтобы угадать среди 9 порядков, нужно так выбирать попытки, чтобы они хорошо делили варианты. Сравним две попытки.
- 1032 (один из 9 вариантов): делит варианты так: 1 вариант угадан, у 4 вариантов быков 2 и коров 2, у 4 вариантов быков 0 и коров 4.
- 1034 (добавили 4, специально чтобы промахнуться): у 1 варианта быков 3, у 2 вариантов быков 2 и коров 1, у 2 вариантов быков 1 и коров 2, у 4 вариантов быков 0 и коров 3.
В обоих случаях в худшем случае остаётся 4 варианта. Но 1032 может сразу оказаться ответом, поэтому она выгоднее, чем 1034. Вот так, когда вариантов осталось мало, выбирай из вариантов тот ряд, который лучше всего их разделяет.
В этом примере 1032 дала 0 быков и 4 коровы, и остались 4 варианта: 2301, 2310, 3201, 3210. Следующая попытка 3210 снова дала 0 быков и 4 коровы, остался только 2301, и на 4-й попытке ответ угадан. 3210 делит 4 варианта так: 1 угадан, у 2 вариантов быков 2 и коров 2, у 1 варианта быков 0 и коров 4.
Когда сумма набралась, думай о местах
Как только сумма быков и коров сравнялась с числом разрядов, искать символы больше не нужно. Остаётся думать только о местах.
- Символ с 0 быков не стоит на этом месте. Выпиши по каждой попытке, какой символ на каком месте стоять не может, и останутся только возможные места.
- Поменяй местами два символа и сравни. Если поменять только два символа, число быков вырастет на 2, уменьшится на 2 или не изменится, и по этому видно, где стоят эти два символа.
Когда быков 0 у всех, ты уже знаешь, что ни один символ не на своём месте, поэтому порядков остаётся гораздо меньше. Подсказка «все коровы» — приятная: символы собраны, да ещё и про места кое-что известно.
Остальные приёмы собраны в статье Советы по «Быкам и коровам».
