Codeforces Round #711 (Div. 2) 問題文和訳

A. GCD Sum (500点)
- 入力
- 出力
- 入出力例
- 注記
B. Box Fitting / Коробка (1000点)
- 入力
- 出力
- 入出力例
- 注記
C. Planar Reflections / Отражения от плоскостей (1750点)
- 入力
- 出力
- 入出力例
- 注記
D. Bananas in a Microwave / Бананы в микроволновке (2500点)
- 入力
- 出力
- 入出力例
- 注記
E. Two Houses / Два дома (2500点)
F. Christmas Game / Рождественская игра (3000点)
- 入力
- 出力
- 入出力例
- 注記

A. GCD Sum (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

正整数の $gcdSum$ とはその整数と、その各桁の和*1の $gcd$ です。形式的には、正整数 $x$ について $gcdSum(x) = gcd(x,\,x\,\text{の各桁の和})$ となります。 $gcd(a,\,b)$ は $a$ と $b$ の最大公約数、即ち、整数 $a$ と $b$ の両方が $d$ で割り切れるような最大の整数 $d$ のことです。

例: $gcdSum(762) = gcd(762,\,7 + 6 + 2) = gcd(762,\,15) = 3$

整数 $n$ が与えられるので $gcdSum(x) \gt 1$ を満たすような最小の整数 $x \geq n$ を求めてください。

入力

入力の1行目には単一の整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、これはテストケース数である。

その後、 $t$ 行が続き、各行には単一の整数 $n$ $(1 \leq n \leq 10^{18})$ が与えられる。

1つのテストにおいて全てのテストケースは異なるものである。

出力

$t$ 行を出力せよ、 $i$ 行目には $i$ 番目のテストケースの答えである単一の整数を出力せよ。

入出力例

12
33
75

注記

サンプルの3つのテストケースについて説明します。

テストケース1: $n = 11$ :
$gcdSum(11) = gcd(11,\,1 + 1) = gcd(11,\,2) = 1$
$gcdSum(12) = gcd(12,\,1 + 2) = gcd(12,\,3) = 3$
なので、 $gcdSum \gt 1$ である最小の整数 $\geq 11$ は $12$ です。

テストケース2: $n =31$ :
$gcdSum(31) = gcd(31,\,3 + 1) = gcd(31,\,4) = 1$
$gcdSum(32) = gcd(32,\,3 + 2) = gcd(32,\,5) = 1$
$gcdSum(33) = gcd(33,\,3 + 3) = gcd(33,\,6) = 3$
なので、 $gcdSum \gt 1$ である最小の整数 $\geq 31$ は $33$ です。

テストケース3: $n =75$ :
$gcdSum(75) = gcd(75,\,7 + 5) = gcd(75,\,12) = 3$
$75$ の $gcdSum$ はすでに $\gt 1$ です。そのため、これが答えです。

B. Box Fitting / Коробка (1000点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

高さ $1$ である長方形が $n$ 個与えられます。それぞれの長方形の幅は $2$ の累乗です(即ち、ある非負整数 $x$ について $2^x$ とあらわすことができる)。

また、幅 $W$ の2次元の箱が与えられます。 $W$ は $2$ の累乗であってもなくてもよいことに注意してください。さらに、 $W$ は最大の長方形の幅以上です。

与えられた長方形を全て収めることができるような、この箱の最小の高さを求めなければなりません。全ての長方形を収めた後に箱の中に空きスペースがあっても構いません。

箱に収めるために長方形を回転させることはできません。さらに、2つの異なる長方形は重なってはいけません、即ち、任意の2つの異なる長方形の交叉領域の面積は0でなければなりません。

サンプル入力の視覚的説明については注記を参照して下さい。

入力

入力の1行目には単一の整数 $t$ $(1 \leq t \leq 5 \cdot 10^3)$ が与えられる、これはテストケース数である。各テストケースは2行から成る。

各テストケースについて:

1行目には2つの整数 $n$ $(1 \leq n \leq 10^5)$ と $W$ $(1 \leq W \leq 10^9)$ が与えられる
2行目には $n$ 個の整数 $w_1,\,w_2,\,\dots,\,w_n$ $(1 \leq w_i \leq 10^6)$ が与えられる、ここで $w_i$ は $i$ 個目の長方形の幅である。各 $w_i$ は $2$ の累乗である。
さらに、 $\displaystyle \max_{i = 1}^{n} w_i \leq W$

全てのテストケースでの $n$ の和は $10^5$ を超えない。

出力

$t$ 個の整数を出力せよ。 $i$ 番目の整数は $i$ 個目のテストケースの答えであり、これは箱の最小の高さである。

入出力例

2
5 16
1 2 8 4 8
6 10
2 8 8 2 2 8

2
3

注記

サンプル入力の1つ目のテストケースについて、次の図は、与えられた5つの長方形を最小の高さの2次元の箱に収める方法の1つを示しています。

上図では、各長方形内部の数字がその幅を表しています。2次元の箱の幅は $16$ です(下の矢印で表されている)。このケースにおいて2次元の箱に必要な最小の高さは $2$ です(左に表されている)。

2つ目のテストケースでは、2つのブロック(幅8と2のもの)を3層のそれぞれに置くことで最小の高さの3にすることができます。

C. Planar Reflections / Отражения от плоскостей (1750点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

Gaurang*2は神秘的な宇宙で育ちました。彼の目の前には連なる $n$ 枚の2次元平面があります。彼は崩壊齢 $k$ の粒子を平面に向けて発射します。

粒子は平面を直接通過することができますが、各平面は崩壊齢 $k-1$ で反対方向に進む粒子である同一のコピーを生成します。崩壊齢が $1$ の粒子は、コピーを生成しません*3。

例えば、2枚の平面があり、粒子が崩壊齢 $3$ で(右方向に)発射された場合、次のようなプロセスになります(ここで、 $D(x)$ とは崩壊齢 $x$ の単一の粒子を表す)。

1枚目の平面が左向きに $D(2)$ を生成し、 $D(3)$ を右に通過させる
2枚目の平面が左向きに $D(2)$ を生成し、 $D(3)$ を右に通過させる
1枚目の平面が $D(2)$ を左に通過させ、左向きに $D(1)$ を生成する
2枚目の平面が $D(1)$ を右に通過させる( $D(1)$ はコピーを生成しない)

全体として、最終的な粒子の多重集合 $S$ は $\{D(3),\,D(2),\,D(2),\,D(1)\}$ になります(このテストケースの視覚的説明については注記を参照)。

平面の数が多すぎるとGaurangはこの複雑な状況に対応できません。 $n$ と $k$ が与えられるのでGaurangが多重集合 $S$ の大きさを求めるのを手助けをしてください。

多重集合の大きさは非常に大きくなる可能性があるため、modulo $10^9 + 7$ で出力しなければなりません。

注意: 粒子は互いに衝突することなく平面間を行き来することができます。

入力

入力の1行目には単一の整数 $t$ $(1 \leq t \leq 100)$ が与えられる、これはテストケース数である。その後、 $t$ 行が続き、各行には2つの整数 $n,\,k$ $(1 \leq n,\,k \leq 1000)$ が与えられる。

さらに、全てのテストケースでの $n$ の和は $1000$ を超えず、全てのテストケースでの $k$ の和は $1000$ を超えない。1つのテストにおいて全てのテストケースは異なるものである。

出力

$t$ 個の整数を出力せよ。 $i$ 番目の整数は $i$ 個目のテストケースの答えである。

入出力例

1
2
257950823

注記

1つ目の入出力例の4つのテストケースについて説明します。

テストケース1: $(n = 2,\,k = 3)$ は問題文で既に説明されています。

このシミュレーションである下図を参照してください。異なる色の各直線は異なる粒子の経路を表しています。ご覧のように、多重集合には4つの異なる粒子が属します。反射した粒子の間の縦方向の間隔は、見た目をわかりやすくするためだけのものであることに注意してください(前述のように、2つの異なる粒子が互いに衝突することはない)。

テストケース2: $(n = 2,\,k = 2)$ は以下のように説明されます。

1枚目の平面が左向きに $D(1)$ を生成し、 $D(2)$ を右に通過させる
2枚目の平面が左向きに $D(1)$ を生成し、 $D(2)$ を右に通過させる
2枚目の平面が $D(1)$ を左に通過させる( $D(1)$ はコピーを生成しない)

得られた多重集合 $\{D(1),\,D(1),\,D(2)\}$ の合計サイズは3です。

テストケース3: $(n = 3,\,k = 1)$ 平面は3枚ありますが、崩壊齢はたったの1です。ですので、1つの粒子が平面を通過するときに、新しいコピーは生成されません。よって、答えは1です。

テストケース4: $(n = 1,\,k = 3)$ 平面は1枚しかありません。粒子は左に新しいコピーを生成します。多重集合 $\{D(2),\,D(3)\}$ の大きさは2です。

D. Bananas in a Microwave / Бананы в микроволновке (2500点)

テストごとの時間制限: 3秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

調子の悪い電子レンジにバナナを入れようとしています。電子レンジが完全に壊れるまで　 $n$ 個のタイムステップがあります。各タイムステップにおいて、新しい操作が表示されます。

現在電子レンジの中にあるバナナの数を $k$ とします。初期状態では $k = 0$ です。 $i$ 番目の操作では入力に3つのパラメータ $t_i,\,x_i,\,y_i$ が与えられます。 $t_i$ の値に基づいて次のいずれかを行わなければなりません。

タイプ1: $(t_i = 1,\,x_i,\,y_i)$ — $0 \leq a_i \leq y_i$ であるような $a_i$ を選び、次の更新を $a_i$ 回行う: $k := \lceil (k + x_i) \rceil$

タイプ2: $(t_i = 1,\,x_i,\,y_i)$ — $0 \leq a_i \leq y_i$ であるような $a_i$ を選び、次の更新を $a_i$ 回行う: $k := \lceil (k \cdot x_i) \rceil$

$x_i$ は小数値でもよいことに注意してください。詳細は入力形式を参照してください。また、 $\lceil x \rceil$ は最小の整数 $\geq x$ のことです。

$i$ 個目のタイムステップでは、 $i$ 個目の操作をちょうど1度行わなければなりません。

$1 \leq j \leq m$ であるような各 $j$ についてちょうど $j$ 本のバナナを作ることができる最も早いタイムステップを出力してください。ちょうど $j$ 本のバナナを作ることができない場合、 $-1$ を出力してください。

入力

1行目にはスペースで区切られた2つの整数 $n$ $(1 \leq n \leq 200)$ と $m$ $(2 \leq m \leq 10^5)$ が与えられる。

その後、 $n$ 行が続き、その $i$ 行目は $i$ 個目のタイムステップを表す。このような各行には区切られた3つの整数 $t_i,\,x'_i,\,y_i$ $(1 \leq t_i \leq 2,$ $1 \leq y_i \leq m)$ が与えられる。

$x'_i$ が与えられていることに注意してください、これは $10^5 \cdot x_i$ である。従って $x_i$ を求めるには式 $\displaystyle x_i = \frac{x'_i}{10^5}$ を利用せよ。

タイプ1について $1 \leq x'_i \leq 10^5 \cdot m$ であり、タイプ2について $10^5 \lt x'_i \leq 10^5 \cdot m$ である。

出力

$m$ 個の整数を出力せよ、 $i$ 番目の整数はちょうど $i$ 本のバナナを得ることのできる最も早いタイムステップである(不可能な場合は $-1$ )。

入出力例

3 20
1 300000 2
2 400000 2
1 1000000 3

-1 -1 1 -1 -1 1 -1 -1 -1 3 -1 2 3 -1 -1 3 -1 -1 -1 3

3 20
1 399999 2
2 412345 2
1 1000001 3

-1 -1 -1 1 -1 -1 -1 1 -1 -1 3 -1 -1 -1 3 -1 2 -1 3 -1

注記

1つ目のサンプル入力で、3つのタイムステップで $16$ 本のバナナを作成する方法を見てみましょう。初期状態では $k=0$ です。

タイムステップ1では、 $a_1 = 2$ を選び、タイプ1の更新 $k := \lceil k + 3 \rceil$ を2回適用する。よって $k$ は6になる
タイムステップ2では、 $a_2 = 0$ を選ぶ。よって $k$ の値は変わらない
タイムステップ3では、 $a_3 = 1$ を選び、タイプ1の更新 $k := \lceil k + 10 \rceil$ を1回適用する。よって $k$ は16になる

与えられた操作では、3個未満のタイムステップで $k=16$ を達成することができないことは示すことができます。

2つ目のサンプル入力で、2つのタイムステップで $17$ 本のバナナを作成する方法を見てみましょう。初期状態では $k=0$ です。

タイムステップ1では、 $a_1 = 1$ を選び、タイプ1の更新 $k := \lceil k + 3.99999 \rceil$ を1回適用する。よって $k$ は4になる
タイムステップ2では、 $a_2 = 1$ を選び、タイプ2の更新 $k := \lceil k \cdot 4.12345 \rceil$ を1回適用する。よって $k$ は17になる

与えられた操作では、2個未満のタイムステップで $k=17$ を達成することができないことは示すことができます。

E. Two Houses / Два дома (2500点)

テストごとの時間制限: 3.5秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

この問題はインタラクティブ問題です。テストプログラムと通信しているときに出力をフラッシュすることを忘れないでください。出力のフラッシュにはC++ではfflush(stdout)、Javaではsystem.out.flush()、Pythonではstdout.flush()、Pascalではflush(output)を用いることができます。他のプログラミング言語を用いている場合はその言語のドキュメントを参照してください。また、インタラクティブ問題についてのガイド(https://codeforces.com/blog/entry/45307)を読むことをお勧めします。

Dixit*4はある都市に住んでいます。この都市には $n$ 軒の家があります。各家の組にはちょうど1本の有向の道があります。例えば、2軒の家AとBについて、AからBとBからAのどちらかの有向の道はありますが、その両方ではありません。 $i$ 番目の家に向かう道の本数を $k_i$ とします。

2軒の家AとBは、AからBへ到達可能であり、かつ、BからAへ到達可能であるとき、双方向到達可能です。家Aから家Bへのパスが存在する場合、家Bは家Aから到達可能であるといいます。

Dixitはこの都市に2軒の家、住むための家と勉強のための家を買おうと思っています。もちろん、彼は一方の家からもう一方の家へ移動したいと思っています。そこで彼は双方向到達可能な家AとBの組を求めたいと思っています。このような組の中で彼は $|k_A - k_B|$ の値が最大のものを選びたいと思っています、ここで $k_i$ は家 $i$ に向かう道の本数です。最適な組が複数存在する場合、そのいずれを選んでもよいです。

DixitはCodeCraft*5の準備で忙しいので、目的の家の組を見つけるのを手伝ってください、もしくはそのような家の組は存在しないといってあげてください。

問題の入力では、各道路の方向は与えられません。与えられるのは、各家についてその家に向かっている道の本数 $(k_i)$ だけです。

ジャッジへは1種類のみのクエリを投げることができます: 2軒の家AとBを与え、ジャッジはAからBは到達可能であるかどうかを答えます。クエリの回数には上限はありません。しかし、ジャッジが"Yes"と答えた後はさらにクエリを投げることはできません。また、同じクエリを2回投げることはできません。

全てのクエリが終わったら(もしくは、ジャッジがクエリに"Yes"と返したら)、プログラムは2軒の家についての推測を出力し、終了しなければなりません。

詳しくは相互入出力の項を参照してください。

入力

1行目には都市内の家の数を表す単一の整数 $n$ $(3 \leq n \leq 500)$ が与えられる。次の行には空白で区切られた $n$ 個の整数 $k_1,\,k_2,\,\dots,\,k_n$ $(0 \leq k_i \leq n - 1)$ が与えられる、 $i$ 個目の整数は $i$ 番目の家に向かっている道の本数を表している。

相互入出力

クエリを投げるには"? A B" $(1 \leq A,\,B \leq N,$ *6 $A \neq B)$ と出力せよ。ジャッジは家Aから家Bへ到達可能であれば"Yes"と、そうでなければ"No"と返答する。

最終的な答えを出力するには"! A B"と出力せよ、ここでAとBは $|k_A - k_B|$ の値が可能な最大値であり、双方向到達可能である。そのような家AとBの組が存在しない場合、"! 0 0"と出力せよ。

最終的な答えを出力した後、プログラムはすぐに終了しなければならない、そうしなければ、Wrong Answerという判定を得る。

同じクエリを2回投げることはできません。クエリの回数には上限はないが、ジャッジが"Yes"と答えた後はさらにクエリを投げることはできない。プログラムは最終的な答え("! A B"か"! 0 0")を出力して終了しなければならない。

間違った形式で質問をしたり、前の質問を繰り返したりすると、Wrong Answerという判定を得る。

クエリの出力後、改行出力、出力のflushを忘れないようにせよ。そうでなければIdleness limit exceededとなる。出力バッファのflushのためには次を利用せよ。

C++の場合、fflush(stdout)やcout.flush()
Javaの場合、System.out.flush()
Pascalの場合、flush(output)
Pythonの場合、stdout.flush()
他の言語の場合は、ドキュメントを参照せよ

入出力例

3
1 1 1
Yes

? 1 2
! 1 2

4
1 2 0 3
No
No
No
No
No
No

注記

1つ目のサンプル入力では、3軒の家があり、それぞれに1本の流入路がある都市が与えられます。ユーザープログラムは"? 1 2"というクエリで家 $1$ から家 $2$ に到達できるかどうかを尋ねます。ジャッジは"Yes"と答えます。ここでユーザプログラムは、これで正解を判断するのに十分な情報が得られたと判断します。そこで"! 1 2"と出力して終了します。

2つ目のサンプル入力では、ユーザープログラムは6つの異なる家のペアを問い合わせ、件の2軒の家がこの都市には存在しないと確信できるため最終的に"! 0 0"と答えます。

F. Christmas Game / Рождественская игра (3000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

AliceとBobはクリスマスを祝うためプレゼントの木を使って遊ぶことにしました。木には $n$ 個のノード( $1$ から $n$ までの番号が付いていて、 $r$ が根である)があります。 $i$ 個目のノードには $a_i$ 個のプレゼントがぶら下がっています。

ゲームが始まる前に特別な整数 $k$ が選ばれます。ゲームは次のように進行します。

Aliceがゲームを開始し、手番ごとに交互に行動する
どの手番においても、手番のプレイヤーは、深さが $k$ 以上であるノード(例えば $i$ ) を選ぶ。次にこのプレイヤーそのノードにぶら下がっているプレゼントを正整数だけ取り除く、この数を $m$ $(1 \leq m \leq a_i)$ とする
この $m$ 個のプレゼントを $i$ 番目のノードの $k$ 番目の祖先( $j$ とする)に置く(頂点 $i$ の $k$ 番目の祖先とは $i$ が $j$ の子孫であり、[tex;i] の深さと $j$ の深さの差がちょうど $k$ であるような頂点 $j$ のとである)。ここで $i$ 番目のノードのプレゼントの数 $(a_i)$ は $m$ だけ減少し、それに応じて $a_j$ は $m$ だけ増加する
AliceもBobも最適にプレイをする。手番を打てなくなったプレイヤーが負けです。