prithivMLmods/Coder-Stat

1 2 3<script src="./IMAGE/varmath.js" charset="UTF-8"></script>4 5<h1>Problem J: J's Final Problem</h1>6<h2>Problem</h2>7 8<p>9不思議なダンジョンとは構造の変化を伴うダンジョンである。不思議なダンジョンは階層が深いものから浅いものまで様々なものがあり、深い階層には凶悪なモンスターが生息していたり、財宝が眠っていたりする。ジェイは不思議なダンジョンを研究している研究者である。ある日、新しいダンジョンを掘っていたところ、とても大きく深いダンジョンに繋がってしまった。ジェイはこのダンジョンを「ジェイの最終問題」と名付けた。このダンジョンの調査が、優秀な冒険者であるあなたに依頼されることになった。冒険者の目的はできるだけ深い層のフロアに到達することである。このダンジョンの特徴を以下に述べる。10</p>11 12<ul>13<li>地上からダンジョンの地下1階の部屋への下りの階段は1つしか存在しない。</li>14<li>各部屋は1つの上りの階段と2つの下りの階段が存在する。</li>15<li>2つの下りの階段のうち片方を右の階段、もう片方を左の階段とする。</li>16<li>冒険者が階段を降りた際に、ダンジョンの構造が変化することがある。</li>17<li>階段を降りるとは、地下<var>i</var>階のある部屋から地下<var>i</var>+1階のある部屋へ降りることを示す。</li>18<li>階段を上った場合はダンジョンに対して何も変化を及ぼさない。</li>19<li>地下<var>n</var>階目には階段は存在しない。</li>20</ul>21 22<p>23最近、ジェイの最終問題に関する石碑が発見された。24どうやら、各階の階段を降りたときの変化がメモとして記されているようだ。25 26メモの形式は、27</p>28 29<ul>30<var>num1</var> <var>direction1</var> : <var>num2</var> <var>direction2</var> 31</ul>32 33<p>34という形である。35 36地下<var>num1</var>階のすべての部屋について、direction1の階段を降りている途中で、地下num2階のすべての部屋について、 direction2の階段を降りた先の部屋が消滅し、さらにそこから階段を降りることによって到達できる部屋や階段がすべて消滅する。部屋や階段の消滅に冒険者が巻き込まれた場合、冒険は失敗する。地下<var>i</var>階から地下<var>i</var>+1階へ向かう階段の途中で冒険者が失敗した場合は地下<var>i</var>階まで到達したものとして扱う。37 38石碑において言及されていない階段は、その階段を降りてもダンジョンの構造に変化を及ぼさないことを示す。39 40<br/>41<br/>42冒険者はこの石碑をヒントにして探索を行うことにした。43</p>44 45<p>46ダンジョンの深さ<var>n</var>とメモの情報が<var>m</var>個与えられるので、最大地下何階まで到達できるかを答えなさい。47</p>48 49<h2>Input</h2>50<p>51 52入力は複数のデータセットからなる。</br>53 54</p>55 56<pre>57<var>n</var>　<var>m</var>58<var>memo<sub>1</sub></var>59<var>memo<sub>2</sub></var>60…61<var>memo<sub>m</sub></var>62</pre>63 64<p>65最初に<var>n</var>,<var>m</var>が与えられる。66それぞれ、ダンジョンの変化前の最下層の階数、石碑のメモの数を表す。67次に<var>m</var>行にわたりメモの情報 <var>num1</var> <var>direction1</var> : <var>num2</var> <var>direction2</var> が与えられる。68</p>69 70 71<h2>Constraints</h2>72<p>入力は以下の条件を満たす。</p>73<ul>74 75<li>入力に含まれる値はすべて整数</li>76<li>1 &le; <var>n</var> &le; 10000</li>77<li>0 &le; <var>m</var> &le; (<var>n</var>-1)&times;4</li>78<li>1 &le; <var>num1</var>,<var>num2</var> &le; <var>n</var>-1</li>79<li>direction1,direction2は"left"と"right"のいずれかである。</li>80 81</ul>82 83<h2>Output</h2>84<p>85最大地下何階まで降りることができるか1行に出力して答えよ。86</p>87 88<h2>Sample Input1</h2>89<pre>9010 2919 left : 9 left929 right : 9 right93</pre>94 95<h2>Sample Output1</h2>96<pre>97998</pre>99 100 101<h2>Sample Input2</h2>102<pre>1034 51041 left : 2 right1052 left : 3 right1062 left : 3 left1071 right : 3 left1082 right : 3 right109</pre>110 111<h2>Sample Output2</h2>112<pre>1133114</pre>