Задача №111553. Числа в Зазеркалье
Назовем N-значное число, не содержащее ведущих незначащих нулей, числом из Зазеркалья, если это число можно написать на бумаге, изображая цифры так, как их пишут на электронных табло (см. рисунок), а потом поднести к этому изображению зеркало и увидеть в нем то же самое число. При этом все цифры полностью мы должны увидеть именно в зеркале, в неискаженном виде, а число целиком прочитать, как обычно, слева направо. Единственное, что может выглядеть по-другому, — это расстояние между цифрами числа.
Вася выписал на бумаге некоторые цифры одного из N-значных чисел. Позиции этих цифр в числе он также зафиксировал. Помогите ему определить, сколько различных чисел из Зазеркалья он может записать, заполняя всеми допустимыми способами остальные позиции.
В первой строке входных данных записано одно натуральное число N (1 ≤ N ≤ 30). Во второй строке находятся ровно N символов, часть из которых цифры, а часть — символы ‘*’, обозначающие свободные места. Строка заканчивается символом перевода строки.
Выведите количество N-значных чисел из Зазеркалья, которые можно получить, заполняя свободные места цифрами.
Условие этой задачи нужно понять буквально.
А для того чтобы проверить ответ к первому примеру, можно перебрать все варианты на бумаге и подносить к ним зеркало, пока не станет понятно, какие 3 варианта являются подходящими.
Тесты к этой задаче состоят из четырех групп.
- Тесты 1-2. Тесты из условия, оцениваются в ноль баллов.
- Тесты 3-26. В тестах этой группы N не превосходит 4. Эта группа оценивается в 30 баллов.
- Тесты 27-32. В тестах этой группы N не превосходит 8. Эта группа оценивается в 30 баллов.
- Тесты 33-40. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из второй и третьей групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
2 *0
3
4 1*7*
0