← 返回题目列表

AtCoder · dwacon2018_prelims_b

B. 2525 字符串分解

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

配点 : 300 点

問題文

dwango公司的员工nisan先生正在开发一个名为2525SNS的新SNS。2525SNS是一个只允许发布2525字符串的划时代SNS。

在这个问题中,25 的 1 以回以上的反复表示的字符串称为2525字符串。例如,25,2525,2525252525252525 等是2525字符串,但空字符串和 2255,2552,252 等不是2525字符串。

首先,niwan先生决定制作几个2525字符串。niwan先生手头有的字符串 s 请计算 1 想要将其分割为至少个子序列,并且使分割后的每个子序列都是2525字符串。

要分解为最少几个子序列才能实现这一点呢?无论如何分解都无法实现的情况,请输出 -1 。关于分割,请参照示例 1 的说明。

制約

  • 1 \leq |s| \leq 2{,}525
  • s 是 2 和 将其放在 5 仅由

入力

输入将以以下形式通过标准输入给出。

s

出力

输出答案。


入力例 1

225525

出力例 1

2
  • 1 个子序列组成的情况下,225525 不是2525字符串,因此不满足条件。
  • 其他分割例如可以考虑分为 (25,2525) 或 (25,25,25) 。对于每种情况,分别给出正确分割的例子和不正确的例子。请注意,在各个子序列内,需要保持s 中的相对出现顺序。通过将其分解为
  • (25,2525) 的 2 个子序列,可以使每个子序列成为2525字符串。
062c9a95edb82917811ef52962f98a3e.png

入力例 2

52

出力例 2

-1
  • 分割方法有 2 种,但无法将其分割成每个子列都是2525字符串。
  • 5 和 将其放在 2 分割之后,更换每个部分的顺序 25 是不可能的,请注意。

入力例 3

2255252252222555552522255255

出力例 3

5

入力例 4

25252

出力例 4

-1