Шаблон-палиндром
(Время: 1 сек. Память: 16 Мб Сложность: 19%)
Шаблоном размера N назовем строку длины N, каждый из символов которой входит в множество {0, 1, ?}. Шаблоны преобразуются в строки из нулей и единиц по следующим правилам:
- символы «0» и «1» могут быть преобразованы только сами в себя;
- символ «?» может быть преобразован либо в «0», либо в «1»;
Палиндромом называется строка, одинаково читающаяся с обеих сторон. Например, строка «abba» является палиндромом, а строка «abc» – нет.
Необходимо найти лексикографически наименьшую строку, являющуюся палиндромом, в которую может быть преобразован заданный шаблон P.
Входные данные
Входной файл INPUT.TXT содержит шаблон P длиной от 1 до 1000 символов.
Выходные данные
В выходной файл OUTPUT.TXT выведите искомый палиндром. Если такой палиндром получить невозможно, выведите «NO SOLUTION» (без кавычек).
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 01????0 | 0100010 |
| 2 | 010? | NO SOLUTION |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
