Time Limit: 2 sec / Memory Limit: 1024 MB
配点 200 点
問題文
座標平面上にAliceがいます。彼女のいる座標は (0,0) です。
彼女は「桂馬飛び」のみで座標 (x,y) に行けるでしょうか。行ける場合は、最小で何回の桂馬飛びで行けるのかを求めてください。
なお、1 回の「桂馬飛び」とは以下の移動のことを指します。
- 座標 (a,b) にいる時、座標 (a+1,b+2) または (a-1,b+2) に移動する。
制約
- 入力は全て整数である。
- -10^5 \leq x, y \leq 10^5
入力
入力は以下の形式で標準入力から与えられます。
x y
出力
座標 (x,y) に行ける場合は、最小で何回の桂馬飛びをするかを出力してください。行けない場合は -1 を出力してください。
入力例1
1 6
出力例1
3
1 回目で (1,2) に飛び、2 回目で (0,4) に飛び、3 回目で (1,6) に飛ぶことでたどり着けます。
以下の画像のように動きます。
入力例2
6 1
出力例2
-1
どのように動いても、座標 (6, 1) には桂馬飛びだけではたどり着けません。
入力例3
869 -120
出力例3
-1
writer: sinatori
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 400 点
問題文
タプリスは技術室国に降り立ちました。
技術室国は 1 ～ N までの N 個の町と N-1 本の道からなっていて、それぞれの道は都市 A_i と都市 B_i を双方向に結んでいます。
また、任意の町から任意の町へと何本かの道を経由することでたどり着くことができます。
技術室国の M 個の町、C_1, C_2, C_3, ..., C_M にはガヴリールの写真があることが知られていて、タプリスはこれらの写真をすべて集めたいです。
しかし、あまり長く外に出ていると門限を過ぎてしまうため、同じ町を二度通らないように町をめぐり、写真を集めることにしました。
タプリスはどの町に降り立ってもよく、どの町で写真集めを終わらせてもよいです。その時、タプリスがすべての写真を集めることができるのかを判定し、集められるなら Yes、集められないなら trumpet と出力してください。
制約
- 入力は全て整数である。
- 1 \leq N \leq 10^5
- 1 \leq A_i, B_i \leq N
- 1 \leq M \leq N
- 1 \leq C_i \leq N
- C_i \neq C_j (i \neq j)
- 与えられるグラフは木である。
小課題
この課題には 2 つの小課題があります。- (200 点) N \leq 2 \ 000
- (200 点) 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられます。
N M
A_1 B_1
A_2 B_2
⋮
A_{N-2} B_{N-2}
A_{N-1} B_{N-1}
C_1 C_2 ... C_{M-1} C_M
出力
タプリスがすべての写真を集められるなら Yes、集められないなら trumpet と出力せよ。
入力例1
3 2
1 2
1 3
1 2
出力例1
Yes
入力例2
5 3
1 2
2 3
3 4
4 5
3 4 5
出力例2
Yes
入力例3
4 3
1 2
1 3
1 4
2 3 4
出力例3
trumpet
writer: Thistle
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 400 点
問題文
机の上に 0 が書かれたカードが A 枚、1 が書かれたカードが B 枚あります。また、黒板には 0 が書かれています。
天使と悪魔が以下のようなゲームを行います。天使を先手とし、それぞれは以下の行動を各ターンに行います。
- 天使 : 机の上のカードを 1 枚選択し、その整数を黒板に書かれた整数に加算する。その後、選んだカードを食べる。
- 悪魔 : 机の上のカードを 1 枚選択し、そのカードを食べる。黒板に対しては操作をしない。
互いに最善を尽くした時、どちらが勝つか判定してください。
制約
- 入力は全て整数である。
- 0 \leq A,B \leq 10^{17}
入力
入力は以下の形式で標準入力から与えられます。
A B
出力
先手である天使が勝つ場合は Angel を、後手である悪魔が勝つ場合は Devil を 1 行に出力してください。
入力例1
0 1
出力例1
Angel
机の上には 1 が書かれたカードが 1 枚だけあります。
先手の天使はそのカードを食べ、黒板に書かれた整数を 1 にします。
そうすると、机の上からカードがなくなり、黒板には 1 が書かれているので天使の勝利で、Angel を出力すれば正解となります。
入力例2
2 3
出力例2
Devil
writer: Ryo2016
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 400 点
問題文
二年生になったPAKEN君は、新入生歓迎の一環として、長さ N の整数列 A をプレゼントすることにしました。
また、彼は情報に強いので、新入生に人気の整数が 2 つあり、これが P と Q であるという情報を入手しました。
PAKEN君は、数列 A が P, Q と密接な関係にあるほど新入生が喜ぶだろうと思ったので、次の条件を全て満たす整数 (x,y,z) の組がどれだけあるかを数えようとしました。
- 1 \leqq x < y < z \leqq N
- A_x + A_y + A_z = P
- A_x - A_y - A_z = Q
PAKEN君に代わって、上の条件を満たす組 (x,y,z) の個数を求めてください。
制約
- 入力は全て整数である。
- 3 \leqq N \leqq 10^5
- -10^9 \leqq P,Q \leqq 10^9
- -10^9 \leqq A_i \leqq 10^9
入力
入力は以下の形式で標準入力から与えられます。
N P Q
A_1 A_2 ... A_{N-1} A_N
出力
条件を満たす組 (x, y, z) の個数を出力してください。
入力例1
4 10 0
5 3 3 2
出力例1
2
(x,y,z)=(1,2,4),(1,3,4) の 2 つの組において、条件を満たします。
入力例2
5 22 -9
1 7 9 3 -2
出力例2
0
条件を満たす組 (x, y, z) は 1 つもありません。
入力例3
10 10 6
8 1 8 1 8 1 8 1 8 1
出力例3
20
writer: TAISA_
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 400 点
問題文
晴れて天使学校を卒業したタプリスたち、天使 1 から天使 N までの N 人の天使たちが下界に降りてきました！ そして、先輩である天真さんを見習って引きこもることにしました！
しかし、このままではお互いに会えなくなってしまうことに気が付いた天使たちは、お互いの住んでいる部屋に行けるように、バス路線のうち長さ L 以下の路線に無料で乗ることができる、無料チケットを手に入れることにしました。
下界のバスは M 路線あり、i 番目の路線は天使 A_i が引きこもっている部屋と天使 B_i が引きこもっている部屋を双方向に結んでおり、路線の長さは C_i です。
天使たちは寂しがり屋なので、それぞれの天使が q 人以上の天使に会えない場合、寂しさから堕天してしまいます。
そこで、タプリスは天使たちがどの程度の寂しがり屋でも対応できるように、いくつかのqについて、購入する必要のあるバスの無料券の路線の上限の長さ、L の最小値を求めようと思いましたが、難しかったのであなたに頼むことにしました。
あなたの仕事は、Q回のクエリで、それぞれ与えられる q_i について 、全ての天使が自分を含めて q_i 人以上の天使に会えるために必要なL (L \geq 0)を求めることです。
なお、天使は無料チケット以外で移動することはできないものとします。
制約
- 入力は全て整数である
- 2 \leq N, M, Q \leq 10^5
- 1 \leq A_i, B_i \leq N
- 0 \leq C_i \leq 10^{10}
- 1 \leq q_i \leq 10^5
- 与えられるグラフは単純とも連結とも限らない
入力
入力は以下の形式で標準入力から与えられます。
N M Q
A_1 B_1 C_1
A_2 B_2 C_2
⋮
A_{M-1} B_{M-1} C_{M-1}
A_M B_M C_M
q_1
q_2
⋮
q_{Q-1}
q_Q
出力
Q 行に渡って出力してください。
i 行目には、i 個目のクエリに対する最小の L の値を出力してください。
なお、どのような L の値を設定しても条件が達成できない場合は、このクエリの答えとして trumpet と出力してください。
入力例1
9 10 4
1 2 3
1 4 1
3 4 4
2 3 1
4 5 9
5 6 3
6 7 4
7 8 2
8 9 3
6 9 5
2
3
5
10
出力例1
3
4
9
trumpet
例えば、1 個目の質問に対して、全ての天使は自分を含めて 2 人以上と会えなければなりません。
この例において、L = 2 の場合と L = 3 の場合の無料チケットが使えるバスは以下の図のようになります。
この図において、L = 2 の場合、天使 5, 6, 9 は自分を含め 1 人の天使にしか会うことはできません。
L = 3 になると、天使 1 は天使 {1, 2, 3, 4} と、天使 5 は天使 {5, 6} と、天使 7 は天使 {7, 8, 9} と会うことができます。このように、全ての天使は自分を含め 2 人以上の天使に会うことができます。
よって、q_1 = 2 の場合の答えは 3 です。
writer: Thistle
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 700 点
問題文
魔法少女のタプリスさんは、Segtree という魔法のステッキを手に入れました。タプリスさんはクオリティの低い自分のなりきり達に腹を立てており、このステッキを使ってなりきり達を倒すことにしました。
N 体のなりきりが一直線に並んでおり、左から順に 1 から N までの番号が付いています。i 番目のなりきりの体力は A_i です。タプリスさんはこれから好きな順番で好きな回数だけ、K 以上 N-K+1 以下の番号の相手をヒットすることができます。
Segtree は範囲攻撃型の武器であり、タプリスさんが x 番目の相手を Segtree でヒットすると y 番目の相手は max(0, K-|x-y|)^2 のダメージを受けます。
タプリスさんはよい天使なので、相手の体力がゼロより小さくなるようには攻撃しません。タプリスさんがこの条件を遵守した上ですべての相手を倒すこと、つまりすべての相手の体力をちょうどゼロにすることが可能であるかを判定してください。
入力
入力は以下の形式で標準入力から与えられる。
N K
A_1 A_2 ... A_{N-1} A_N
出力
全ての相手の体力をちょうどゼロにすることが可能なら Yes、そうでないなら No と出力してください。
制約
- 入力は全て整数である。
- 3 \leq N, K \leq 133 \ 333
- 2K-1 \leq N
- 0 \leq A_i \leq 10^{13}
小課題
この課題には 2 つの小課題があります。- (200 点) N, K \leq 1 \ 333
- (500 点) 追加の制約はない。
入力例1
8 3 1 4 10 9 14 13 5 1
出力例1
Yes
例えば、3番目、5番目、6番目の相手をこの順に Segtree でヒットすると、以下のように体力の値が変化します。
- まず、3 番目の相手をヒットする。相手の体力は左から順に {0, 0, 1, 5, 13, 13, 5, 1} に変化する。
- 次に、5 番目の相手をヒットする。相手の体力は左から順に {0, 0, 0, 1, 4, 9, 4, 1} に変化する。
- 次に、6 番目の相手をヒットする。相手の体力は左から順に {0, 0, 0, 0, 0, 0, 0, 0} に変化する。
入力例2
6 3 8 6 9 1 2 1
出力例2
No
どのようなやり方でヒットしても、全ての相手の体力をちょうどゼロにすることはできません。
入力例3
16 4 2 9 22 41 34 20 20 37 71 72 55 36 15 5 1 0
出力例3
Yes
writer: ynymxiaolongbao
Time Limit: 3 sec / Memory Limit: 1024 MB
配点: 700 点
問題文
パ研には部長の E869120 君の他に部員 1 から部員 N までの N 人の部員がいます。
パ研部員たちは全員AtCoderのコンテストに参加しており、E869120 君の現在のレーティングは A、部員 i の現在のレーティングは a_i です。
彼は、パ研をより強い部活にするため、自分以外の部員に対してこれから以下のような操作を何回か行うことにしました。
-
操作 1: 部員 1 人を選び、教育する。
部員 i を 1 回教育すると、その部員のレーティングが b_i 上がります。
また、何度も同じ部員を教育すれば、そのたびにレーティングが b_i 上がります。
このとき、E869120 君は毎回体力を c_i 消費します。 -
操作 2: 現在部員であるうちの 1 人を選び、圧力をかけて退部させる。
部員 i を退部させるとき、E869120 君は体力を d_i 消費します。
E869120 君は、消費する体力の合計が K 以下となるようにこれらの操作を行い、彼自身を含むパ研部員のAtCoderレーティングの平均を最大化したいです。
このとき、達成できる最大の平均レーティングを求めて下さい。
なお、E869120 君は彼自身を教育することはできず、また退部することもないものとします。
制約
- 入力は全て整数である。
- 1 \leq N \leq 1 \ 500
- 1 \leq K \leq 1 \ 500
- 1 \leq A \leq 10^9
- 1 \leq a_i, b_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq c_i, d_i \leq K (1 \leq i \leq N)
小課題
この課題には 2 つの小課題があります。- (300 点) N, K \leq 500
- (400 点) 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられます。
N K A a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 ... a_N b_N c_N d_N
出力
達成できる最大の平均レーティングを出力してください。
絶対誤差または相対誤差が 10^{-4} 未満であれば正解となります。
入力例1
3 200 2804 2416 20 30 80 2269 80 20 80 2115 30 40 70
出力例1
2656.33333
以下のような操作によって平均レーティングを最大にできます。
- まず、部員 3 に圧力をかけて退部させる。このとき E869120 君は体力を 70 消費する。
- 次に、部員 2 を 6 回教育する。このとき E869120 君は体力を 120 消費する。
操作の後、残っている部員は E869120 君と部員 1、部員 2 のみで、それぞれレーティングは 2804、2416、2749 になります。
入力例2
2 170 1 30 1 10 50 20 30 50 50
出力例2
47.66667
E869120 君は自分よりレーティングの高い部員も教育できることに注意して下さい。
入力例3
4 300 4089 2800 20 30 40 3200 30 40 50 3600 30 50 60 4000 20 70 80
出力例3
4089.00000
最適な操作をした場合、E869120 君は他の部員を全員退部させ、パ研部員は E869120 君 1 人となります。
writer: autumn_eel
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 700 点
問題文
現在のパ研では、「打鍵戦争」というゲームが流行っています。パ研には N 人の部員がいますが、その中から「打鍵戦争」という大会に K (2K \leq N) 人の代表選手を出すことになりました。
各部員には、「打鍵力」という値が定まっており、部員 i の打鍵力は A_i で、この値が等しいような部員の組は存在しません。
現在パ研では、「打鍵力」の小さい方から K 人が「代表候補」として選ばれています。
パ研の主将であるあなたは、以下の操作を 0 回以上行います。
- その時点で代表候補である部員 i、代表候補でない部員 j を自由に選び、対戦させる。
- 部員 i は確率 \frac{A_i}{A_i+A_j} で勝ち、部員 j は確率 \frac{A_j}{A_i+A_j} で勝つ。
- その時点で代表候補である部員 i が勝った場合何も起こらない。
- その時点で代表候補でない部員 j が勝った場合、部員 j が新たに代表候補となり、部員 i は代表候補から外れる。
あなたが対戦をさせるのをやめた時点で代表候補である部員たちが、そのまま代表選手となります。
あなたは、できるだけ少ない回数の対戦を行うことで、代表選手の打鍵力の和を最大化したいと思っています。対戦回数の期待値を最小化するように対戦させたとき、代表選手の打鍵力の和が最大になるまで何回の対戦が必要でしょうか。その期待値を求めてください。
制約
- 入力は全て整数である。
- 2 \leq N \leq 10^5
- 1 \leq 2K \leq N
- 1 \leq A_i \leq 10^9
- A_i \neq A_j(i \neq j)
入力
入力は以下の形式で標準入力から与えられます。
N K
A_1 A_2 ... A_{N-1} A_N
出力
対戦回数の期待値の最小値を出力してください。
絶対誤差または相対誤差が 10^{-9} 以内ならば正解となります。
入力例1
2 1
42 8
出力例1
1.190476190476
部員 1 と部員 2 を、部員 1 が勝つまでひたすら対戦させるしかありません。
このときの対戦回数の期待値は、 \frac{25}{21} = 1.190476... 回となります。
入力例2
5 1
3 9 4 2 8
出力例2
1.222222222222
入力例3
10 5
20 3 9 5 8 1 100 32 7 2
出力例3
5.723472222222
writer: TAISA_
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 700 点
問題文
互いに素でないペアを持つ N の約数の集合の個数を求めてください。
入力
N は M 個の自然数 A_1A_2...A_{M-1}A_M の積であり、以下の形式で標準入力から与えられます。
M
A_1 A_2 ... A_{M-1} A_M
制約
- 入力は全て整数である。
- 1 \leq M \leq 1 \ 000
- 1 \leq A_i \leq 10^9
出力
条件を満たす集合の個数を 10^9+7 で割ったあまりを出力してください。
入力例1
1 6
出力例1
6
N = 6 のとき、(2, 6), (3, 6), (2, 3, 6), (1, 2, 6), (1, 3, 6), (1, 2, 3, 6) の 6 つの集合が条件を満たします。
入力例2
2 2 3
出力例2
6
N = 2 \times 3 = 6であり、入出力例 1 と等しい問題です。
入力例3
10 16808 282475250 622650074 984943659 144108931 470211273 101027545 457850879 458777924 7237710
出力例3
820588505
10^9+7 で割った余りを求めることに注意してください。
writer: ynymxiaolongbao
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
パ研王国には N 個の町があり、 M 本の道がそれらを結んでいます。i 番目の道は町 A_i から町 B_i を一方通行に結んでいます。 また、 P 個の町には 1 つずつ展望台があり、町 C_i の展望台は標高 D_i の場所に設置されています。
ZRK君はこれからドライブに行く計画を立てています。彼は町 S の展望台を出発し、いくつかの道を移動して町 T の展望台でドライブを終えます。 同じ町や道を何度通過しても構いません。
ZRK君は、通過した町に展望台がある場合必ず立ち寄ります。 彼の嬉しさは最初 0 ですが、出発時以外である展望台 i に立ち寄った時、その直前に立ち寄った展望台 j との標高差の絶対値 |D_i - D_j| だけ嬉しさが増えます。
彼は、ドライブを終えた後の嬉しさが K 以上となるルートでドライブをしたいです。 この条件を満たすルートの長さの最小値がいくつになるか求めてください。
ただし、ルートの長さは、全ての道に対する「この道を何回通ったか」の値の合計値とします。例えば、頂点 3→5→2→4→3→5→4 というルートを辿った場合、ルートの長さは 6 となります。
もし嬉しさが K 以上となるルートが存在しない場合、代わりに -1 と出力して下さい。
制約
- 入力は全て整数である。
- 2 \leq N \leq 50
- 1 \leq M \leq N(N-1)
- 1 \leq P \leq N
- 1 \leq S, T \leq N
- 1 \leq K \leq 10^9
- 1 \leq A_i , B_i \leq N (1 \leq i \leq M)
- A_i \neq B_i (1 \leq i \leq M)
- (A_i, B_i) \neq (A_j, B_j) (i \neq j)
- 1 \leq C_i \leq N (1 \leq i \leq P)
- 1 \leq D_i \leq 10^5 (1 \leq i \leq P)
- C_i \neq C_j (i \neq j)
- C_i = S となる i, C_j = T となる j が存在する。
小課題
この課題には 2 つの小課題があります。- (300 点) K \leq 20 を満たす。
- (700 点) 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられます。
N M P S T K A_1 B_1 A_2 B_2 ... A_M B_M C_1 D_1 C_2 D_2 ... C_P D_P
出力
条件を満たすルートの長さの最小値を出力してください。
もしそのようなルートが存在しない場合、代わりに -1 と出力してください。
入力例1
4 5 3 2 2 11 2 1 1 3 3 2 3 4 4 1 1 1 2 3 4 5
出力例1
6
以下のようなルートで移動するのが最適です。
- 町 2 から町 1 に移動する。嬉しさは |1-3|=2 増える。
- 町 1 から町 3 を経由して町 4 に移動する。嬉しさは |5-1|=4 増える。
- 町 4 から町 1 に移動する。嬉しさは |1-5|=4 増える。
- 町 1 から町 3 を経由して町 2 に移動する。嬉しさは |3-1|=2 増える。
入力例2
3 2 2 1 3 5 1 2 2 3 1 1 3 3
出力例2
-1
入力例3
6 7 4 1 6 14 1 2 2 3 3 4 4 5 5 1 6 1 2 6 1 1 3 2 5 7 6 4
出力例3
7
writer: autumn_eel
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
TMJN君はアニメが大好きです。
昨晩は、N 本のアニメを見る予定でした。アニメには 1 から N の番号が付けられており、i 番目のアニメの放映開始時刻は A_i、終了時刻は B_i です。
しかし、昨晩は疲れていたため、気が付いたら朝に！
そう、アニメを見ずに寝てしまったのです。
しかしご安心を、このTMJN君、時間遡行ができるのです！
そこで、時間遡行をして全てのアニメを鑑賞することにしました。しかし、時間遡行は体力の消耗が激しいので、なるべく遡る時間は短くしたいです。
さて、TMJN君が目覚めた現在時刻は T です。
TMJN君は瞬時にテレビのチャンネルを変えることができますが、同時に複数のアニメを鑑賞することはできません。
また、あるアニメの視聴を開始したら、そのアニメを最後まで鑑賞します。あるアニメの鑑賞中に他のアニメを見るためにチャンネルを切り替えることは絶対に行いません。
そのとき、TMJN君が遡る時間の合計の最小値と、それを達成するためのアニメを視聴する順番を出力してください。
制約
- 入力は全て整数である。
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^9
- 0 \leq A_i < B_i \leq T
小課題
この課題には 3 つの小課題があります。- (250 点) A_i \leq A_j < B_i である (i, j) (i ≠ j) の組が存在しない。すなわち 2 つのアニメが同時に放映されることはない。
- (250 点) A_1 = 0, B_1 = T を満たす。
- (500 点) 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられます。
N T
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}
A_N B_N
出力
N+1 行に渡って出力して下さい。
1 行目には遡る時間の合計の最小値を出力してください。
i+1 (1 \leq i \leq N) 行目には i 番目に視聴するアニメの番号を出力してください。
遡る時間の合計が最小となる答えが複数ある場合は、どれを出力しても構いません。
入力例1
3 141 5 9 26 53 58 97
出力例1
136 1 2 3
アニメ 1、アニメ 2、アニメ 3 の順に視聴した時、遡る時間の合計は 136 となります。
これより遡る時間の合計が短くなる視聴順は存在しません。
なお、この入力例は小課題 1 の制約を満たします。
入力例2
5 10 0 10 2 5 6 9 1 8 5 7
出力例2
25 2 5 3 4 1
例えば、アニメ 2、アニメ 5、アニメ 3、アニメ 4、アニメ 1 の順に視聴した時、遡る時間の合計は 25 となります。
これより遡る時間の合計が短くなる視聴順は存在しません。
なお、この入力例は小課題 2 の条件を満たします。
入力例3
7 30 1 15 23 25 13 21 0 5 18 20 4 11 19 22
出力例3
47 6 4 1 3 5 7 2
writer: TMJN
Time Limit: 1 sec / Memory Limit: 1024 MB
配点：1300 点
この問題はインタラクティブ問題ですので、通常の問題と形式が異なります。ご注意ください。
問題文
パ研王国には、N 個の都市があります。また、N - 1 本の双方向を繋ぐ道で結ばれており、これらの道のみを使って任意の都市から任意の都市までを移動することが出来ます。すなわち、パ研王国は「木構造」を成します。
また各都市には、都市を代表する建物が 1 個ずつあります。
さて、E869120 君はパ研王国の構造、すなわちパ研王国の各道がどの都市とどの都市の間を繋いでいるのかを知りたいですが、パ研王国は魔の手により封鎖されているため簡単に知る事は出来ません。
そこで、パ研王国の大統領である魔女の Segtree さんに以下の質問をすることによって、パ研王国の構造を知ろうとしました。
- 長さ N の順列 p を指定する。ここで、p は 1 以上 N 以下の値が 1 個ずつ含まれているものでなければならない。
- Segtree さんに魔力を使ってもらい、都市 i を代表する建物の高さを 2^{p_i - 1} に設定してもらう。
-
そして、0 以上 2^{N}-1 以下の値 x を指定し、以下の条件を満たす (u, v) (u < v) の組の個数 e を答えてもらう。
- u から v までの最短経路において、通る都市の建物の高さの合計が x 以上であるようなもの。
例えば、パ研王国が以下の図のような構造である場合において、p = {1, 5, 3, 4, 2}, x = 21 の場合、
- まず、各都市の建物の高さは下図の通り、{1, 16, 4, 8, 2} となります。
- よって、(u, v) = (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5) の 7 通りにおいて x \geq 21 の条件を満たすため、魔女の Segtree さんは7 を返します。
- 例えば、1 から 5 までの最短経路において通る都市の建物の高さの合計は、1 (都市 1) + 16 (都市 2) + 8 (都市 4) + 2 (都市 5) = 27 となり、21 以上であるため条件を満たします。
E869120 君は魔女の Segtree さんに質問しすぎると、パ研王国の軍隊に襲われる可能性が高まるため、出来るだけ少ない質問回数でパ研王国の構造を知りたいです。特に、3 \ 600 回を超えて質問した場合、軍隊だけでなく Segtree さんも怒り狂い、自動的に不正解となります。
ですが彼にとってこの問題は難しすぎて解けません。彼の代わりにできるだけ少ない質問回数で構造を当てるプログラムを作成して下さい。
制約
- 1 \leq N \leq 60
- パ研王国は連結な木構造を成す。つまり、任意の都市から任意の都市まで道を辿って行くことが出来る。
小課題
この課題には、2 個の小課題があります。- (100 点) N \leq 4 を満たす。
- (1200 点) 5 \leq N \leq 60 を満たす。
ただし、小課題 2 においては、質問回数の最大値 Q によって得点が決まります。
| 質問回数の最大値 Q | 小課題 2 の得点 (1 \ 200 点満点) |
|---|---|
| 2 \ 001 \leq Q \leq 3 \ 600 | 310 |
| 1 \ 721 \leq Q \leq 2 \ 000 | 420 |
| 1 \ 101 \leq Q \leq 1 \ 720 | 550 |
| 601 \leq Q \leq 1 \ 100 | 1 \ 200 - (Q - 600) |
| Q \leq 600 | 1 \ 200 |
入出力
この問題はインタラクティブ問題であるため、通常の入出力形式とは違います。ご注意ください。
(△) まず、ジャッジから都市の数 N を以下の形式で受け取ります。
N
次に、(☆) と (★) の入出力を、パ研王国の構造が分かるまで繰り返し行います。
(☆) 自分が魔女 (ジャッジ) に対して質問を以下の形式で行います。
? p_1 p_2 p_3 ... p_N x
このように、最初に '?' を出力し、その後 N + 1 個の整数を出力してください。その際、出力は ? を含め全て一行で行ってください。なお、p, x の値に関しては問題文を参照してください。
また、p は 1 以上 N 以下の値を 1 回ずつ含む順列である必要があり、x は 0 以上 2^{N}-1 以下の値である必要があります。
最後に改行を忘れないようにしてください。
(★) 魔女 (ジャッジ) が質問に対する回答を行います。
回答は、1 つの整数 e で表されます。ジャッジに質問をしたら、1 つの整数を受け取るようにしてください。
ただし、3 \ 600 回を超える質問をした場合、-1 という値を返します。この場合、直ちにプログラムを終了させてください。質問制限回数を超えた場合にプログラムを終了させたときの挙動は WA となりますが、プログラムを終了しない場合の挙動は定義されていません。
(◇) 答えとなるパ研王国の構造が分かったら、以下のように出力してください。
!
a_1 b_1
a_2 b_2
a_3 b_3
...
a_{N-1} b_{N-1}
このように、N 行に渡って出力してください。
ただし、a_i, b_i は、パ研王国の構造を表す値です。具体的には、i 本目の道路が a_i と b_i を結んでいるという事を指します。
道路を出力する順番はどれでも構いません。また、a_i, b_i の順番が逆でも構いません。例えば、パ研王国の道が (1, 2), (2, 3), (3, 4) であった時に、以下のような出力をしても正解となります。
3 2 1 2 4 3
注意
出力形式を間違えた場合のジャッジの挙動は不定です。(WA とは限りません。)
また、出力の最後に flush しなければならず、そうしない場合 TLE となる場合がございます。
E869120 君 は、3 \ 600 回を超える質問をしてはなりません。この回数の質問を超えてもなおプログラムを打ち切らない場合の挙動は不定です。
なお、AC となった場合でも満点が取れていない場合があることにご注意ください。小課題 1, 2 全てのテストケースにおいて 3 \ 600 回以内の質問で答えが求まれば、たとえ部分点であっても AC と出ます。
入出力例 1
この入力例は、N = 4 であり、パ研王国が以下のような構造である場合のジャッジ側とのやり取りの例である。
| 自分のプログラムへの入力（ジャッジ側の出力） | 自分のプログラムの出力 |
|---|---|
| 4 | |
| ? 1 2 3 4 8 | |
| 3 | |
| ? 4 3 2 1 15 | |
| 1 | |
|
! 1 2 2 4 1 3 |
writer: E869120