prithivMLmods/Coder-Stat

1 2 3 4<H1>Problem F: Cosmic Market</H1>5<p>6Cosmic market(コズミック・マーケット)、通称コズミケ、は全宇宙最大規模の同人即売会だ。7コズミケにはあらゆるジャンルの同人愛好家達が集う。8近年、コズミケへの来場者は増加傾向にある。9最初から全ての人が入場できると大変混雑して危険なので、開場直後は入場規制を行っている。10ある一定人数の人だけが開場と同時に入場することが出来るのだ。11それ以外の人たちはしばらく待ってからの入場となっている。12</p>13 14<p>15しかし先着順に会場に入ることにすると、徹夜で前日から並ぶ人が出てしまう。16コズミケの参加者には未成年も多く、治安上の問題もあるので先着順という決め方はとても良くない。17そういう理由があって、コズミケでは参加者の中である種のゲームを行い、そのゲームで勝ち残った人が最初に入場する権利を手にできる。18公平を期すために毎年ランダム性の高いゲームを採用している。19</p>20 21<p>22僕は今回もコズミケに参加する予定だ。23僕は今回のコズミケでどうしても手に入れたい同人誌がある。24とある人気サークルが頒布する同人誌で、今年の春に話題になった魔法少女のアニメを取り扱っている。25しかし、このサークルはとても人気で毎回すぐに頒布が終了してしまう。26開場と同時に入場できなかった場合に手に入れることはほぼ不可能だろう。27もちろん後日同人ショップなどでも手に入るようになるのは間違いない。しかしそれまで我慢することなど僕には出来ない。28僕はどんな手を使ってでもコズミケ当日に手に入れなくてはいけないのだ。29不幸なことに僕は今までのコズミケで最初に入場できたことは一度もない。30</p>31	32<p>33コズミケのカタログによると、今回は以下のようなゲームで最初に入場できる人を選ぶらしい。34まず参加者のうち先着 <i>r</i>×<i>c</i> 人の人が、<i>r</i>×<i>c</i>　のグリッドのように配置された座席の好きな場所に座る。35先着順で場所を選べるので早く行った方が選択肢が沢山ある。36<i>r</i>×<i>c</i> 人の人が座ったらゲームが始まる。37このゲームはある一定の回数、ある1つの列（行）の座席にいる全ての人に対して、着席、あるいは起立が指示される。38すでに着席している人に着席の指示が出された場合はそのまま待機すれば。起立している人も同様である。39この指示が出される対象の列（行）と指示の内容はランダムにルーレットで決められる。40ある一定の回数の指示が終わった時点で起立している人だけが最初に開場に入れるのだ。41指示の回数は参加者には知らされていないので、いつゲームが終わるか分からない。42なのである時点で立っている人も座っている人も自分が最初に入場できるかは分からない。43だからスリルを味わうことが出来る、とカタログでは強調されている。44</p>45 46<p>47コズミケ前日の午後1時、僕は今年のゲームに関するデータをすべて手に入れた。48僕が手に入れた情報によると、この指示の回数、<i>q</i> はすでに決まっている。49それどころか<i>q</i> 回の指示内容が全てがすでに決まっている。50ランダム性が高いなどといわれているがそれは嘘だったのだ。51どういう理由があって事前に決まっているのかは分からない。52しかしこの情報は僕にとっては天の恵みのようだ。53</p>54 55<p>56もしこのデータどおりにゲームが行われれるのであれば、最初に入場することが出来る座席の場所が全て分かる。57最悪の場合、僕以外の参加者全員がこの情報を得ていたとしてみよう。58そんな場合でも遅くとも何番目に開場に到着すれば最初に会場に入ることが出来るかわかるはずだ。59しかしこの指示内容を今から手計算で解析するのは量が多すぎるので無理そうだ。60どんなに頑張ってもコズミケには間に合わない。61</p>62 63<p>64そこで、僕は君にこの計算を任せることにした。65君はプログラミングコンテストによく参加しており、このようなの計算プログラムを書くのは得意なはずだ。66もちろんただでやってくれとは言わない。67カタログによると、今年のコズミケにはプログラミングコンテストに関する同人誌を出しているサークルが参加する予定のはずだ。68もし僕が開場と同時に入場できたら報酬としてその同人誌を手に入れて君にプレゼントするよ。69さて、僕はこれから5時間ぐらい仮眠をとることにしよう。その間に君ならきっと答えを出してくれると僕は信じている。70</p>71 72<h2>Input</h2>73<p>74入力は複数のケースからなる。75各ケースは以下のフォーマットで与えられる。76</p>77 78<pre>79<i>r</i> <i>c</i> <i>q</i>80<i>A<sub>0</sub></i> <i>B<sub>0</sub></i> <i>order<sub>0</sub></i>81<i>A<sub>1</sub></i> <i>B<sub>1</sub></i> <i>order<sub>1</sub></i>82.83.84.85<i>A<sub>q-1</sub></i> <i>B<sub>q-1</sub></i> <i>order<sub>q-1</sub></i>86</pre>87 88<p>89<i>A<sub>i</sub></i> = 0 の時,<i>B<sub>i</sub></i> 行目に対して<i>order<sub>i</sub></i> の指示が実行される。<br>90<i>A<sub>i</sub></i> = 1 の時,<i>B<sub>i</sub></i> 列目に対して<i>order<sub>i</sub></i> の指示が実行される。<br>91<i>order<sub>i</sub></i> = 0の時は指定された行または列の人全員を座らせる。<br>92<i>order<sub>i</sub></i> = 1の時は指定された行または列を人全員を立たせる。<br>93</p>94 95<p>96入力の終わりは<i>r</i> =0 <i>c</i> =0 <i>q </i>=0 で与えられる。97</p>98 99<p>100入力の値は以下の条件を満たす。<br>1011 &le; <i>r</i> &le; 50,000<br>1021 &le; <i>c</i> &le; 50,000<br>1031 &le; <i>q</i> &le; 50,000<br>104<i>order<sub>i</sub></i> = 0 または 1<br>105<i>A<sub>i</sub></i> = 0 の時<br>1060 &le; <i>B<sub>i</sub></i> &lt; <i>r</i><br>107<i>A<sub>i</sub></i> = 1 の時<br>1080 &le; <i>B<sub>i</sub></i> &lt; <i>c</i><br>109</p>110 111<p>112テストケースの数は100を超えない<br>113</p>114 115<h2>Output</h2>116<p>117最悪の場合に、何番目までに到着すれば最初に会場に入れる権利を得ることが出来るかを一行で出力せよ。118</p>119 120<h2>Sample input</h2>121<pre>1225 5 51230 0 11240 0 01250 2 01261 2 11270 0 01285 5 51291 4 01300 1 11310 4 11321 3 01330 3 11345 5 51351 0 01360 3 01371 2 11380 4 01390 1 11400 0 0141</pre>142 143<H2>Sample output</H2>144<pre>1454146131478148</pre>149 150<hr>151<p>152The University of Aizu Programming Contest 2011 Summer<br>153原案、問題文: Tomoya Sakai<br>154</p>