2525文字列分解
题意翻译
题目:2525字符串分解
描述:dwango的社员niwango君正在开发一个叫做2525SNS的社交软件。 2525SNS是只能发送2525字符串的划时代的社交软件。(译者注:2525谐音“niconico”)
关于这个问题,2525字符串是由“25”多次重复表达的字符串。打个比方,25,2525,2525252525252525是2525字符串,空串以及2255,2552,252等字符串不是2525字符串。
首先,niwango君已经写出了好几个2525字符串,他想把一个字符串s分解成1个以上的子字符串,被分解的子字符串都要是2525字符串。
要达成这个条件,需要把字符串最小分解成几个部分?如果无论如何也无法分解(无解),输出-1.关于如何分解请参照输入样例1.
输入:一个字符串s。
输出:一个整数,表示被分解部分的数量的最小值。
题目描述
[problemUrl]: https://atcoder.jp/contests/dwacon2018-prelims/tasks/dwacon2018_prelims_b
dwango社員のニワンゴくんは2525SNSという新しいSNSを開発しています。 2525SNSは2525文字列のみ投稿可能な画期的なSNSです。
この問題において、`25` の $ 1 $ 回以上の繰り返しで表される文字列を2525文字列と呼びます。 例えば、`25`,`2525`,`2525252525252525` などは2525文字列ですが、空文字列や `2255`,`2552`,`252` などは2525文字列ではありません。
まず、ニワンゴくんは2525文字列をいくつか作ることにしました。 ニワンゴくんは手元にあった文字列 $ s $ を $ 1 $ つ以上の部分列に分解し、分解された部分列それぞれが2525文字列となるようにしたいです。
最小でいくつの部分列に分解すればこれを達成可能ですか?どのように分解しても達成不可能な場合は `-1` を出力してください。分解についてはサンプル $ 1 $ の説明も参照してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ s $
输出格式
答えを出力せよ。
输入输出样例
输入样例 #1
225525
输出样例 #1
2
输入样例 #2
52
输出样例 #2
-1
输入样例 #3
2255252252222555552522255255
输出样例 #3
5
输入样例 #4
25252
输出样例 #4
-1
说明
### 制約
- $ 1\ \leq\ |s|\ \leq\ 2{,}525 $
- $ s $ は `2` と `5` のみからなる
### Sample Explanation 1
\- $ 1 $ つの部分列に分解した場合、`225525` は2525文字列ではないため条件を満たしません。 - その他の分解としては例えば $ ( $`25`,`2525`$ ) $ となるような分解と $ ( $`25`,`25`,`25`$ ) $ となるような分解が考えられます。それぞれについて正しい分解の例とそうでない例を示します。各部分列内において、$ s $ における相対的な出現順序が守られるように分解する必要があることに注意してください。 - $ ( $`25`,`2525`$ ) $ となるように $ 2 $ つの部分列に分解することで、それぞれの部分列が2525文字列となるように分解できます。 !\[062c9a95edb82917811ef52962f98a3e.png\](https://img.atcoder.jp/dwacon2018-prelims/062c9a95edb82917811ef52962f98a3e.png)
### Sample Explanation 2
\- 分解方法は $ 2 $ 通りありますが、それぞれの部分列が2525文字列となるように分解することはできません。 - `5` と `2` に分解したのち、それぞれの順序を入れ替えて `25` を作ることは不可能なことに注意してください。