← 返回题目列表

AtCoder · code_formula_2014_final_e

E. ab 字符串

中文机器翻译题面 查看原题

問題文

考虑以下递归公式。 当

  • 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

请注意,可能有多个解决方案。