E - ab文字列
Editorial
/
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
以下のような漸化式を考えます。
- 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
解は複数ある場合もあることに注意してください。