prithivMLmods/Coder-Stat

1 2 3 4<H1><font color="#000000">Problem D:</font> Course Planning for Lazy Students</H1>5 6 7<p>8会津大学では2009年度より、授業履修に関する新しい制度を開始した。新制度では必修科目を撤廃し、それぞれの進路を考慮して科目を自由に選択できるようになった。9</p>10 11<p>12しかし、どの科目も無条件で履修できるわけではなく、特定の科目を履修するためには、先修条件を満たしている必要がある。下図に履修計画表の一部の例を示す：13</p>14 15<br>16<center>17<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_coursePlanning">18</center>19<br>20 21<p>22図の長方形が１つの科目を表し科目名と単位数を含んでいる。図の矢印が先修条件を表す。矢印の意味は、矢印の終点で指されている科目を履修するためには、その矢印の始点を示す科目を修得している必要がある。例えば、Linear Algebra II (線形代数２)を履修するためには、Linear Algebra I (線形代数１)を修得している必要がある。また、Applied Algebra (応用代数)を履修するためには、Linear Algebra I と Discrete Systems (離散系論)の両方を修得している必要がある。23</p>24 25<p>26さて、履修登録計画において卒業に要する最低限の合計単位数 <i>U</i> を満たす履修科目の組み合わせは、怠慢な学生にとって興味深いものである。27</p>28 29<p>30あなたの仕事は、与えられた履修計画表と <i>U</i> を読み込み、最低限の履修科目数を報告するプログラムを作成することである。これは計画であるため、履修登録した科目は必ず単位を修得できるものと仮定する。31</p>32 33<H2>Input</H2>34 35<p>36入力は複数のデータセットからなる。各データセットは以下の形式で与えられる：37</p>38 39<blockquote>40<i>n</i> <i>U</i><br>41<i>c</i><sub>0</sub> <i>k</i><sub>0</sub> <i>r</i>0<sub>1</sub> <i>r</i>0<sub>2</sub> ... <i>r</i>0<sub><i>k</i><sub>0</sub></sub><br>42<i>c</i><sub>1</sub> <i>k</i><sub>1</sub> <i>r</i>1<sub>1</sub> <i>r</i>1<sub>2</sub> ... <i>r</i>1<sub><i>k</i><sub>1</sub></sub><br>43.<br>44.<br>45<i>c<sub>n-1</sub></i> <i>k<sub>n-1</sub></i> <i>r(n-1)</i><sub>1</sub> <i>r(n-1)</i><sub>2</sub> ... <i>r(n-1)</i><sub><i>k</i><sub><i>n-1</i></sub></sub><br>46</blockquote>47 48 49<p>50<i>n</i> (1 &le; <i>n</i> &le; 20) は履修計画表が含む科目の数を示す整数である。科目には 0 から <i>n</i>-1 までの番号が割り当てられているものとし、以下 <i>i</i> 番目の科目を科目 <i>i</i> と呼ぶことにする。51</p>52 53<p>54<i>U</i> (1 &le; <i>U</i> &le; 100) は必要な合計単位数を表す整数である。55</p>56 57<p>58<i>c<sub>i</sub></i> (1 &le; <i>c<sub>i</sub></i> &le; 10)は科目 <i>i</i> の単位数を示す。次の <i>k<sub>i</sub></i> (0 &le; <i>k<sub>i</sub></i> &le; 5) は科目 <i>i</i> の先修科目の数を示す。それに続く <i>ri</i><sub>1</sub> <i>ri</i><sub>2</sub> ... <i>ri</i><sub><i>k</i><sub><i>i</i></sub></sub> は科目 <i>i</i> の先修科目の科目番号を示す。59</p>60 61<!--62<p>63入力で与えられる <i>n</i> は 20 以下と仮定してよい。また、<i>U</i> を満たす科目の組み合わせが必ず存在すると仮定してよい。64</p>65-->66 67<p>68ある科目から先修条件を表す矢印を１つ以上たどり、再びその科目に戻るような入力は与えられない。また、<i>U</i> を満たす科目の組み合わせが必ず存在すると仮定してよい。69</p>70 71<p>72<i>n</i> と <i>U</i> がともに 0 のとき入力の終わりを示す。データセットの数は 100 を超えない。73</p>74 75<H2>Output</H2>76 77<p>78各データセットについて、最低限必要な科目数を１行に出力せよ。79</p>80 81 82<H2>Sample Input</H2>83 84<pre>854 4861 0873 2 0 2882 0892 0903 6911 0923 2 0 2932 0940 095</pre>96 97<H2>Output for the Sample Input</H2>98<pre>9921003101</pre>102