/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
文字列 t について、t の長さが 2 以上であり、かつ t の中の文字のうち過半数が同じ文字であるとき、t をアンバランスであると呼ぶことにします。例えば、voodoo や melee はアンバランスであり、noon や a はアンバランスではありません。
小文字のアルファベットからなる文字列 s が与えられます。s にアンバランスな (連続する) 部分文字列が存在するか判定してください。存在する場合は、s の中でそのような部分文字列が存在する位置を一つ示してください。
制約
- 2 ≦ |s| ≦ 10^5
- s は小文字のアルファベットのみからなる。
部分点
- 2 ≦ |s| ≦ 100 を満たすデータセットに正解した場合は、200 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
s
出力
s にアンバランスな部分文字列が存在しない場合は、-1 -1 と出力せよ。
s にアンバランスな部分文字列が存在する場合は、そのような部分文字列の一つを s_a s_{a+1} ... s_{b} (1 ≦ a < b ≦ |s|) として、a b と出力せよ。そのような部分文字列が複数存在する場合は、いずれも正解とみなされる。
入力例 1
needed
出力例 1
2 5
文字列 s_2 s_3 s_4 s_5 = eede はアンバランスな文字列です。他にもアンバランスな部分文字列は存在し、例えば 2 6 と出力しても正解となります。
入力例 2
atcoder
出力例 2
-1 -1
文字列 atcoder はアンバランスな部分文字列を持ちません。
Score : 400 points
Problem Statement
Given a string t, we will call it unbalanced if and only if the length of t is at least 2, and more than half of the letters in t are the same. For example, both voodoo and melee are unbalanced, while neither noon nor a is.
You are given a string s consisting of lowercase letters. Determine if there exists a (contiguous) substring of s that is unbalanced. If the answer is positive, show a position where such a substring occurs in s.
Constraints
- 2 ≦ |s| ≦ 10^5
- s consists of lowercase letters.
Partial Score
- 200 points will be awarded for passing the test set satisfying 2 ≦ N ≦ 100.
Input
The input is given from Standard Input in the following format:
s
Output
If there exists no unbalanced substring of s, print -1 -1.
If there exists an unbalanced substring of s, let one such substring be s_a s_{a+1} ... s_{b} (1 ≦ a < b ≦ |s|), and print a b. If there exists more than one such substring, any of them will be accepted.
Sample Input 1
needed
Sample Output 1
2 5
The string s_2 s_3 s_4 s_5 = eede is unbalanced. There are also other unbalanced substrings. For example, the output 2 6 will also be accepted.
Sample Input 2
atcoder
Sample Output 2
-1 -1
The string atcoder contains no unbalanced substring.