prithivMLmods/Coder-Stat

1 2 3 4<script type="text/x-mathjax-config">5  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});6</script>7<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-MML-AM_CHTML">8</script>9 10 11<H1>あみだくじ</H1>12 13<p>14PCK 君はみんなでゲーム大会をしています。このゲーム大会では、大会の最後にあみだくじで順位を入れ替えます。大会には <var>N</var> 人のプレイヤーが参加しており、あみだくじには <var>N</var> 本の縦棒があります。15</p>16 17<p>18あみだくじは、図のように <var>N</var> - 1 段の部品からできており、それぞれ 1 から <var>N</var>-1 の番号が割り当てられています。各部品は、あみだくじの一部を横方向に切り取った部分です。各部品にはいくつかの横棒が引かれていますが、部品の中の横棒はすべて同じ高さにあります。横棒同士がつながることはありません。19</p>20 21<center>22<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_PCK2015_amida"><br/>23</center>24<br/>25 26<p>27大会の最後に、順位の高い人から右から左の順に縦棒が割り当てられます。PCK 君は現時点で最下位なので、左端からスタートです。例えば、上図の組み立て方では、６位だったPCK 君は、このあみだくじによって４位（右から４番目の棒）に浮上することができます。28</p>29 30<p>31このゲームでは、最下位の人にあみだくじを組み立てる権利が与えられます。PCK 君はうまくあみだくじの部品の順番を決めて、逆転優勝を狙っています。ただし、部品を回転することはできません。32</p>33 34<p>35（※補足：あみだくじのたどり方について）<br/>36あみだくじのある縦棒の上端から出発して上から下へ進む。ただし、横棒がある地点ではその横棒でつながった別の縦棒に移動する。これを、縦棒の下端にたどり着くまで繰り返す。37</p>38 39<p>40ゲームの参加人数とあみだくじの部品の情報を入力し、PCK 君が優勝できるかどうか判定するプログラムを作成せよ。優勝できる場合、そのあみだくじの部品の並びを１つ出力せよ。ただし、そのような並べ方が複数ある場合は、与えられた部品の番号で辞書順最小のものを出力せよ。41</p>42 43 44 45<h2>Input</h2>46 47<p>48入力は以下の形式で与えられる。49</p>50 51<pre>52<var>N</var>53<var>b<sub>1,1</sub></var> <var>b<sub>1,2</sub></var> ... <var>b<sub>1,N&minus;1</sub></var>54<var>b<sub>2,1</sub></var> <var>b<sub>2,2</sub></var> ... <var>b<sub>2,N&minus;1</sub></var>55:56<var>b<sub>N&minus;1,1</sub></var> <var>b<sub>N&minus;1,2</sub></var> ... <var>b<sub>N&minus;1,N&minus;1</sub></var>57</pre>58 59<p>60１行目に大会の参加者数 <var>N</var> (2 &le; <var>N</var> &le; 500) が与えられる。続く <var>N</var>-1 行に <var>i</var> 番目の部品の横棒の情報が与えられる。<var>b<sub>i,j</sub></var> が 1 であるとき、<var>i</var> 番目の部品の、左から <var>j</var> 本目の縦棒から <var>j</var>+1 番目の縦棒へ横棒が引かれていることを表す。<var>b<sub>i,j</sub></var> が 0 であるとき、<var>i</var> 番目の部品の、左から <var>j</var> 本目の縦棒から <var>j</var>+1 番目の縦棒へ横棒は引かれていないことを表す。<var>b<sub>i,j</sub></var> が 1 であるとき、<var>b<sub>i,j+1</sub></var> が 1 となるような部品は与えられない。また、横棒の総数は 10000 を越えない。61</p>62 63 64<h2>Output</h2>65 66<p>67PCK 君が優勝できる場合，１行目に「yes」と出力する。続く <var>N</var>-1 行に、あみだくじの上から順に、部品の番号の並びを出力する。そのような並びが複数ある場合、辞書順最小である並びを出力する。PCK 君が優勝できない場合、１行に「no」と出力する。68</p>69 70<h2>Sample Input 1</h2>71 72<pre>736741 0 0 0 1751 0 1 0 1760 1 0 1 0770 0 0 1 0780 1 0 0 179</pre>80 81<h2>Sample Output 1</h2>82<pre>83yes84185386287488589</pre>90<br/>91 92<h2>Sample Input 2</h2>93<pre>945950 1 0 1960 1 0 1971 0 1 0981 0 0 199</pre>100 101<h2>Sample Output 2</h2>102<pre>103yes1044105110631072108</pre>109<p>1104 1 3 2 と 4 2 3 1 の２通りの組み立て方が可能だが、辞書順で小さい方の 4 1 3 2 を出力する。111</p>112 113<br/>114 115<h2>Sample Input 3</h2>116 117<pre>11851191 0 0 11200 1 0 11211 0 0 01220 1 0 1123</pre>124 125<h2>Sample Output 3</h2>126<pre>127no128</pre>