Code Formula 2014 本選

E - ab文字列


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB

問題文

以下のような漸化式を考えます。

  • F_{1,0} = b
  • F_{2,0} = a
  • n≧3 かつ 0≦k<2^{n-2} かつ k が偶数のとき、F_{n,k} = F_{n-1,floor(k/2)} + F_{n-2,floor(k/4)}
  • n≧3 かつ 0≦k<2^{n-2} かつ k が奇数のとき、F_{n,k} = F_{n-2,floor(k/4)} + F_{n-1,floor(k/2)}

以上の漸化式で定義されない F_{n,k} に関しては、考慮しないものとします。

文字列 S が与えられます。この文字列は、F_{p,q} の形で表せることが解っています。

S = F_{p,q} となる p,q のうち、1 つを出力してください。

ただし、floor(n) は、n の床関数とします。


入力

入力は以下の形式で標準入力から与えられる。

S
  • 1 行目には、文字列 S (1 ≦ |S| ≦ 20000) が与えられる。

出力

S = F_{p,q} となる p,q のうち、1 つを、スペース区切りで出力せよ。出力の末尾には改行をいれること。


入力例1

babaa

出力例1

5 5
  • F_{1,0} = b
  • F_{2,0} = a
  • F_{3,1} = F_{1,0} + F_{2,0} = ba
  • F_{4,2} = F_{3,1} + F_{2,0} = baa
  • F_{5,5} = F_{3,1} + F_{4,2} = babaa

となるため、p=5, q=5 が、求める答えの 1 つとなります。


入力例2

aababaabaababaabaababaababaabaabab

出力例2

9 44

解は複数ある場合もあることに注意してください。


Source name

Code Formula 2014 本戦

Submit提出する