[[iwi]]

Time Limit : 1 sec, Memory Limit : 262144 KB

問題 C : [[iwi]]

そうだ,僕のハンドルネームは (iwi) だ. 僕は確かに昔にプログラミングコンテストに参加していた. そして,多くの仲間と楽しい時間を過ごした.

確か,仲間たちは全員,美少女だったような気がする. プログラミングコンテストの世界は,僕のハーレムだったような気がする. G○○gle は,僕のハーレムを奪ったのだ,そうに違いない. 昔の仲間の手がかりをつかむためにも,やはりプログラミングコンテストに出なければならない.

G○○gle Code Jam に参加登録することにしよう. 今度の ID には,丸括弧以外の括弧も検討に入れてみよう.

問題

'i', 'w', '(', ')', '{', '}', '[', ']' からなる文字列が与えられた時, その部分列をとって,線対称な文字列を作りたい. 最大で何文字の文字列を作ることができるかを計算するプログラムを作成せよ.

与えられる文字列は, "iwi" という文字列を一度含み,それ以外の部分には 'i' と 'w' を含まない. より形式的には,与えられる文字列は s "iwi" ts と "iwi" と t を連結したもの)という形で表すことができ, st は '(', ')', '{', '}', '[', ']' からなる文字列である. st が 0 文字である可能性もある.

作る文字列は,与えられる文字列の部分列をとって作る. 部分列とは,元の文字列からいくつかの文字を取り出し,それらを, 元の文字列に含まれる順番で繋げたものである. 取り出す文字たちは必ずしも元の文字列で連続していなくても良い.

また,作る文字列も,与えられる文字列と同様に,"iwi" という文字列を一度含み, それ以外の部分には 'i' と 'w' は含まないようにしたい.

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

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

入力

入力は 'i', 'w', '(', ')', '{', '}', '[', ']' からなり上記の条件を満たす文字列である.

出力

上記の条件を満たし作ることのできる文字列の長さの最大値を出力せよ.

制約

  • 入力の文字列の長さは 15 以下である.

入出力例

入出力例 1

入力例 1:

[[[iwi[[[

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

3

"iwi" という文字列しか作ることができない.

入出力例 2

入力例 2:

[{)iwi(]}

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

7

"[)iwi(]" や "{)iwi(}" など 7 文字の文字列を作ることができる.


Source: University of Tokyo Programming Contest 2011 , Tokyo, Japan, 2011-05-14
Problem Setter:  Takuya Akiba
http://www.utpc.jp/2011/