Скажем, что строка \(s\) имеет период \(k\), если \(s_i = s_{i + k}\) для всех \(i\) от \(1\) по \(|s| - k\) (\(|s|\) — это длина строки \(s\)), и \(k\) — минимальное положительное целое число с этим свойством.
Несколько примеров вычисления периода: для \(s\)=«0101» период равен \(k=2\), для \(s\)=«0000» период равен \(k=1\), для \(s\)=«010» период равен \(k=2\), для \(s\)=«0011» период равен \(k=4\).
Вам задана строка \(t\), состоящая только из 0 и 1, и вам нужно найти такую строку \(s\), что:
- Строка \(s\) состоит только из 0 и 1;
- Длина \(s\) не превосходит \(2 \cdot |t|\);
- Строка \(t\) является подпоследовательностью строки \(s\);
- Строка \(s\) имеет минимальный возможный период среди всех строк, удовлетворяющих условиям 1—3.
Напомним, что \(t\) является подпоследовательностью \(s\), если \(t\) можно получить из \(s\) путем удаления нуля или более элементов (любых) и не меняя порядок оставшихся элементов. Например, \(t\)=«011» — это подпоследовательность строки \(s\)=«10101».
Примечание
В первом и втором наборе \(s = t\), так как это уже одни из оптимальных решений. Периоды ответов равны \(1\) и \(2\), соответственно.
В третьем наборе, есть и другие более короткие ответы, но все в порядке, потому что не требуется минимизировать ответ \(s\). Строка \(s\) имеет период \(1\).