東京工業大学プログラミングコンテスト2015

C - おおおかやま


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

okayama国の首都ookayamaでは、ookayamaの先頭に1個以上の任意の個数のoが付加された文字列のことを良い文字列と呼ぶ。

あなたの仕事は文字列Sを次のルールで処理するプログラムを書くことである。

  • 手順1. Sの部分文字列に良い文字列が存在するならば手順2へ、存在しないならば処理を終了する。
  • 手順2. 良い文字列であるようなSの部分文字列のうち、長さが最長のものを選びこれをTとして手順3へ。最長のものが複数ある場合は最も左側にあるものを選ぶ。
  • 手順3. Tooという部分文字列が存在するならば、そのうち最も左側にあるものをOへ置換して手順4へ、存在しないならば手順1へ。
  • 手順4. TOOという部分文字列が存在するならば、そのうち最も左側にあるものをoへ置換する。存在するかどうかにかかわらず手順3へ。

処理終了後のSを求めよ。この処理結果が何に用いられるかは機密情報であるため、あなたは知る必要はない。

ある文字列TSi (1 \leq i \leq |S|)文字目からj (i \leq j \leq |S|)文字目までを取り出したものであるとき、TSの部分文字列であると呼ぶ。ここで | S | は文字列Sの長さを表す。


入力

入力は以下の形式で標準入力から与えられる。

S

1 行目に処理すべき文字列S(1 \leq | S | \leq 100)が与えられる。Sは英小文字のみからなることが保証される。

出力

処理終了後のS1行に出力せよ。改行を忘れないこと。


入力例1

ooookayama

出力例1

okayama

文字列ooookayamaに対し、処理を行うと、以下のような順序で扱われる。

  1. 手順1においてSの部分文字列に良い文字列は存在する。
  2. 手順2において良い文字列であってSの部分文字列であるようなもののうち長さが最長のものは1番目のoから始まる部分文字列である、ooookayamaである。これをTとする。
  3. 手順3においてTに存在するooという部分文字列のうち、最も左側にあるものをOに置換する。TOookayamaとなる。
  4. 手順4においてTOOという部分文字列は存在しない。
  5. 手順3においてTに存在するooという部分文字列のうち、最も左側にあるものをOに置換する。TOOkayamaとなる。
  6. 手順4においてTに存在するOOという部分文字列のうち、最も左側にあるものをoに置換する。Tokayamaとなる。
  7. 手順3においてTooという部分文字列は存在しない。
  8. 手順1においてSokayamaである。Sの部分文字列に良い文字列は存在しない。処理を終了する。

入力例2

ooookayamaoooookayama

出力例2

okayamaOkayama

Sの部分文字列には、良い文字列が複数存在することもある。最長のものかつ最も左側にあるものから処理する必要があることに注意せよ。また、与えられる入力には英大文字は含まれないものの、答えや処理の過程には現れる可能性があることに注意せよ。


入力例3

okayama

出力例3

okayama

文字列okayamaの部分文字列には良い文字列は存在しない。


入力例4

ookayama

出力例4

ookayama

文字列ookayamaの部分文字列には良い文字列は存在しない。良い文字列とはookayamaの先頭に1個以上の任意の個数のoが付加された文字列のことであるためookayamaは条件を満たさない。


入力例5

ooookayamakenooooookayamashiookayama

出力例5

okayamakenOokayamashiookayama

Submit提出する