ВКОШП: ВКОШП 2020

В Берляндском Биологическом Университете (ББУ) занимаются изучением бактерий. Известно, что поведение бактерии определяется строением ее ДНК. В этой задаче будем считать, что ДНК бактерии — это строка, состоящая из нулей и единиц.

Недавно ученые ББУ открыли новый вид бактерий, основная особенность которого заключается в том, что при делении клетки ее ДНК не реплицируется, а также делится пополам. А именно, пусть ДНК исходной клетки задается некоторой строкой \(S=s_1s_2\ldots s_k\) четной длины \(k\) (\(s_i\) обозначет \(i\)-й символ строки \(S\) и равен либо \(0\), либо \(1\)). Тогда в результате деления будут получены клетки с ДНК, равными \(s_1s_2\ldots s_{\frac{k}{2}}\) и \(s_{\frac{k}{2}+1}\ldots s_{k-1}s_k\), соответственно.

Для исследования ученые планируют взять бактерию, ДНК которой будет иметь длину \(2^n\). Исследование состоит из \(n+1\) шага, в конце каждого из которых, кроме последнего, каждая имеющаяся в данный момент бактерия делится. Так, на первом шаге будет всего одна бактерия с ДНК длиной \(2^n\), на втором — две бактерии с ДНК с длинами \(2^{n-1}\) каждая и так далее. Наконец, на \(n+1\) шаге будет \(2^n\) бактерий, ДНК каждой из которых будет состоять лишь из одного символа.

Разумеется, изучать бактерии с одинаковыми ДНК неинтересно. Определите, какой должна быть ДНК у первой бактерии, чтобы в ходе исследования было получено как можно больше различных ДНК.