prithivMLmods/Coder-Stat

1 2 3 4<H1>通学経路</H1>5 6<h2>問題</h2>7 8<p>9太郎君の住んでいるJOI市は，南北方向にまっすぐに伸びる a 本の道路と，東西方向にまっすぐに伸びる b 本の道路により，碁盤の目の形に区分けされている．10</p>11<p>12南北方向の a 本の道路には，西から順に 1, 2, ... , a の番号が付けられている．また，東西方向の b 本の道路には，南から順に 1, 2, ... , b の番号が付けられている．西から i 番目の南北方向の道路と，南から j 番目の東西方向の道路が交わる交差点を (i, j) で表す．13</p>14<p>15太郎君は，交差点 (1, 1) の近くに住んでおり，交差点 (a, b) の近くのJOI高校に自転車で通っている．自転車は道路に沿ってのみ移動することができる．太郎君は，通学時間を短くするため，東または北にのみ向かって移動して通学している．16</p>17<p>18現在， JOI市では， n 個の交差点 (x<sub>1</sub>, y<sub>1</sub>), (x<sub>2</sub>, y<sub>2</sub>), ... , (x<sub>n</sub>, y<sub>n</sub>) で工事を行っている．太郎君は工事中の交差点を通ることができない．19</p>20<p>21太郎君が交差点 (1, 1) から交差点 (a, b) まで，工事中の交差点を避けながら，東または北にのみ向かって移動して通学する方法は何通りあるだろうか．太郎君の通学経路の個数 m を求めるプログラムを作成せよ．22</p>23 24 25<H2>入力</H2>26 27<p>28入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．入力はゼロを２つ含む行で終了する．29</p>30 31<p>321行目には，空白を区切りとして2個の整数 a, b が書かれている．これは，南北方向の道路の本数と，東西方向の道路の本数を表す． a, b は 1 &le; a, b &le; 16 をみたす．33</p>34<p>352行目には, 工事中の交差点の個数を表す整数 n が書かれている． n は 1 &le; n &le; 40 をみたす．36</p>37<p>38続く n 行 (3行目から n+2 行目) には，工事中の交差点の位置が書かれている． i+2 行目には空白で区切られた整数 x<sub>i</sub>, y<sub>i</sub> が書かれており，交差点 (x<sub>i</sub>, y<sub>i</sub>) が工事中であることを表す． x<sub>i</sub>, y<sub>i</sub> は 1 &le; x<sub>i</sub>, y<sub>i</sub> &le; 16 をみたす． 39</p>40 41<p>42データセットの数は 5 を超えない．43</p>44 45<H2>出力</H2>46<p>47<!--提出するファイルは, 太郎君の通学経路の個数 m だけを含む1行からなる.-->48データセットごとに, 太郎君の通学経路の個数 m を1行に出力する．49</p>50 51<h2>入出力例</h2>52<!--53<pre>54<table style="margin-bottom: 0px;  margin-left: 0px;  margin-right: 0px;">55 <tr>56  <th width="150" align="left">入力例</th>57 </tr>58<tr><td></td><td></td></tr>59<tr><td>5 4  </td></tr>60<tr><td>3  </td></tr>61<tr><td>2 2  </td></tr>62<tr><td>2 3  </td></tr>63<tr><td>4 2  </td></tr>64<tr>65  <td>　</td>66</tr>67<tr>68  <th width="150" align="left">出力例</th>69</tr>70<tr><td>5</td></tr>71</table>72-->73 74<H2>入力例</H2>75 76<pre>775 4783792 2802 3814 2825 4833842 2852 3864 2870 088</pre>89 90<H2>出力例</H2>91 92<pre>93594595</pre>96 97<p>下図は a=5, b=4, n=3 で，工事中の交差点が (2,2), (2,3), (4,2) の場合を表している．</p>98 99<center>100<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_route-fig1">101</center>102 103<p>104この場合，通学経路は m=5 通りある． 5通りの通学経路を全て図示すると，以下の通り．105</p>106 107<center>108<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_route-fig2">109</center>110 111 112<div class="source">113<p class="source">114上記問題文と自動審判に使われるデータは、<a href="http://www.ioi-jp.org">情報オリンピック日本委員会</a>が作成し公開している問題文と採点用テストデータです。115</p>116</div>117