AtCoder Regular Contest 006

B - あみだくじ


Time limit時間制限 : 2sec / Stack limitスタック制限 : 10MB / Memory limitメモリ制限 : 64MB

問題文

 高橋君は学校で班のリーダーを決めなければいけなくなったので、あみだくじを用いて決めることにしました。
 あみだくじとは、複数の縦線から 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 が偶数の時: (空白)
    • oL+2 行目にただ 1 つのみ与えられる。

出力

あみだくじを辿って o に到達するために選ぶべき縦線は左から何番目か 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

3 2
| |-|
|-| |
o    

出力例 1

3
  • 一番右の縦線を選ぶと、再左端に到達する。つまり、左から 3 番目を選択すると、 o のある位置に到達できる。

入力例 2

10 2
| |-| |-| |-| |-| |
|-| |-| |-| |-| |-|
            o      

出力例 2

9
  • 左から 9 番目の縦線から辿ると、o の位置に到達できる。
  • したがって、答えは 9 になる。

入力例 3

1 5
|
|
|
|
|
o

出力例 3

1
  • 縦線が 1 本なので、左から 1 番目の縦線が答えとなる。

入力例 4

4 2
| | | |
| | | |
      o

出力例 4

4
  • 横線が 1 本も存在しないので、o のある縦線を選べば良い。
  • したがって左から 4 番目の縦線が答えとなる。

入力例 5

9 8
| | | | | | | | |
|-| | |-| | |-| |
| | |-| | |-| | |
| |-| | | | | |-|
| | | |-| | | |-|
| | |-| |-| | | |
|-| | |-| | |-| |
| | | | | |-| | |
            o    

出力例 5

3

Source name

ARC 006

Submit提出する