눈먼 플리브

플리브는 미래를 예측하는 환상의 생물이다. 유전 알고리즘을 시연할 때 플리브가 자주 쓰인다. 이 문제에서는 외부 세계에서 아무 정보도 받지 않고 미래를 예측하는 '눈먼' 플리브의 성질을 살펴본다.

미래를 0과 1로 이루어진 문자열 $w$로 나타내고, 이 문자열을 끝없이 이어 붙인 무한 문자열을 $w^*$라고 하자. 예를 들어 $w = 010011$이면 $w^*=010011010011010011...$이다. 눈먼 플리브는 전이할 때마다 기호를 출력하는 결정적 유한 오토마타다.

눈먼 플리브는 상태가 $n$개이고, 각 상태에서 0으로 표시된 전이와 1로 표시된 전이가 하나씩 나간다. 전이는 세 원소의 묶음 $\langle m, p, s \rangle$로 나타낸다. 여기서 $m$은 전이에 붙은 기호, $p$는 전이에서 출력되는 기호, $s$는 전이 후의 상태다.

처음에 플리브는 원하는 기호 하나를 출력하고 상태 1로 이동한다. 이후 마지막으로 출력한 기호를 $c$라 하면, 플리브는 $c$와 같은 기호가 붙은 전이를 따라가며 그 전이에 붙은 기호를 출력한다. 이 과정이 무한히 계속된다.

$z$를 플리브가 출력한 무한 문자열이라 하자. $e(k)$는 처음 $k$개 위치 중 $z$와 $w^*$의 기호가 같은 위치의 개수다. $k$가 커지면 $e(k)/k$는 어떤 수 $P$에 한없이 가까워진다. 이 $P$를 플리브의 예측 능력이라 한다. 예측 능력이 높을수록 좋은 플리브다.

예를 들어 어떤 $w$에 대해서도 상태가 $n$개이고 예측 능력이 1.0인 플리브가 있다는 것은 분명하다. $n$은 $w$의 길이다. 이 플리브의 상태는 지금까지 출력된 $w$의 위치에 대응하며, 다음 기호를 언제나 맞힌다.

주어진 단어 $w$에 대해, $k$를 1부터 $w$의 길이까지 바꿔 가며 상태가 $k$개이고 예측 능력이 최대인 플리브를 만들어라.

입력 파일에는 단어 $w$가 하나 들어 있다. $w$의 길이는 1 이상 200 이하이며, $w$는 0과 1로만 이루어져 있다.

$k$를 1부터 $w$의 길이까지 바꿔 가며, 상태가 $k$개인 블라인드 플리브가 가질 수 있는 최대 예측 능력을 한 줄에 하나씩 출력한다.