← 返回题目列表

AtCoder · dwango2015_prelims_2

B. Niconico 字符串

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

問題文

0 到 9 中的一串数字 S 被给予。

一个字符串 X ,X="25" 或 上面写着字符 X="2525" 或 上面写着字符 X="252525" ...等等。 当字符串由多次重复 "25" 组成时,X 据说是一个微笑字符串。 例如 "25" 呀 "25252525" 是一个微笑字符串,"123" 呀 "225" 不是微笑字符串。

你的工作是创建一个字符串 对于 S ,答案是有多少种方法可以提取构成笑脸字符串的连续子串。 即使字符串相同,如果提取位置不同,也会单独统计。


入力

输入将以以下格式从标准输入给出。

S
  • 1 行包含字符串 S 给出。S的长度是 1 以上 100,000 下面。另外,S 中的每个字符是 仅由数字 0 到 9 组成。

部分点

这个问题有部分要点。 如果您正确回答所有

N≦2000 的数据集 如果您正确回答 1 , 您将获得30 积分。 如果数据集 2 中的所有答案都正确且没有附加约束,那么除了上述数据集之外, 获得 70 分,总体 您将获得 100 积分。 输出从

出力

1 行包含字符串 S 中提取形成笑脸字符串的连续子串的方法有多少种。

请注意,如果忘记行尾换行符,答案将被判断为不正确。


入力例1

2525

出力例1

3

S="2525"就是这种情况。子串是 提取方法为 "25" 取出来的方法是 2 街道,"2525" 取出来的方法是 1 方法有好几种,总共 3 输出街道。


入力例2

1251251252525

出力例2

8

入力例3

25225

出力例3

2

入力例4

252252252252252252

出力例4

6

入力例5

20061212

出力例5

0