Поздравляю Петра Митричева с потрясающим результатом и победой! Сегодняшнее выступление Петра сильно подняло моё настроение, я теперь гораздо быстрее победю вирусную инфекцию.
Каждому из 14 квадратов надо присвоить какую-то цифру от 0 до 6, каждая цифра должна соответствовать паре квадратов. Сразу заметим, что если взять корректное решение и применить перестановку ко всем цифрам на поле, мы опять получим корректное решение. Следовательно, решение характеризуется разбиением 14 квадратов на пары. Если мы имеем такое разбиение, то по нему можно сгенерировать 7! решений. Возможных разбиений всего 13!! = 13·11·9·7·5·3 = 135135 . Первому квадрату соответствует один из 13-и, следующему без пары - 11, и.т.д. Сотню тысяч вариантов легко перебрать и проверить корректность.
С точностью до поворотов, всего конфигураций поля, которые имеют решения, около 6 тысяч. Наибольшее число решений - 22·7!.
Подколки:
1) Если не оптимизировать решение в 7! раз , можно получить TL. В комментариях уже указали что хватит оптимизации и в 7 раз.
2) Можно подумать что квадратики делятся на два класса - 7 квадратиков в которых есть доминошка дубль, и 7 в которых ее нету. Если говорить в терминах графов, 7 вершин со степенью 2, и 7 со степенью 4. Понятно, что две вершины степени 2 не могут соответствовть одной цифре, иначе получаем два дубля одной цифры. При таком делении достаточно перебрать 7! возможных соответствий вершин второго типа вершинам первого типа.
А теперь рассмотрим второй претест:
Дубль 4-4 поделен между двумя квадратиками. Имеем 6 вершин степени 2 и 8 степени 4. Challenge Succeeded.
Более того:
Здесь целых два дубля появляются на стыках квадратиков!
И бонус,одна из красивых конфигураций с несколькими дырками:
Очень жаль, но несвязных конфигураций c решениями не существует :(
А за что, кстати, эта задача стоит в три раза меньше, чем все остальные? Действительно ли средний член жюри Яндекс.Алгоритма решает+пишет+отлаживает её в три и более раза быстрее, чем остальные задачи раунда? Результаты показывают, что выгодно было если и решать её, то последней.
Да и вообще. Может быть, у всех с этим всё хорошо, но мне с некоторых пор на CodeForces удобнее начинать с задач C, D, E, чем с A или B.
Хм. Который сделал пять неверных посылок по вашей задаче...
Вообще, теперь есть мотивация потренироваться ещё, чтобы выйти на новый уровень, так же быстро решать алгоритмические задачи.
Спасибо за второй претест!
На самом деле можно найти количество "хороших" квадратов пусть их будет А (а не 7). И тогда перебрать все (14-A)!/27-A вариантов, ответ умножить на C из 7 по А и на А!.