AT_arc006_2 [ARC006B] あみだくじ

[problemUrl]: https://atcoder.jp/contests/arc006/tasks/arc006_2 高橋君は学校で班のリーダーを決めなければいけなくなったので、あみだくじを用いて決めることにしました。 あみだくじとは、複数の縦線から $ 1 $ 本を選び、その上端から下端へと辿っていき、途中で横線があれば、その横線を通り繋がっている隣接する縦線へと移動し、また下へと進みます。 今日はたまたま手元に紙がなかったので、パソコン上で `|`、`-`、`o` を用いて以下のようなあみだくじを作りました。 ``` | | | | | | | | | |-| | |-| | |-| | | | |-| | |-| | | | |-| | | | | |-| | | | |-| | | |-| | | |-| |-| | | | |-| | |-| | |-| | | | | | | |-| | | o ``` `o` がある位置に到達した人がリーダーになります。 実は高橋君はリーダーになりたかったので、どの縦線を選べば `o` に辿り着くのか知りたいです。 左から何番目の縦線を選べばリーダーになれるのかを求めなさい。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ L $ |x|x|‥‥| |x|x|‥‥| |x|x|‥‥| : : : : : : : : | | |‥‥| y y y‥‥y - 入力は $ L+2 $ 行ある。 - $ 1 $ 行目には、あみだくじの縦線の本数を表す整数 $ N(1≦N≦10) $ とあみたくじの長さを表す整数 $ L(1≦L≦20) $が与えられる。 - $ 2 $ 行目からの $ L $ 行には、あみたくじの形が与えられる。 - $ i $ 行目 $ (2≦i≦L+1) $ には $ 2N-1 $ 文字の記号が与えられる。 - 各行の $ j $ 番目の記号は、以下のようになっている。 - $ j $ が奇数の時：`|` - $ j $ が偶数の時(上記のxの位置)：`-` または ` `(空白) - `|` はあみだくじの縦線を表し、`-`はその両端の縦線を繋ぐ横線であることを表す。また、空白はその位置に横線が無いことを表す。 - `|` を $ 1 $ つ挟んで左右に隣り合ったxの位置の両方が `-` という入力は存在しない。 - $ L+2 $ 行目には $ 2N-1 $ 文字の記号が与えられる。 - 各行の $ j $ 番目の記号は、以下のようになっている。 - $ j $ が奇数の時(上記のyの位置)：`o` または ` `(空白) - $ j $ が偶数の時：` `(空白) - `o` は $ L+2 $ 行目にただ $ 1 $ つのみ与えられる。 あみだくじを辿って `o` に到達するために選ぶべき縦線は左から何番目か $ 1 $ 行で出力せよ。 なお、最後には改行を出力せよ。 ``` 3 2 | |-| |-| | o ``` ``` 3 ``` - 一番右の縦線を選ぶと、再左端に到達する。つまり、左から $ 3 $ 番目を選択すると、 `o` のある位置に到達できる。 ``` 10 2 | |-| |-| |-| |-| | |-| |-| |-| |-| |-| o ``` ``` 9 ``` - 左から $ 9 $ 番目の縦線から辿ると、`o` の位置に到達できる。 - したがって、答えは $ 9 $ になる。 ``` 1 5 | | | | | o ``` ``` 1 ``` - 縦線が $ 1 $ 本なので、左から $ 1 $ 番目の縦線が答えとなる。 ``` 4 2 | | | | | | | | o ``` ``` 4 ``` - 横線が $ 1 $ 本も存在しないので、`o` のある縦線を選べば良い。 - したがって左から $ 4 $ 番目の縦線が答えとなる。 ``` 9 8 | | | | | | | | | |-| | |-| | |-| | | | |-| | |-| | | | |-| | | | | |-| | | | |-| | | |-| | | |-| |-| | | | |-| | |-| | |-| | | | | | | |-| | | o ``` ``` 3 ```

N/A

N/A