問題文

わたしは近所のスーパーで初めてスパゲッティというものを購入した．パッケージの情報によると，このスパゲッティは T 秒茹でると最も理想的な状態に茹で上がるらしい．

ところでわたしは電気が嫌いな人間であり，家にはテレビやパソコンはおろか，時計さえ無い． そのためスパゲッティを茹でようにも，時間を測ることができない． 電池式の時計は嫌なので，わたしは代わりに砂時計を買おうと考え，スーパーの砂時計売り場へと向かった． 売り場には N 個の砂時計があった．i 番目の砂時計はちょうど x_i 秒だけ測ることができるようであった． いろいろあって悩ましいが，スパゲッティのために砂時計を何個も買うのは馬鹿らしいのでこの中からちょうど 1 個だけ買おうと思う．

しかし皆さんご存知の通り，砂時計というのは一度測り始めると，それから測り終えるまでは途中の時刻というのはまったく分からない． そのため，もし私が i 番目の砂時計を買って使ったとすると，時計を連続して使うことで x_i 秒，2x_i 秒，3x_i 秒，... という時間を測ることができるが，逆にそれ以外の時間は測ることができない．

理想的な茹で上がりに必要な時間は T 秒らしいが，ここでは妥協して E (< T) 秒以内の誤差を許そう． すなわち，どれか 1 つの砂時計を用いて，T-E 秒，T-E+1 秒，T-E+2 秒，...，T+E-2 秒，T+E-1 秒，T+E 秒のうちのどれかの時間を計測したい． 私は何番目の砂時計を購入して使えばよいだろうか?

N T E
x_1 ... x_N

入出力例

入力例 1

2 10 2
3 4

出力例 1

2

8秒，9秒，10秒，11秒，12秒 のうちのいずれかの時間を計測できればよい． 1 番目の砂時計で測ることのできる時間は 3秒，6秒，9秒，12秒，... であり， 2 番目の砂時計で測ることのできる時間は 4秒，8秒，12秒，16秒，... であるので，どちらの砂時計を用いても目的の時間を計測できる． 出力例 1 では 2 を答えとしているが，1 を答えにしても正解である．

入力例 2

3 10 5
16 17 18

出力例 2

-1

どの砂時計を使っても目的の時間は計測できない．

問題文

B君はオセロが大好きである (オセロのルールについてはWikipediaのオセロのページを参照せよ．「パス」についても Wikipedia に書かれているとおり，駒を打つことができない場合のみパスできるものとし，パスの回数に制限は無いものとする．) B君は駒の初期配置によってゲームの結果がどのように変わるのかに興味がある． しかしいきなり 2 次元の盤面で考えるのは難しいので，ひとまずは 1 次元の盤面で考えることにした． すなわち，この問題では盤面は縦幅 1，横幅無限のマス目であると見なす． また，オセロの駒はアルファベット小文字の o と x によって表すことにする．

B君はこの盤面上のオセロの初期配置として N 個の駒を連続させて並べ，左から i 番目の駒を c_i \in \{o, x\} とするものを考えることにした． 先手の駒を o とするとき，両方のプレイヤーが最善を尽くした時に勝利者がどちらになるかを求めて欲しい．

c1c2...cN

入出力例

入力例 1

oxxoxoo

出力例 1

o

最初は o の番であるが，打てるマスが存在しないのでパスをする． 続いて x の番になり，左端と右端のどちらかに打つことができる．しかし，x がどちらに打ったとしても o に勝つことはできない．

入力例 2

xxxooxxox

出力例 2

x

問題文

うさぎが N 匹おり，ボートを使って川を渡ろうとしている．ボートは K 個あり，誰がどのボートに乗るかを適当に決めて乗ることにした．

ところでうさぎというのは互いの仲の良し悪しに敏感であり，狭い空間に仲の悪いうさぎと一緒に閉じ込められると気分を悪くしてしまう． この N 匹のうさぎについても何組かのうさぎは仲が悪いということが分かっており，今の割り当てでは何匹かは気分を悪くしてしまう可能性がある． もっと良い割り当てを考えるのがよいところではあるが，ひとまず今の割り当てで何匹のうさぎが気分を悪くするかを求めて欲しい．

N\ K\\
m1\ bunny1,1\ ...\ bunny1,m1\\
m2\ bunny2,1\ ...\ bunny2,m2\\
...\\
mK\ bunnyK,1\ ...\ bunnyK,mK\\
R\\
p1\ q1\\
...\\
pR\ qR\\

入出力例

入力例 1

6 2
2 1 5
4 2 3 4 6
2
1 2
2 5

出力例 1

0

気分を悪くしているうさぎはいない．

入力例 2

6 2
2 1 5
4 2 3 4 6
3
2 3
3 4
1 2

出力例 2

3

割り当ては例 1 と同じであるが仲の悪さを表す組が異なっている．この例ではうさぎ 2,3,4 が気分を悪くしてしまう．

入力例 3

10 3
3 4 1 9
3 10 5 2
4 3 8 7 6
9
3 4
1 2
1 9
6 8
1 6
1 8
6 7
6 10
7 8

出力例 3

5

問題文

10号館とはとある大学にある建物で，J研究科のメンバーが日夜研究に勤しんでいる施設である．

10号館は建物が古いことで有名であったが，今年ついに改装されることになった． 改装工事終了後は綺麗な環境で研究が出来ると皆が期待していたある日， K研究科の一部が，改装工事終了後の10号館の部屋を侵略するという知らせが届いた．

10号館は N 個の部屋が1直線上に並んでおり，順番に 1,2,...,N の番号が付けられている． K研究科は，この N 個の部屋を全て侵略しようとしてくる． J研究科には M 人の教授が在籍しており，各教授はある区間に含まれる部屋に対して権力を発揮できる． 1人以上の教授に権力を発揮された部屋はK研究科に侵略されることはなく守ることが出来るが，どの教授からも権力を発揮されなかった部屋は侵略されてしまう．

教授は研究で忙しいので，出来るだけ少人数で全ての部屋を守りたい． 全ての部屋を守るために権力を発揮するべき教授の最少人数を求めよ． なお，教授全員が権力を発揮しても全ての部屋を守ることが出来無い場合があることに注意せよ．

N\ M\\
a1\ b1\\
...\\
aM\ bM

入出力例

入力例 1

8 4
3 7
1 5
2 5
4 8

出力例 1

2

2 番目の教授と 4 番目の教授が権力を発揮することにより，10号館の全ての部屋を守ることが出来る．

入力例 2

8 4
1 4
2 5
3 6
4 7

出力例 2

Impossible

問題文

E 君はじゃんけんが大好きである (ちなみにじゃんけんのルールについてはWikipediaのじゃんけんのページを参照せよ)． ある日，町内でじゃんけん大会があるということを知った E 君は，じゃんけんの腕に自信があったこともあり早速出場することにした． ところが大会当日，E 君を待ち受けていたのは，普通の「グー・チョキ・パー」のみからなる普通のじゃんけんではなく， より多くの手からなる一般化されたじゃんけんであった．

一般化されたじゃんけんは 2 人のプレイヤーで行われるゲームである． まず，2 人にはこのじゃんけんにおいて使用出来る手の個数 N と，N 個の手の勝敗関係を示す表が伝えられる． そして，通常のじゃんけんと同じように同時に手を出しあい，伝えられた手の勝敗関係に基いて勝敗を決める．これを 1,000 回 繰り返す． 1 回のじゃんけんの勝敗の結果によって得点が手に入り，相手に勝利した場合は 3 点，相手と「あいこ」になった場合は 1 点が手に入る．相手に負けてしまった場合は得点を得られない．

このなんだかよくわからないルールのじゃんけんにすっかり戦意を喪失してしまった E 君であったが，どうやら聞くところによると，最終的に相手に得点で勝てなくても，350 点以上を獲得すれば何か景品がもらえるらしい． めんどくさいので 350 点を得てさっさと大会を後にすることにした．

この問題の目的は，一般化されたじゃんけんをプレイする AI を作成し，ジャッジ側の用意した AI と対戦させて 350 点以上を獲得することである．

入出力形式

まず入力が以下の形式で与えられる．

N\ \\
a1,1 ... a1,N \\
...\\
aN,1 ... aN,N
 

N はじゃんけんの手の数である．
各 a_i,j は N 個の手の勝敗関係を表す． a_i,j は -，o，x のいずれかであり，- ならば手 i が手 j に対し引き分けることを，o ならば手 i が手 j に対し勝つことを，x なら負けることを示す．

この条件の下で 1,000回 AI とじゃんけんをする．

プログラムは自分の使う手を出力すると，ジャッジの AI が使った手を入力で受けとる事ができる． 例えば C/C++で 3 番目の手を使う場合は

printf("3\n"); fflush(stdout);

とする．次に，

scanf("%d", &judge_ai_hand);

とすると変数 judge_ai_hand にジャッジの AI が使った手が入る． なおじゃんけんの手は1-indexedである．

1,000 回のじゃんけんを終えた後は直ちにプログラムを終了せよ．その後，獲得できた得点の合計が 350 点以上であれば正答と判定される．

制約

• 3 ≤ N ≤ 10
• i \neq j のとき，a_i,j \in \{ o, x \} であり， a_i,j=o，a_j,i=x または a_i,j=x，a_j,i=o のどちらか片方が成り立つ．
• i = j のとき， a_i,j=- である．
• AI の出す手は勝敗関係の表 a_i,j と AI の過去の手にだけ依存し，競技者のプログラムの過去の手や直前に出した手には依存しない．
• N は整数である．
• データセットに N=10 のテストケースは高々 6 個しか含まれていない．

入出力例1

じゃんけんの説明
プログラムの出力
プログラムへの入力

4
-oox
x-oo
xx-o
oxx-

1 回目に競技者の AI が使った手
1

1 回目にジャッジの AI が使った手
2
 ... 
 ... 
 ... 
1,000 回目に競技者の AI が使った手
4

1,000 回目にジャッジの AI が使った手
3

最初にプログラムはじゃんけんの手の表を受け取る．その後，1,000 回のじゃんけんを行う． ここで，1 回目のじゃんけんでは競技者の AI はジャッジの AI に勝利しているが， 1,000 回目のじゃんけんでは競技者の AI はジャッジの AI に敗北していることに注意せよ．

インターネットと言う広大な海は少しずつ黒く塗りつぶされていった。
ボットの反乱、DDOS攻撃の嵐、ウィルスの蔓延、
何度も何度も繰り返されたクラッカーとの戦争で、人もインターネットもボロボロになった。

人の手では、インターネットはどうにもならない。
だから人は、とんでもない時間をかけて
インターネットを復旧できる「少女」を造った。

少女は、インターネットの手当をはじめた。
果てしなく広いインターネットの世界をどうにかしようと頑張った。

まだ少女ひとりでは撚り対線を織る事くらいしかできないけど、
長い長い時がすぎてインターネットが少し復旧すれば、
みんなと一緒に頑張れるだろうという期待をこめて。

問題文

少女はかつてインターネットに存在した N 個のサービスを復旧するために日々頑張っている． 現在を 0 日目とする． インターネットがどの程度復旧しているかを復旧度という指標で表し，現在の復旧度は 0 であるとする． 少女は毎日作業をし，復旧度を 1 日につき 1 ずつ上げていく． 任意のまだ復旧していないサービス i は，復旧度が w_i 以上になると自動的に復旧する． サービス i が復旧すると，みんなが手伝ってくれることにより，復旧した次の日から x_i 日間だけ作業がはかどり，復旧度の増加が加速する． サービスには 3 つの種類があり，種類によって復旧度がどの程度増加するのかが異なる． サービスの種類を 0, 1, 2 の番号で表すとする． サービス i の種類を t_i (\in \{0, 1, 2\}) とすると， サービス i が復旧してから d-1 日目から d 日目にかけて (1 ≤ d ≤ x_i)， t_i=0 の場合は 1， t_i=1 の場合は d， そして t_i=2 の場合は d^2 だけ，少女の作業とは別に復旧度が増加する． また，同時に複数のサービスが復旧している場合，それぞれのサービスは独立に並行して復旧度を増加させる．

少女はサービスが復旧するまでにとんでもない時間がかかると思ったので，現在から何日目にサービスが復旧するか調べることにした． またある日にち y_j に復旧度がいくらになっているかも気になったので，それも Q 日分だけ調べることにした．

N Q
w_1 t_1 x_1
...
w_N t_N x_N
y_1
...
y_Q

入出力例

入力例1

3 11
1 0 2
4 1 3
7 2 4
0
1
2
3
4
5
6
7
8
9
10

出力例1

1
3
4
0
1
3
5
7
11
19
29
46
47
48

入力例2

5 5
10000 0 20
10000 1 30
10000 0 40
10000 2 70
30000 2 10000
5000
10000
15000
20000
25000

出力例2

10000
10000
10000
10000
10039
5000
10000
40711690801
329498273301
333383477320

入力例3

2 2
3652425 0 1
3652426 2 10000
3652424
3652425

出力例3

3652425
Many years later
3652424
3652425

2つ目のサービスは復旧する日にちが 3,652,425 日を超えているのでMany years laterと出力している．

問題文

きつねのしえるは，休暇でとある小さな村を訪れている．彼女が驚いたのは，その村の表札がもつ性質である．

村には N 個の家屋がある．ここでは簡単のため，村は 2 次元平面であるとし，家屋はこの平面上の点であると見なす． それぞれの家屋には表札が 1 個設けられており，その家の苗字を表していた．しえるは村の中を訪問するにつれて，この村の表札が次のような性質を持っていることに気付いた．

• ある実数 R が存在する．
• もし 2 つの家屋の距離が R 以下であるなら，その 2 つの家屋は同じ表札を持つ．
• もし 2 つの家屋の距離が 3R 以上であるなら，その 2 つの家屋は異なる表札を持つ．
• 任意の 2 つの家屋の距離は R 以下であるか 3R 以上であるかのどちらかである．

ここで，家屋同士の距離は，平面上のユークリッド距離によって計測するものとする．

しえるはこの村に表札が全部で何種類あるのかが気になったが，この村は意外に広いということに気付いたので，計算機を使ってこの答えを模索することにした．

N\ R\\
x1\ y1\\
x2\ y2\\
...\\
xN\ yN

入出力例

入力例 1

5 3.000
1.000 0.000
0.000 0.000
-1.000 0.000
10.000 0.000
-10.000 0.000

出力例 1

3

家屋 1,2,3 と家屋 4 と家屋 5 で表札が異なる．全体で 3 つの表札が存在する．

入力例 2

12 1.234
0.500 0.000
-0.500 0.000
0.000 0.000
0.000 -0.500
55.500 55.000
-55.500 55.000
55.000 55.000
55.000 -55.500
99.500 99.000
-99.500 99.000
99.000 99.000
99.000 -99.500

出力例 2

7

入力例 3

5 99.999
0.000 0.000
49.999 0.001
0.000 0.000
-49.999 -0.001
0.000 0.000

出力例 3

1

問題文

とある大学の魔法学部の生徒であるK君は広大な屋敷に住んでいる． 屋敷の裏には林が広がっていたが，所々木が生えていない箇所があった． このままでは屋敷からの見た目が悪いと感じたので，K君は木が生えていない箇所に木を植えることに決めた． 魔法使いの卵であるK君は使い魔を召喚することが出来るので，植林の作業を使い魔にやらせようと考えた．

林は H \times W 個のセルを持つ長方形領域とみなすことが出来る． 各セルは木が1本生えているか1本も生えていないかのどちらかである． K君はこの H \times W 個のセルのどれか 1 つを指定し，そこに使い魔を召喚する． しかしK君はまだ未熟者なので，魔力を調節することが出来ず，使い魔を召喚するときは必ず 5 匹召喚してしまう． さらに悪いことに，K君が召喚する使い魔はひねくれもので，訪れたセルに木が生えていない場合はそこに木を植えるが，訪れたセルに既に木が生えている場合はそのセルの木を消してしまう． 召喚された使い魔のうちの 4 匹は，指定されたセルを始点として東西南北に散らばり1直線上を進み，1つ1つセルを訪れていく．これらの使い魔は林の外に出ると消える． 残りの使い魔は指定されたセルのみを訪問し，その後直ちに消える．

より正確に言えば，K君がセル (i, j) に使い魔を召喚すると，i 行目か或いは j 列目にある H+W-1 個のセルに対し， 木が生えていなければ木が植えられ，木が生えていれば木が消されるという操作が行われる．

召喚には多くの魔力を必要とするので，出来るだけ少ない召喚回数で林を木で覆いつくしたい． K君はどのセルに使い魔を召喚すれば最小の召喚回数で林を木で覆いつくすことが出来るだろうか．

H\ W\
a1,1\ ...\ a1,W\
...\
aH,1\ ...\ aH,W

b1,1\ ...\ b1,W\
...\
bH,1\ ...\ bH,W

入出力例

入力例 1

4 4
0 0 0 1
0 1 1 0
0 1 1 0
1 0 0 0

出力例 1

1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1

セル (1,1) とセル (4,4) に使い魔を召喚することで林を木で覆いつくすことが出来る．

問題文

わたしはある宝探しの依頼を受けた．
どうやら，この近くの地中 2W \times 2H の範囲内にお宝が埋まっているらしい．
わたしの得意なダウジングを使えば，現在の位置からお宝がどの方向にねむっているのか知ることができる．

ただ，わたしの能力はその日の体調による影響が大きく，今日はダウジングをした時に最大で E 度まで誤差が出てしまいそうだ．
また，わたしの体力にも限界はある．1日に200回までしかダウジングを行うことはできない．

わたしは考えることは苦手だ．
あなたには，宝を見つけるためにどこでダウジングをするべきかの指示を出していただきたい．

入出力形式

最初の入力は以下の形式で与えられる．入力は全て小数12桁までの実数で与えられる．

W H E

この入力は，宝の埋まっている座標 (x,y) が，

• -W ≤ x ≤ W
• -H ≤ y ≤ H

以降，あなたはダウジングを行う場所を指定し結果を得るか，もしくは，宝の場所を確定したと伝えることができる．

地点 (x,y) でダウジングを行い，結果を得るには

printf("? %.12f %.12f\n", x, y); fflush(stdout);

scanf("%lf", &degree);

地点 (x,y) に宝が存在すると伝える場合には

printf("! %.12f %.12f\n", x, y); fflush(stdout);

なお参考のため，実際にやりとりを行うプログラムを reactive.zip に置いている．

制約

• 0 ≤ W ≤ 10^4
• 0 ≤ H ≤ 10^4
• 0 ≤ E < 120
• 入力値は全て小数12桁までの実数である．
• ダウジングは最大で 200 回まで行える．それを越えると誤答(Query Limit Exceeded)となる．

この問題の判定には，3 点分のテストケースのグループが設定されている．このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

• E = 0

入出力例

プログラムの出力
プログラムへの入力

100 100 0

? -97.30147375 -55.03559390

45.8958081317
? 44.46472896 -54.50272726

110.928234444
 ... 
 ... 
! 4.50000018 50.00000005

最初にプログラムは宝のある範囲 W,H とダウジングの精度 E を受け取る．
その後，プログラムは (-97.3, -55.0) で1回目のダウジングを行い，宝のある方向は 45.8 度の方向だという情報を得ている．
次に，プログラムは (44.5, -54.5) で2回目のダウジングを行い，宝のある方向は 110.9 度の方向だという情報を得ている．
その後何度かダウジングを行い，最終的に宝のある位置は (4.5, 50.0) であると出力している．

問題文

きつねのしえるは川で釣りをしていた．黒くて細長い魚を手に入れることができたので，その場で切り刻んで刺身にして食べることにした．

魚は体長が N センチメートルある．奇妙なことに，この魚は身体の部分ごとに密度が異なっていた． 魚の身体を頭から 1 センチメートルごとに区切って番号を 1, 2, ..., N と付けるとき，身体の i 番目の部分の重みは w_i であった． 魚の i 番目から j 番目までの部分を [i..j] と表すことにする． 最初，しえるは魚の身体 [0..N-1] を 1 枚だけ持っていると見なせる．しえるはこれを切っていき最終的に N 個に分割された魚の身体 [0..0], [1..1], ..., [N-1..N-1] を得たい．

しえるは今野外におり，まな板などを持っていないので，次のようなアクロバティックな方法で魚の身体を切っていくことにした ： まず，魚の身体を 1 枚取る．これを [i..j] とする．この魚の身体は長さが少なくとも 2 センチメートル以上でなければならない．すなわち， j-i ≥ 1 でなければならない．次に，それを空中に投げる．そして日本刀を手に持ち，宙に舞う魚を真っ二つに切る．このとき，しえるは強靭な運動神経によって任意の位置でこの魚を切ることができるが，必ず 1 センチメートル区切りの位置で切るものとする．これにより，元の魚の身体 [i..j] を，任意の切断位置 k (i ≤ k < j) によって，[i..k] と [k+1..j] の 2 つに分割するのである． このアクロバティックな方法で魚の身体を 2 つに切るとき，元の身体の重さ (=w_i+w_i+1+...+w_j) だけコストがかかる．

しえるは，魚のすべての部分を 1 センチメートル区切りに切るのにかかるコストの合計値を最小にしたい．

N\\
w1\ w2\ ...\ wN

入出力例

入力例 1

3
1 2 3

出力例 1

9

まず，魚全体を 2 番目と 3 番目の部分の間で切る．これには 1+2+3 = 6 のコストがかかる． 次に，1 番目と 2 番目の部分の間で切る．これには 1+2=3 のコストがかかる．合計で 6+3=9 のコストがかかり，これが最善手である．

入力例 2

6
9876543210 9876543210 9876543210 9876543210 9876543210 9876543210

出力例 2

158024691360

入力例 3

10
127 131 137 139 149 151 157 163 167 173

出力例 3

5016

問題文

KU大学では一風変わったラリーゲームが人気である． このゲームの舞台であるサーキットには，N 個の休憩所と M 個の道があり，i 番目の道は f_i 番目の休憩所と t_i 番目の休憩所の間にある． すべての道にはチェックポイントが一つずつ存在し，道 i のチェックポイントを通過するとどちらの向きで通っても p_i の得点がXORで加算される．XORで加算される．大事なことなので2回言いました．

このゲームでは，同じ休憩所や道を何度通っても良いし， ゴールにたどり着いてもそのままラリーを続行することができるが， 道の途中にあるチェックポイントを迂回して別の休憩所へ行くことは禁止されている． そのため，どのような道順をたどれば高い得点を取ることができるかを頑張って考えなければならない点が人気のある所以である．

今回は Q 人の参加者がいて，j 番目の参加者は a_j の休憩所からスタートして，ゴールである b_j の休憩所まで行くことになっているようだ． 運営側の人間としてそれぞれの参加者の最高得点を前もって調べておくことにした．

N M Q
f_1 t_1 p_1
...
f_M t_M p_M
a_1 b_1
...
a_Q b_Q

入出力例

入力例1

5 5 3
0 1 7
1 2 22
2 3 128
3 4 128
4 2 128
0 1
0 0
3 4

出力例1

135
128
128