問題 B : (iwi)

20XX 年の今,G○○gle 社の世界的な支配により,人々のコミュニケーションは限られており, 例えば,自由に人と情報をやりとりすることは基本的に許されていない. 特に,過去にプログラミングコンテストで名を馳せた強豪たちは,危険と判断され, お互いバラバラにされ,密かに注意深く監視されているという.

自分も,そんな一人であった,ような気がする. しかし実は,自分は記憶を失ってしまっているのだ. 自分が何と名乗っていたか,それすらも思い出せない. 'i' とか 'w' とか括弧とかを使っていた気がするが, それっぽいものを書きだしてみても,しっくりこない. そういえば,今思い出したことには,左右に線対称だった気がするのだ.

問題

'i', 'w', '(', ')' からなる文字列が与えられた時, 一部の文字を他の文字に置き換えて,'i', 'w', '(', ')' からなる左右に線対称な文字列にしたい. 文字の追加や削除は許さず,1 文字を別の 1 文字に変える操作のみを行うことにする. 少なくとも何文字置き換えなければならないかを出力するプログラムを作成せよ.

ここで用いる左右に線対称の定義は,以下とする.

  1. 以下の文字列は左右に線対称.
  • 空文字列
  • "i"
  • "w"
  1. 文字列 x が左右に線対称のとき,以下の文字列も左右に線対称.
  • "i" x "i"
  • "w" x "w"
  • "(" x ")"
  • ")" x "("
  1. 以上のもののみが左右に線対称.

ここで,"i" x "i" とは "i" と x と "i" を連結したものを表す. 他のものも同様である.

入力

入力は 'i', 'w', '(', ')' からなる 1 つの文字列である.

出力

置き換えなければならない文字数を表す整数を出力せよ.

制約

入出力例

入出力例 1

入力例 1:

(iwi)

入力例 1 に対する出力例:

0

入力例 1 では文字列がはじめから左右に線対称である.

入出力例 2

入力例 2:

ii(((((ww

入力例 2 に対する出力例:

5

入力例 2 では例えば ww((i))ww 等に変更すればよい.


Problemsetter: 秋葉 拓哉