入力

入力は以下の形式で標準入力から与えられる.

C1 A
C2 B

出力

二地点の間の時差を出力せよ.

制約

• C1, C2 は W か E のどちらかである.
• A, B は 0 以上 180 未満の 15 の倍数である.

小課題

この問題には小課題 / 部分点はない.

入力

入力は以下の形式で標準入力から与えられる.

N

出力

出力は, 以下の形式で標準出力から行うこと.

Result1
Result2

Result1 は 6 で割り切れるかどうか, Result2 は 11 で割り切れるかどうかを示す. Result1, Result2 は, それぞれについて割りきれる場合 yES, 割りきれない場合 nO となる.

制約

• N は 0 以上 10^{200 \ 000} 以下の整数.

小課題

この問題には小課題 / 部分点はない.

入力

入力は以下の形式で標準入力から与えられる.

N P
A_1 A_2 A_3 ... A_N

出力

PAKEN 君を喜ばせることができるなら Yay!, そうでないなら :( と出力せよ.

制約

• N は 1 以上 100 \ 000 以下の整数
• P は 1 以上 1 \ 000 \ 000 \ 000 以下の整数
• A_i は 1 以上 9 以下の整数

小課題

この問題には小課題 / 部分点はない.

入力

入力は以下の形式で標準入力から与えられる.

H W Q
a_1 a_2 a_3 ... a_H
b_1 b_2 b_3 ... b_W
px_1 py_1 qx_1 qy_1
px_2 py_2 qx_2 qy_2
px_3 py_3 qx_3 qy_3
...
px_Q py_Q qx_Q qy_Q

出力

Q 行にわたって出力せよ.

i 行目には, 左上のマスが (px_i, py_i), 右下のマスが (qx_i, qy_i) である長方形に含まれる (黒い長方形の面積の合計) - (白い長方形の面積の合計) を出力せよ.

制約

• H, W, Q は 1 以上 100 \ 000 以下の整数である.
• a_i, b_i は 1 以上 10 \ 000 以下の整数である.
• px_i, qx_i は 1 以上 H 以下の整数である.
• py_i, qy_i は 1 以上 W 以下の整数である.
• px_i \leq qx_i, py_i \leq qy_i である.

小課題

小課題1 [ 30点 ]

• H, W \leq 1 \ 000 を満たす.
• Q \leq 5 を満たす.

小課題2 [ 120点 ]

• H, W \leq 1 \ 000 を満たす.

小課題3 [ 250点 ]

• 追加の制約はない.

入力

入力は以下の形式で標準入力から与えられる.

n

出力

このゲームでもらえるお金の期待値を出力せよ. 絶対誤差または相対誤差が 10^{-7} 未満であれば, 正解となる.

制約

• n は 1 以上 500 \ 000 以下の整数である.

小課題

小課題1 [ 60点 ]

• n \leq 8.

小課題2 [ 120点 ]

• n \leq 18.

小課題3 [ 320点 ]

• 追加の制約はない.

入力

入力は, 以下の形式で標準入力から与えられる.

N
A_1 B_1
A_2 B_2
A_3 B_3
...
A_N B_N

出力

T さんがふすまを完全に閉め切るのに必要な体力の最小値を出力しなさい.

制約

• N は 1 以上 200 \ 000 以下の整数である.
• A_i, B_i (1 \leq i \leq N) は 1 以上 10 \ 000 以下の整数である.

小課題

小課題1 [ 200点 ]

• N \leq 10 を満たす.

小課題2 [ 500点 ]

• 追加の制約はない.

入力

入力は以下の形式で標準入力から与えられる.

N
a_1 b_1 r_1
a_2 b_2 r_2
a_3 b_3 r_3
...
a_N b_N r_N
K
y_1
y_2
y_3
...
y_K

出力

Thistle 君が K 回の買い替えで買う事の出来るパソコンの会社の種類数の最大値を出力せよ.

制約

• N, K は 1 以上 200 \ 000 以下の整数
• a_i は 1 以上 200 \ 000 以下の整数
• b_i は 2 以上 200 \ 000 以下の整数
• r_i は 0 以上 200 \ 000 以下の整数
• y_i は 0 以上 200 \ 000 以下の整数
• y_i < y_{i+1} (1 \leq i \leq K - 1)
• パソコンの買い替え時において, 一番性能の良いパソコンと二番目に性能が良いパソコンの性能は同じか, 1+10^{-11} 倍以上離れている. 一番性能の良いパソコンが同率で複数台あるときも、それより下とは 1+10^{-11} 倍以上離れている. (16:06 追記)

小課題

小課題1 [ 200点 ]

• N, K \leq 1 \ 000 を満たす.

小課題2 [ 500点 ]

• 追加の制約はない.

入力

入力は, 以下の形式で標準入力から与えられる.

N
A_1 A_2 A_3 ... A_N

出力

出力は, 以下の形式で標準出力から行うこと.

Q
(1 回目の操作の情報)
(2 回目の操作の情報)
(3 回目の操作の情報)
...
(Q 回目の操作の情報)

まず最初に, 行う操作の回数 Q を出力しなければならない. Q は 0 以上 550 \ 000 以下の整数でなければならない. 次の Q 行, 各回の操作の情報は, 以下のように出力しなければならない.

(☆) 操作 1 を行う場合

1 x

これは, P_x を 1 にするという操作を行う, という意味である.

(★) 操作 2 を行う場合

2 y z

これは, P_y に P_z の値を足すという操作を行う, という意味である.

制約

• N は 2 以上 200 \ 000 以下の整数である.
• A_1 = 1 を満たす.
• A_i (1 \leq i \leq N) は 1 以上 2^{30} - 1 以下の整数である.

小課題

小課題1 [ 60点 ]

• N = 2 を満たす.

小課題2 [ 140点 ]

• N \leq 8 \ 000 を満たす.

小課題3 [ 80点 ]

• N \leq 16 \ 000 を満たす.

小課題4 [ 230点 ]

• N \leq 25 \ 000 を満たす.

小課題5 [ 270点 ]

• N \leq 160 \ 000 を満たす.

小課題6 [ 220点 ]

追加の制約はない.

入力

入力は以下の形式で標準入力から与えられる.

N M
P_2 P_3 ... P_N
L_2 L_3 ... L_N
R_1 R_2 R_3 ... R_N

1 行目には, 頂点数 N と, 店の種類数 M が空白区切りで入力される.

2 行目には, 辺の情報 P_2, P_3, ..., P_N が空白区切りで与えられる.

3 行目には, 辺の長さの情報 L_2, L_3, ..., L_N が空白区切りで与えられる.

4 行目には, 店の種類の情報 R_1, R_2, R_3, ..., R_N が空白区切りで与えられる. R_i は, 頂点 i の店の種類を表す.

出力

i 行目には, 頂点 i の不便さを 1 行で出力せよ.

注意

入力サイズが 1 ケース当たり 7.5 MB 程度と大きいので, C++ の場合 cin/cout ではなく scanf/printf を使うことが推奨される.

制約

• N は 1 以上 400 \ 000 以下の整数.
• M は 1 以上 400 \ 000 以下の整数.
• P_i は 1 以上 i - 1 以下の整数.
• L_i は 1 以上 1 \ 000 \ 000 以下の整数.
• R_i は 1 以上 M 以下の整数.
• 種類 1 から M まで, 全種類の店が 1 個以上ある.

小課題

小課題1 [ 55点 ]

• N \leq 1 \ 500 を満たす.
• M \leq 750 を満たす.

小課題2 [ 110点 ]

• N, M \leq 70 \ 000 を満たす.
• N = M を満たす.

小課題3 [ 275点 ]

• N, M \leq 70 \ 000 を満たす.
• 同じ種類の店は王国中に高々 8 個しか存在しない.

小課題4 [ 330点 ]

• N, M \leq 70 \ 000 を満たす.

小課題5 [ 330点 ]

• N, M \leq 400 \ 000 を満たす.

入出力

1. まず, あなたは, 以下のような入力を受け取らなければならない.

N

N は, 平面上に存在する円の個数を表す.

2. 次に, あなたは質問をしなければならない. まず, 質問をするためには以下のように出力しなければならない.

? p q

あなたは '?', p, q を空白区切りで一行に出力しなければならない. これは, 座標 (p, q) はいくつの円の内部に含まれているか, という質問をすることを意味する. p, q は小数でもよいが, 絶対値が 5 \ 000 以下でなければならない.

3. 質問への答えは, 以下のようにしてジャッジから入力として受け取らなければならない.

R

R は, 質問した座標は何個の円の内部に含まれているかを表す整数である. 質問への答えが終わったら, 2. もしくは 4. に行かなければならない.

4. 答えが分かったら, 分かったタイミングで質問の代わりに解答を行わなければならない. 解答をするためには, 以下のような出力を行わなければならない.

!
x_1 y_1 r_1
x_2 y_2 r_2
...
x_N y_N r_N

(x_i, y_i) は i 個目の円の中心座標, r_i は i 個目の円の半径を意味する.

解答を行う際には, N+1 行にわたって出力しなければならない.

1 行目には, '!' と出力しなければならない.

2 行目からは, N 行にわたって円の情報 (x_i, y_i, r_i) をその順に空白区切りで出力しなければならない. ただし, 出力する順番は中心座標の x 座標の小さい順, x 座標が同じであれば y 座標の小さい順に出力しなければならない.

制約

• N は 1 以上 20 以下の整数.
• 円の座標 (x_i, y_i) と円の半径 r_i は, 問題文中に書かれている制約を満たす.
• 全てのケースは, 制約の範囲内で, 一様な確率でランダムに生成されたものである. 具体的には, それぞれの円に対して, まず中心座標が (-1000, -1000) から (1000, 1000) までの 4004001 個の中から一様な確率分布でランダムに選ばれ, 次に半径が 200 から 1000 までの 801 通りの選択肢の中から一様な確率分布で選ばれる.

注意

• 出力形式を間違えたりした場合にジャッジ結果は不定である. (WA とは限らない)
• また, 出力の最後に flush をする必要があり, そうしない場合 TLE となる場合がある.
• あなたは, 50 \ 000 回を超える質問をしてはならない.

小課題 / 得点

小課題1 [ 200点 ]

• N = 1 である.
• 小課題 1 のケースは 10 個ある. 10 個全てのケースに対して, 50 \ 000 回以内の質問で答えを求めることができれば, 正解となる.

小課題2 [ 1 \ 100点 ]

• N = 20 である.
• 小課題 2 のケースは 20 個ある. 20 個全てのケースで 50 \ 000 回以内の質問で答えを求めることができれば正解となるが, 質問回数によって下記のように得点が変わる.

一番多くの質問回数を要したケースにおける質問回数を L* とおくとき, 得点は以下のように変動する.

• 25 \ 001 \leq L* \leq 50 \ 000 のとき, 200 点.
• 9 \ 001 \leq L* \leq 25 \ 000 のとき, 280 点.
• 3 \ 001 \leq L* \leq 9 \ 000 のとき, 350 点.
• 2 \ 001 \leq L* \leq 3 \ 000 のとき, 450 点.
• 601 \leq L* \leq 2 \ 000 のとき, 300 + floor(\frac{480000}{L*}) の 1 の位を切り捨てて 10 の位までの概数にした得点.
• L* \leq 600 のとき, 1 \ 100 点満点.