C - 節約生活 Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

　高橋君は有料の衛星放送を見ようとしています。有料衛星放送はお金を払わないと見ることが出来ませんが、高橋君はその契約を行なっていません。
　しかし、有料衛星放送はどのような内容を放送しているか視聴者がわかるように、無料でも視聴可能な時間が定期的に存在し、視聴可能な時間とできない時間が交互に繰り返されます。このような視聴可能な時間とそうでない時間を視聴パターンと呼ぶことにします。
　視聴パターンは o と x から成り立っており、図 1 で示すように視聴可能な時間を o の個数、視聴できない時間を x の個数で表しています。
図 1:視聴パターンの例(入力は10文字以下なので、この入力はテストに存在しません)
　一度テレビを点けると途切れることなくこの視聴パターンが繰り返される。また、テレビは一度点けると消すことはできません。
　高橋君は複数のテレビを点けるタイミングをずらして並行して利用することで、無料でも常にいずれかのテレビで視聴ができる方法を思いつきました。
　例えば図 1 の視聴パターンの場合は図 2 で示すように 5 分後にもう 1 台テレビを点ければ常に視聴ができます。
図 2:2 台のテレビで常に視聴する例
　その場合高橋君が用意しなければいけない最低限のテレビの台数を答えなさい。
　なお、必要なテレビを全て点け終えるまでの間には視聴できない時間があっても構いませんが、全てのテレビを点けてからは常にいずれかのテレビで視聴ができないといけません。

入力

入力は以下の形式で標準入力から与えられる。 
c_0c_1‥‥c_{N-1}
  • 入力は 1 行のみで視聴パターンを表す長さ N(1≦N≦10) の文字列が与えられる。
    • 視聴パターンは o と x から成り、i+1(0≦i≦N-1) 番目の文字 c_i はテレビを点けてから i 分から i+1 分の間はテレビが以下の状態であることを意味する。
      • o:視聴可能である。
      • x:視聴できない。
    • 視聴パターンは少なくとも 1 つの o を含む。
    • テレビは最初にテレビをつけてから j(j : 正の整数) 分後にのみ点けることができる。

出力

常にいずれかのテレビが視聴可能であるために用意しなければいけないテレビの台数の最小値を標準出力に 1 行で出力せよ。
必要なテレビを全て点け終えるまでの間は視聴できない時間があっても構わないが、全てのテレビを点けてからは常にいずれかのテレビが視聴できないといけない。
なお、最後には改行を出力せよ。

入力例 1

oxoxx

出力例 1

3
  • 以下の図のタイミングでテレビを点けることで 3 台のテレビで常に視聴ができます。

入力例 2

oxxxxoooo

出力例 2

2
  • 1 台目のテレビを点けてから 4 分目に 2 台目のテレビを点けることで 1 分目から 5 分目直前までは視聴が不可能だが、5 分目以降は視聴が可能になります。

入力例 3

ox

出力例 3

2
  • 1 台目のテレビを点けてから 1 分後に 2 台目のテレビを点けることで 2 台で視聴可能です。

入力例 4

o

出力例 4

1
  • 視聴パターンに視聴できない時間が含まれない場合もあります。

入力例 5

xxxoxo

出力例 5

4

Source Name

ARC 007