Educational Codeforces Round 107 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Educational Codeforces Round 和訳

A. Review Site / Сайт отзывов

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
貴方は将来の映画監督で、最初の映画を公開したところです。また、「いいね」と「ひどいね」の2つのボタンのついたシンプルなサイトを立ち上げました。

しかし、このサイトは内部的にはそれほど単純ではありません。サーバが2台あり、「いいね」と「ひどいね」をそれぞれのサーバが別々にカウントしています。

n 人のレビュアーが1人ずつサイトを訪れます。各レビュアーは以下のタイプのいずれかです。

  • タイプ 1: レビュアーは映画を見て気に入り、「いいね」ボタンを押す
  • タイプ 2: レビュアーは映画を見て気に入らず、「ひどいね」ボタンを押す
  • タイプ 3: レビュアーは映画を見ないで、自分のいるサーバの「いいね」と「ひどいね」の現在の数を見て、どちらのボタンを押すかを決める。「ひどいね」が「いいね」より多い場合、この映画に対して「ひどいね」を押す。そうでない場合、この映画に対して「いいね」を押す。

各レビュアーは1回のみ映画に対して評価を行います。

サーバが2つあるので、映画にできるだけ多くの「いいね」が付くように投票を操作することができます。レビュアーがサイトを訪れたときその人のタイプが分かるので、第1サーバに送るか第2サーバに送るかを選ぶことができます。

各レビュアーをどちらのサーバに送るかを決めたとき、両方のサーバで集められる「いいね」の合計値の最大値はいくらでしょう?

入力

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

その後、t 個のテストケースについての記述が続く。

各テストケースの1行目には単一の整数 n (1 \leq n \leq 50) が与えられる、これはレビュアーの人数である。

各テストケースの2行目には n 個の整数 r_1,\,r_2,\,\dots,\,r_n (1 \leq r_i \leq 13) が与えられる、これらはサイトを訪れる順に並べたレビュアーの種類である。

出力

各テストケースについて、単一の整数を出力せよ、その整数とは各レビュアをどちらのサーバーに送るかを決めたとき、両方のサーバで集められる「いいね」の合計値の最大値である。

入出力例

4
1
2
3
1 2 3
5
1 1 1 1 1
3
3 3 2
0
2
5
2

注記

入出力例の1つ目のテストケースでは、唯一のレビュアをどちらのサーバにも送ることができますが、どちらにしても「ひどいね」を押します。この映画は「いいね」の評価を受けません。

入出力例の2つ目のテストケースでは、レビュアーを全員第1サーバに送ることができます。

  • 1人目のレビュアーが「いいね」を押す
  • 2人目のレビュアーが「ひどいね」を押す
  • 最後のレビュアーが「ひどいね」が「いいね」を上回っていなことを確認し、「いいね」を押す

「いいね」は合計で2つです。別の方法として、1人目のレビュアーと2人目のレビュアーを第1サーバに、最後のレビュアーを第2サーバに送ることもできます。

  • 1人目のレビュアーが第1サーバで「いいね」を押す
  • 2人目のレビュアーが第1サーバで「ひどいね」を押す
  • 最後のレビュアーが第2サーバで「いいね」も「ひどいね」もないことを確認し、「いいね」を押す

B. GCD Length / Длина НОД

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
3つの整数 a,\,b,\,c が与えられます。

次の条件を満たす2つの正整数 x,\,y (x \gt 0, y \gt 0) を求めて下さい。

  • 先行ゼロを除いた x の十進数表現は a 桁である
  • 先行ゼロを除いた y の十進数表現は b 桁である
  • 先行ゼロを除いた gcd(x,\,y) の十進数表現は c 桁である

gcd(x,\,y) は整数 xと y の 最大公約数(greatest common divisor, GCD)*1を表します。

xと y を出力してください。答えが複数存在する場合、そのいずれかを出力してください。

入力

1行目には単一の整数 t (1 \leq t \leq 285) が与えられる、これはテストケースの個数である。

続く t 行のそれぞれには3つの整数 a,\,b,\,c (1 \leq a,\,b \leq 9, 1 \leq c \leq \min(a,\,b)) が与えられる、これらは数字の長さの条件である。

与えられた制約のもとで、全てのテストケースに対して答えが存在することは証明できる。

入力についての追加制約: 全てのテストケースは異なるものである。

出力

各テストケースについて2つの整数を出力せよ、その2つの整数は以下の条件を満たす x,\,y (x \gt 0, y \gt 0) である。

  • 先行ゼロを除いた x の十進数表現は a 桁である
  • 先行ゼロを除いた y の十進数表現は b 桁である
  • 先行ゼロを除いた gcd(x,\,y) の十進数表現は c 桁である

入出力例

4
2 3 1
2 2 2
6 6 2
1 1 1
11 492
13 26
140133 160776
1 1

注記

入出力例では次の通りになります。

  1. gcd(11,\,492) = 1
  2. gcd(13,\,26) = 13
  3. gcd(140133,\,160776) = 21
  4. gcd(1,\,1) = 1

C. Yet Another Card Deck / Очередная задача про колоду карт

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
上から下に番号が振られた n 枚のカードデッキがあります。つまり，一番上のカードのインデックスは 1で、一番下のカードのインデックスは n となります。各カードにはそれぞれの色があり、i 枚目の色は a_i です。

q 個のクエリを処理しなければなりません。j 番目のクエリは整数 t_j で表されます。各クエリについて次のようなことを行わなければなりません。

  • デッキ内で色 t_j である最も上のカード、即ち、最小のインデックスを持つカードを見つける
  • 見つけたカードの位置を出力する
  • そのカードを取り出し、デッキの一番上に置く

入力

1行目には2つの整数 n,\,q (2 \leq n \leq 3 \cdot 10^5; 1 \leq q \leq 3 \cdot 10^5) が与えられる、これらはデッキ内のカードの枚数とクエリの個数である。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 50) が与えられる、これらはカードの色である。

3行目には q 個の整数 t_1,\,t_2,\,\dots,\,t_q (1 \leq t_j \leq 50) が与えられる、これらはクエリの色である。クエリではデッキ内に存在する色のみを尋ねられることは保証される。

出力

q 個の整数を出力せよ、それらは各クエリに対する答えである。

入出力例

7 5
2 1 1 4 3 3 1
3 2 1 1 4
5 2 3 1 5

注記

入出力例の説明:

  1. デッキは [2,\,1,\,1,\,4,\,\underline{3},\,3,\,1] で、色 t_1 = 3 である最初のカードの位置は 5 である。
  2. デッキは [3,\,\underline{2},\,1,\,1,\,4,\,3,\,1] で、色 t_2 = 2 である最初のカードの位置は 2 である。
  3. デッキは [2,\,3,\,\underline{1},\,1,\,4,\,3,\,1] で、色 t_3 = 1 である最初のカードの位置は 3 である。
  4. デッキは [\underline{1},\,2,\,3,\,1,\,4,\,3,\,1] で、色 t_4 = 1 である最初のカードの位置は 1 である。
  5. デッキは [1,\,2,\,3,\,1,\,\underline{4},\,3,\,1] で、色 t_5 = 4 である最初のカードの位置は 5 である。

D. Min Cost String / Строка минимальной стоимости

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
文字列 s のコストを s_i = s_j かつ s_{i+1} = s_{j+1} を満たすインデックスの組 i,\,j (1 \leq i \lt j \leq |s|) の個数と定義しましょう。

2つの正整数 n,\,k が与えられます。ラテン文字の最初の k 文字のみを含む長さ n の全ての文字列の中で、可能な限り最小コストの文字列を求めて下さい。そのような最小コストの文字列が複数存在する場合は、そのいずれかを出力してください。

入力

唯一の行には2つの整数 n,\,k (1 \leq n \leq 2 \cdot 10^5; 1 \leq k \leq 26) が与えられる。

出力

n 文字で構成され、その各文字がラテン文字の最初の k 文字のうちの1つであり、これらの文字列の中でコストが最小となるような文字列 s を出力せよ。このような文字列が複数ある場合は、そのうちのいずれかを出力せよ。

入出力例

9 4
aabacadbb
5 1
aaaaa
10 26
codeforces

E. Colorings and Dominoes / Раскраски и домино

テストごとの時間制限: 3秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
n \times m 個のセルに分割されている大きな長方形のボードがあります(n 行 m 列)。各セルは白か黒です。

各白セルを赤か青で塗ります。自明ですが、白セルの数を w とすると塗り方は 2^w 通りあります。

ボード上の白セルを塗ったのち、次のようなルールに従って最大数のドミノを置いていきます。

  • 各ドミノは隣接する2つのセルを覆う
  • 各セルは高々1枚のドミノで覆われる
  • ドミノを横向きに置いた(1行の2つセルを覆う)場合、赤セルのみを覆う
  • ドミノを縦向きに置いた(1列の2つセルを覆う)場合、青セルのみを覆う

ボードの値を置くことができるドミノの最大枚数とします。可能な 2^w 通りの塗り方全てについての値の合計を計算してください。個の和が巨大になる可能性があるので、modulo 998\,244\,353 で出力してください。

入力

1行目には2つの整数 n,\,m (1 \leq n,\,m \leq 3 \cdot 10^5; nm \leq 3 \cdot 10^5) が与えられる、これらはそれぞれ行と列の数である。

そののち、n 行が続き、各行には m 文字の文字列が与えられる。i 個目の文字列の j 文字目は i 行目の j 番目のセルが黒のとき *、そうでないときoである。

出力

1つの整数を出力せよ、その数とは可能な 2^w 通りの塗り方についてボードの値の和を 998\,244\,353 で割った余りである。

入出力例

3 4
**oo
oo*o
**oo
144
3 4
**oo
oo**
**oo
48
2 2
oo
o*
4
1 4
oooo
9

F. Chainword / Чайнворд

テストごとの時間制限: 3秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
チェーンワードはクロスワードの特殊な種類です。大体のクロスワードと同様に、文字を入れるセルと、その文字が何であるかを示すヒントがあります。

チェーンワードの文字セルは1列に並べられています。この課題では長さ m のチェーンワードを考えます。

チェーンワードのヒントとは、互いに交差せず、m 個の文字セルを全てカバーするような、一連のセグメントのことです。各セグメントには、対応するセルにある単語の説明が含まれています。

奇妙なことに実際にはヒントは2つあります: 1つは文字セルの上の行のセグメント列で、もう1つは文字セルの下の行のセグメント列です。列が異なる場合は、答えの曖昧さを解消するのに役立っています。

n 単語の辞書が当たられます、各語は小文字のラテン文字から成ります。全ての語は互いに相異なります。

チェーンワードのインスタンスは次のような3つ組です。

  • m 文字の小文字のラテン文字の文字列
  • 第1ヒント: 各セグメントに対応する文字が辞書内の単語となるようなセグメント列
  • 第2ヒント: 各セグメントに対応する文字が辞書内の単語となるような別のセグメント列

セグメント列は必ずしも異なるものである必要はないことに注意してください。

チェーンワードの2つのインスタンスは、異なる文字列または異なる第1ヒントまたは異なる第2ヒントを持つ場合、異なるものと見做されます。

チェーンワードの異なるインスタンスの数を数えます。この数はかなり大きくなるかもしれないので、modulo 998\,244\,353 で出力してください。

入力

1行目には2つの整数 n,\,m (1 \leq n \leq 8, 1 \leq m \leq 10^9) が与えられる、これらは辞書の単語数と文字セルの数である。

続くn 行のそれぞれには単語が与えられる、これらは小文字のラテン文字 5 文字以内の空でない文字列である。全ての単語は互いに異なる。

出力

1つの整数を出力せよ、与えられた辞書に対する長さ m の異なるチェーンワードのインスタンスの数を 998\,244\,353 で割った余りである。

入出力例

3 5
ababa
ab
a
11
2 4
ab
cd
4
5 100
a
aa
aaa
aaaa
aaaaa
142528942

注記

ここにあるのは、1つ目の入出力例についての有効なチェーンワードの全てのインスタンスです。
f:id:Flkanjin:20210413181239p:plain
文字の上の赤い線は第1ヒントのセグメントを、文字の下の青い線は第2ヒントのセグメントを示しています。

2つ目の入出力例では、以下の文字列が考えられます: "abab", "abcd", "cdab", "cdcd"。ヒントは全て、最初の2文字と最後の2文字をカバーするセグメントです。

G. Chips on a Board / Фишки на доске

テストごとの時間制限: 5秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
AliceとBobは n 行 m 列から成る長方形のボードを持っています。各行にはチップがちょうど1枚置かれています。

AliceとBobは次のようなゲームをします。2人は 1 \leq l \leq r \leq m である2整数 l,\,r を選び、列 lから列 r まで(区間の両端を含む)の部分のみが残るようにボードを切ります。つまり、列 l より左にある全ての列と列 r より右にある全ての列はもはやボードの一部ではなくなります。

ボードを切った後、ボードの残った部分(列 lから列 r までの部分)のチップを移動させます。交互に手を打ち、手を打てなかったプレイヤーがゲームに負けます。1手目はAlice、2手目はBob、3手目はAliceというように進行します。手を打つ際、プレイヤーはボード上のチップを1つ選び、任意の正の数のセル分左に移動させなければなりません(つまり、列 i にあったチップは列 j \lt i に移動させることができ、一番左の列にあるチップは選べない)。

AliceとBobは数の組 L_i,\,R_i を q 組持っています。そのような各ペアについて、l = L_i, r = R_i としたときに、どちらがゲームの勝者になるかを判別したいと思っています。これらのゲームは独立である(次のゲームのボードの状態には影響を与えない)と考えられ、AliceもBobも最適なプレーを行います。

入力

1行目には2つの整数 n,\,m (1 \leq n,\,m \leq 2 \cdot 10^5) が与えられる、これらはそれぞれ行と列の数である。

2行目には n 個の整数 c_1,\,c_2,\,\dots,\,c_n (1 \leq c_i \leq m) が与えられる、ここで c_i は i 行目のチップのある列のインデックスである(つまり、i 行目のチップは c_i 列目にある)。

3行目には1つの整数 q (1 \leq q \leq 2 \cdot 10^5) が与えられる。

そののち、q 行が続き、その i 行目には2つの整数 L_i,\,R_i (1 \leq L_i \leq R_i \leq 2 \cdot m) が与えられる。

出力

q 文字の文字列を出力せよ。 i 文字目は、l = L_i, r = R_i のゲームでAliceが勝った場合はA、Bobが勝った場合はBとする。

入出力例

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

*1:原文では英語、ロシア語のWikipediaへのリンク

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

Codeforces 競技プログラミング Codeforces 和訳 Codeforces Div. 2 和訳

A. Array and Peaks / Массив и пики (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n 整数の列は 1 から n までの全ての整数をちょうど1個ずつ含むとき順列と呼ばれます。

2つの整数 n,\,k が与えられるので、ちょうど k 個のピークをもつ 1 から n までの数の順列 a を構築してください。大きさ n の配列 a のインデックス i は 1 \lt i \lt n かつ a_i \gt a_{i-1} かつ a_i \gt a_{i+1} であるとき、ピークといいます。そのような順列が存在しない場合は、-1 と出力してください。

入力

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

それから t 行が続き、そのそれぞれには空白で区切られた2つの整数 n (1 \leq n \leq 100), k (0 \leq k \leq n) が与えられる、これらは配列の長さとピークの数である。

出力

t 行出力せよ。各テストケースについて、与えられた長さとピークの数を持つ順列がない場合は、-1 と出力せよ。そうでない場合は、1 から n までの数の順列を形成し、ちょうど k 個のピークを持つような空白で区切られた n 個の整数を1行に出力せよ。

答えが複数存在する場合、そのいずれかを出力せよ。

入出力例

5
1 0
5 2
6 6
2 1
6 1
1 
2 4 1 5 3 
-1
-1
1 3 6 5 4 2

注記

入出力例の2つ目のテストケースでは、配列 a = [2,\,4,\,1,\,5,\,3] となります。ここでインデックス i = 2 と i = 4 がピークとなります。これは (a_2 \gt a_1, a_2 \gt a_3) で、 (a_4 \gt a_3, a_4 \gt a_5) であるからです。

B. AND Sequences / Последовательности И (1250点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n (n \geq 2) 個の非負整数の列 a_1,\,a_2,\,\dots,\,a_n は 1 から n-1 までの全ての i について次の条件が成立するとき、よい配列という。
a_1 \: \& \: a_2 \: \& \: \dots \: \& \: a_i = a_{i+1} \: \& \: a_{i+2} \: \& \: \dots \: \& \: a_n
ここで、\& はビットAND*1を表します。

大きさ n (n \geq 2) の配列 a が与えられます。列 a_{p_1},\,a_{p_2},\,\dots,\,a_{p_n} がよい配列となるような 1 から n までの数の順列 p の個数を求めて下さい。この数は大きくなる可能性があるので、modulo 10^9 + 7 で出力してください。

入力

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

各テストケースの1行目には単一の整数 n (2 \leq n \leq 2 \cdot 10^5) が与えられる、これは配列の大きさである。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (0 \leq a_i \leq 10^9) が与えられる、これらは配列の要素である。

全てのテストケースでの nの和が 2 \cdot 10^5 を超えないことは保証されている。

出力

t 行出力せよ、ここで、i 行目には i 番目のテストケースでの良い順列の個数を 10^9 + 7 で割った余りを出力せよ。

入出力例

4
3
1 1 1
5
1 2 3 4 5
5
0 2 0 3 0
4
1 3 5 1
6
0
36
4

注記

1つ目のテストケースでは、全ての数が同じなので、どのような順列をとっても良い配列になります。1 から 3 までの数の順列は次のように合計で 6 通り存在します: [1,\,2,\,3], [1,\,3,\,2], [2,\,1,\,3], [2,\,3,\,1], [3,\,1,\,2], [3,\,2,\,1]。

2つ目のテストケースでは、よい配列となるような順列が存在しないことを証明することができます。

3つ目のテストケースでは、よい配列となるような順列が合計で 36 通り存在しますそのうち1つが順列 [1,\,5,\,4,\,2,\,3] であり、このとき列は s = [0,\,0,\,3,\,2,\,0]となります。これがよい配列となるのは以下の通りです。

  • s_1 = s_2 \: \& \: s_3 \: \& \: s_4 \: \& \: s_5 = 0
  • s_1 \: \& \: s_2 = s_3 \: \& \: s_4 \: \& \: s_5 = 0
  • s_1 \: \& \: s_2 \: \& \: s_3 = s_4 \: \& \: s_5 = 0
  • s_1 \: \& \: s_2 \: \& \: s_3 \: \& \: s_4 = s_5 = 0

Add One / Добавь единицу (1500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
整数 n が与えられます。それに m 回操作を適用させなければなりません。

1回の操作では、数の各桁 d を d+1 の十進数表現に置き換えなければなりません。例えば、1912 は1回の操作を適用させると 21023 となります。

m 回の操作を適応させた後の n の長さを求めなければなりません。この数は大きくなる可能性があるので、modulo 10^9 + 7 で出力してください。

入力

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

各テストケースの唯一の行には2つの整数 n (1 \leq n \leq10^9, [tex:m (1 \leq m \leq 2 \times 10^5) が与えられる、これらは初期状態の数と操作回数である。

出力

各テストケースについて結果として得られる数の長さを 10^9 + 7 で割った余りを出力せよ。

入出力例

5
1912 1
5 6
999 1
88 2
12 100
5
2
6
4
2115

注記

1つ目のテストケースについて、1912 は 1 回の操作の後 21023 となり、その長さは 5 となります。

2つ目のテストケースについて、5 は 6 回の操作の後 21 となり、その長さは 2 となります。

3つ目のテストケースについて、999 は 1 回の操作の後 101010 となり、その長さは 6 となります。

4つ目のテストケースについて、88 は 2 回の操作の後 1010 となり、その長さは 4 となります。

D. GCD and MST / НОД и МОД (2000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n (n \geq 2) 個の正整数から成る配列 a と整数 p が与えられます。頂点 i と j (i \lt j) の間の辺が次のようにして追加される 1 から n までの番号がついた n 個の頂点からなる重み付き無向グラフを考えます。

  • gcd(a_i,\,a_{i+1},\,a_{i+2},\,\dots,\,a_j) = min(a_i,\,a_{i+1},\,a_{i+2},\,\dots,\,a_j) である場合、i から j の間に重さ min(a_i,\,a_{i+1},\,a_{i+2},\,\dots,\,a_j) の辺が存在する
  • i + 1 = j である場合、i と j の間に重さ p の辺が存在する

ここで gcd(x,\,y,\,\dots) は整数 x,\,y,\,\dots の最大公約数(greatest common divisor, GCD)*2を表します。

上記の条件の両方を満たす場合、i と j の間には多重辺が存在し、何方の条件も満たさない場合、i と j の間には辺が存在しないことに注意してください。

目標は、このグラフの最小全域木(minimum spanning tree, MST)*3の重みを求めることです。

入力

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

各テストケースの1行目には2つの整数 n (2 \leq n \leq 2 \cdot 10^5), p (1 \leq p \leq 10^9) が与えられる、これらは頂点数とパラメータ p である。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,a_3,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる、これらは配列の要素である。

全てのテストケースでの nの和が 2 \cdot 10^5 を超えないことは保証されている。

出力

t 行出力せよ。各テストケースでについて対応するグラフの重さを出力せよ。

入出力例

4
2 5
10 10
2 5
3 3
4 5
5 2 4 9
8 8
5 3 3 6 10 100 9 15
5
3
12
46

注記

ここでは、例題の4つのテストケースのグラフを示しています(グラフの可能なMSTの辺はピンク色で示されています)。
テストケース1について
f:id:Flkanjin:20210412183948p:plain
テストケース2について
f:id:Flkanjin:20210412184017p:plain
テストケース3について
f:id:Flkanjin:20210412184118p:plain
テストケース4について
f:id:Flkanjin:20210412184143p:plain

E. Cost Equilibrium / Ценовой баланс (2750点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
配列の全ての要素が等しい場合、その配列は美しいといいます。

以下の手順で、配列を任意の回数変換することができます。

  1. 2つのインデックス i,\,j (1 \leq i,\,j \leq n) と整数 x (1 \leq x \leq a_i) を選ぶ。i をソースインデックス、j をシンクインデックスとする
  2. i 番目の要素を x だけ減らし、j 番目の要素を x だけ増やす。i 番目と j 番目で得られる値はそれぞれ a_i - x, a_j + x となる
  3. この操作のコストは x \cdot |j - i| である
  4. ここで、i がシンクインデックス、j がソースインデックスになることはなくなる

変換の総コストはステップ 3 の全てのコストの合計です。
例えば、配列 [0,\,2,\,3,\,3] は総コスト 1 \cdot |1-3| + 1 \cdot |1-4| = 5 で美しい配列 [2,\,2,\,2,\,2] に変換できます。

美しい配列に変換することができ、その変換のコストが一意に定まる配列をバランス型といいます。言い換えれば、美しい配列に変換するための最小のコストは、最大のコストに等しいものです。

非負整数から成る長さ n の配列 a_1,\,a_2,\,\dots,\,a_n が与えられます。貴方の仕事は、与えられた配列の並べ替えであるバランス型の配列の数を求めることです。要素が異なる位置が存在する場合2つの配列は異なる配列とみなされます。答えが大きくなる可能性があるため、modulo 10^9+7 で出力して下さい。

入力

1行目には単一の整数 n (1 \leq n \leq 10^5) が与えられる、これは配列の大きさである。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (0 \leq a_i \leq 10^9) が与えられる。

出力

単一の整数を出力せよ、これはバランス型である並び替えの数を 10^9 + 7 で割った余りである。

入出力例

3
1 2 3
6
4
0 4 0 4
2
5
0 11 12 13 14
120

注記

1つ目の入出力例では、値 3 のインデックスをソース、値 1 のインデックスをシンクと考えることができるので、[1,\,2,\,3] は有効な並び替えです。したがって、変換後は美しい配列 [2,\,2,\,2] となり，総コストは 2 となります。これが美しい配列になる唯一の変換であることを示すことができます。同様に他の並び替えについても調べることができます。

2つ目の入出力例では、[0,\,0,\,4,\,4] と [4,\,4,\,0,\,0] がバランス型である並び替えです。

3つ目の入出力例では、すべての並び替えがバランス型です。

F. Swapping Problem / Задача об обмене (3500点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
大きさ n の2つの配列 a,\,b が与えられます。b の2つの要素を最大1回だけ入れ替える(またはそのままにする)ことができ、次の値を最小化しなければなりません。
\displaystyle \sum_{i} |a_i - b_i|
この和の可能な最小値を求めて下さい。

入力

1行目には単一の整数 n (1 \leq n \leq 2 \cdot 10^5) が与えられる。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる。

3行目には n 個の整数 b_1,\,b_2,\,\dots,\,b_n (1 \leq b_i \leq 10^9) が与えられる。

出力

\displaystyle \sum_{i} |a_i - b_i| の最小値を出力せよ。

入出力例

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

注記

1つ目の入出力例では、配列 b の1番目と5番目の要素を入れ替えて [5,\,2,\,3,\,4,\,1] にすることができます。

従ってその和の可能な最小値は |5-5| + |4-2| + |3-3| + |2-4| + |1-1| = 4 となります。

2つ目の入出力例では、1番目と2番目の要素を入れ替えることができます。つまり、答えは 2 となります。

*1:原文では英語、ロシア語のWikipediaへのリンク

*2:これも原文では英語、ロシア語のWikipediaへのリンク

*3:英語、ロシア語のWikipediaの最小全域木のページへのリンク

AtCoder Beginner Contest 198のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

AtCoder Beginner Contest 198に参加、レートが+1されました。

A - Div (100点)

A君が x 個貰うとすると、B君は N-x 個貰うことになるので 1 \leq x \leq N かつ 1 \leq N-x \leq N より N \geq 2 のとき 1 \leq x \leq N-1 よりx は整数であるため N-1 通り存在します。N=1 のとき条件を満たす分け方は存在しないので、どちらの場合も N - 1 通りとなります。

B - Palindrome with leading zeros (200点)

N = 0 でない限り先頭に0はもともと来ないので末尾の0を削除した文字列が回文なら条件を満たし、そうでなければ条件を満たしません。
文字列が条件を満たしているかどうかは実際に両端から文字が等しいかどうか調べることで判別できます。

C - Compass Walking (300点)

1 歩移動後に高橋くんがいる点の集合は半径 R の円周となります。
そのあともう 1 歩移動することで、

R\begin{pmatrix} \cos\alpha \\ \sin\alpha \\ \end{pmatrix} + R\begin{pmatrix} \cos\beta \\ \sin\beta \\ \end{pmatrix} = \displaystyle 2R \cos\frac{\alpha-\beta}{2} \begin{pmatrix} \cos\dfrac{\alpha+\beta}{2} \\ \sin\dfrac{\alpha+\beta}{2}\\ \end{pmatrix}
となり、\alpha+\beta と \alpha-\beta の組は \mathbb{R}^2 の全域を動くことができるため点の集合は半径 2R の円周及び内部になります。
これ以降は、数学的帰納法により、i\,(\geq 2) 歩移動後の点の集合は半径 iR の円周及び内部となります。
よって、原点から (X,\,Y) の距離が R の時は答え 1、R 未満の時は答え 2、それ以外の時は答え \displaystyle \left\lceil \frac{距離}{R} \right\rceil となります。
誤差が怖かったのでfor文を用いて条件を求めましたが、繰り返し回数を 100\,000 回にしていたため、1つのケースを落としてしまい、2ペナとなってしまいました。上限は R = 1, (X,\,Y) = (100\,000,\,100\,000) のときの 141\,422 となります。

D - Send More Money (400点、実行時間制限: 5 sec)

最初、覆面算 S_1 + S_2 = S_3 という条件を見落としていて1ペナついてしまいました(問題名の意味を考えれば...)。
文字と数字が対応するため 11 種類以上の文字を用いている場合、UNSOLVABLEとなります。
そうでない場合、文字と数字の対応を全て試してみます。高々 10! = 3\,828\,800 通りなので間に合います。std::next_permutaionを用います。1 文字目が0でないか、stollを用いてN_1 + N_2 = N_3 が成り立っているかどうかを判別しましょう。

E - Unique Color (500点)

根からDFSしていきます。答えをstd::setを用いてとっていく場合は、マージテクを用いるようにしましょう。そうでなければ O(N^2) になってTLEしてしまいます(1敗)。

F - Cube (600点): 未提出

色々回してよく分からなくなりました。

結果、感想

f:id:Flkanjin:20210412162529p:plain
本当にギリギリ暖まりました。4ペナが痛い...

Codeforces Round #713 (Div. 3) 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Codeforces Div. 3 和訳

A. Spy Detected! / Шпион обнаружен!

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n (n \geq 3) 個の正整数から成る配列 a が与えられます。この配列では、1つを除いて全ての数字が同じであることが知られています(例えば、配列 [4,\,11,\,4,\,4] では1つを除く全ての数字が 4 に等しい)。

残りの要素と等しくない要素のインデックスを出力して下さい。配列内の数字は1から順に番号が振られています。

入力

1行目には単一の整数 t (1 \leq t \leq 100) が与えられる。そののち t 個のテストケースが続く。

各テストケースの1行目には単一の整数 n (3 \leq n \leq 100) が与えられる、これは配列 a の長さである。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 100) が与えられる。

配列 a の中の1つを除く全ての数字が同じであることは保証されている。

出力

各テストケースについて単一の整数を出力せよ、その整数とは他の要素と等しくない要素のインデックスである。

入出力例

4
4
11 13 11 11
5
1 4 4 4 4
10
3 3 3 3 10 3 3 3 3 3
3
20 20 10
2
1
5
3

B. Almost Rectangle / Почти прямоугольник

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
大きさ n \times n の正方形の領域があり、そのうち2つのセルにマークがされています。これらのセルは同じ行でも同じ列でも構いません。

座標軸に平行な辺を持つ長方形の角になるようにさらに2つのセルをマークしなければなりません。

例えば、n = 4 で、長方形の領域が次のような場合(マークされたセルにはアスタリスクが書かれている)、

\begin{matrix} . & . & * & . \\ . & . & . & . \\ * & . & . & . \\ . & . & . & . \\ \end{matrix}
次のようにさらに2つのセルをマークすることができます。
\begin{matrix} * & . & * & . \\ . & . & . & . \\ * & . & * & . \\ . & . & . & . \\ \end{matrix}
可能な解が複数存在する場合、そのいずれかを出力してください。

入力

1行目には単一の整数 t (1 \leq t \leq 400) が与えられる。そののち t 個のテストケースが続く。

各テストケースの1行目には単一の整数 n (2 \leq n \leq 400) が与えられる、これは表の行や列の個数である。

続く n 行のそれぞれには空のセルとマークされたセルを表す'.'と'*'のn 文字が与えられる。

全てのテストケースでの n の和が 400 を超えないことは保証されている。

領域内位にちょうど2つのアスタリスクがあることは保証されている。これらは同じ行/列にあっても構わない。

解が存在することは保証されている。

出力

各テストケースについて n 文字を n 行出力せよ、これらは問題文に対応した、4つのアスタリスクのある領域である。正解が複数ある場合、そのいずれかを出力せよ。

入出力例

6
4
..*.
....
*...
....
2
*.
.*
2
.*
.*
3
*.*
...
...
5
.....
..*..
.....
.*...
.....
4
....
....
*...
*...
*.*.
....
*.*.
....
**
**
**
**
*.*
*.*
...
.....
.**..
.....
.**..
.....
....
....
**..
**..

C. A-B Palindrome / A-B палиндром

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
文字'0', '1', '?'から成る文字列 s が与えられます。文字列が回文になり、ちょうど a 文字の'0'とちょうど b 文字の'1'をもつように文字列 s 内の全ての'?'を'0'や'1'に置換しなければなりません。文字'?'のそれぞれは他とは独立に置換されることに注意してください。

長さ n の文字列 t は全ての i (1 \leq i \leq n) について等式 t[i] = t[n-i+1] が真である場合、回文と言います。

例えば、s = "01?????0",\,a = 4, b = 4 の場合、次のように文字'?'を置換することができます。

  • "01011010"
  • "01100110"

与えられた文字列 s と数 a と b について、文字列が回文になり、ちょうど a 文字の'0'とちょうど b 文字の'1'をもつように文字列 s 内の全ての'?'を'0'や'1'に置換してください。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる。そののち t 個のテストケースが続く。

各テストケースの1行目には2つの整数 a,\,b (0 \leq a,\,b \leq 2 \cdot 10^5, a + b \geq 1) が与えられる。

各テストケースの2行目には文字'0', '1', '?'から成る長さ a + b の文字列 s が与えられる。

全てのテストケースでの s の文字列長の合計が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて次のように出力せよ。

  • 文字列が回文になり、ちょうど a 文字の'0'とちょうど b 文字の'1'をもつように文字列 s 内の全ての'?'を'0'や'1'に置換できない場合、"-1"
  • そうでない場合、置換の結果得られる文字列

文字の置換について適す方法がいくつかある場合、そのいずれかを出力せよ。

入出力例

9
4 4
01?????0
3 3
??????
1 0
?
2 2
0101
2 2
01?0
0 1
0
0 3
1?1
2 2
?00?
4 3
??010?0
01011010
-1
0
-1
0110
-1
111
1001
0101010

D. Corrupted Array / Испорченный массив

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
数 n と以下のアルゴリズムによって得られた配列 b_1,\,b_2,\,\dots,\,b_{n+2} が与えられます。

  • ある配列 a_1,\,a_2,\,\dots,\,a_n が与えられる
  • 配列 a を配列 b に書き込む、即ち b_i = a_i (1 \leq i \leq n)
  • 配列 b の (n+1) 番目の要素は配列 a の数値の合計である、即ち b_{n+1} = a_1 + a_2 + \dots + a_n
  • 配列 b の (n+2) 番目の要素にある整数 x (1 \leq x \leq 10^9)を書き込む、即ち b_{n+2} = x
  • 配列 b をシャッフルする

例えば、配列 b = [2,\,3,\,7,\,12,\,2] は次のようにして得ることができます。

  • a = [2,\,2,\,3], x = 12
  • a = [3,\,2,\,7], x = 2

与えれた配列 b について、最初に与えられた可能性のある配列 a のいずれかを求めて下さい。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる。そののち t 個のテストケースが続く。

各テストケースの1行目には単一の整数 n (0 \leq n \leq 2 \cdot 10^5) が与えられる。

各テストケースの2行目には n+2 個の整数 b_1,\,b_2,\,\dots,\,b_{n+2} (1 \leq b_i \leq 10^9) が与えられる。

全てのテストケースでの n の和が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて次のように出力せよ。

  • 配列 b がどんな配列 a からも得られない場合、"-1"
  • そうでない場合、n 個の整数 a_1,\,a_2,\,\dots,\,a_n

複数の配列 a が存在する場合、そのいずれかを出力せよ。

入出力例

4
3
2 3 7 12 2
4
9 1 7 1 6 5
5
18 2 2 3 2 9 2
3
2 6 9 2 1
2 3 7 
-1
2 2 2 3 9 
1 2 6

E. Permutation by Sum / Перестановка по сумме

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
順列とは 1 から n までの n 個の整数の列であり、全ての数がちょうど1度ずつ現れるような列のことです。例えば、[1], [3,\,5,\,2,\,1,\,4], [1,\,3,\,2] は順列ですが、[2,\,3,\,2], [4,\,3,\,1], [0] は順列ではありません。

Поликарп*1は4つの整数 n,\,l,\,r (1 \leq l \leq r \leq n), s \displaystyle \left(1 \leq s \leq \frac{n(n+1)}{2}\right) が与えられ、次の条件を満たすような 1 から n までの数の順列 p を求めるように頼まれました。

  • s = p_l + p_{l+1} + \dots + p_r

例えば、n = 5, l = 3, r = 5, s = 8 の場合、次のような順列が適します(全ての選択肢が記載されているわけではない)。

  • p = [3,\,4,\,5,\,2,\,1]
  • p = [5,\,2,\,4,\,3,\,1]
  • p = [5,\,2,\,1,\,3,\,4]

しかしn = 4, l = 1, r = 1, s = 5 については上記の条件に適すような順列は存在しません。

与えられた n,\,l,\,r,\,s について上記の条件に合うような 1 から n の数の順列を求めるПоликарпの手助けをしてください。適当な順列が複数存在する場合、そのいずれかを出力してください。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる。そののち t 個のテストケースが続く。

各テストケースは1行から構成され、4つの整数 n (1 \leq n \leq 500), l (1 \leq l \leq n), r (l \leq r \leq n), s \displaystyle \left(1 \leq s \leq \frac{n(n+1)}{2}\right) が与えられる。

全てのテストケースでの n の和が 500 を超えないことは保証されている。

出力

各テストケースについて次のように個別の行に出力せよ。

  • n 個の整数 — 上記の条件を満たすような順列が存在する場合で、そのような長さ n の順列
  • そうでない場合、-1

適する順列が複数存在する場合、そのいずれかを出力せよ。

入出力例

5
5 2 3 5
5 3 4 1
3 1 2 4
2 2 2 2
2 1 1 3
1 2 3 4 5 
-1
1 3 2 
1 2 
-1

F. Education / Образование

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Поликарпは c トゥグルグ*2する新しいコンピュータを買おうと思っています。そのために、大企業でプログラマとして働きたいと思っています。

Поликарпの会社には役職が n 個あり、1から順に番号が振られています。役職 i の従業員は毎日 a[i] トゥグルグを得ます。役職番号が大きいほど、その従業員はより多くのトゥグルグを得ることができます。最初、Поликарпは役職 1 に配置され、0 トゥグルグを持っています。

各日、Поликарпは2つのうち1つのことをすることができます。

  • Поликарпが役職 x にいる場合、a[x] トゥグルグを得る
  • Поликарпが役職 x (x \lt n) にいて、少なくとも b[x] トゥグルグ持っている場合、b[x] トゥグルグをオンライン講座に用いることで役職 x + 1 に移動する

例えば、n = 4, c = 15, a = [1,\,3,\,10,\,11], b = [1,\,2,\,7] の場合、Поликарпはこのように行動することができます。

  • 1日目、Поликарпは役職 1 にいて 1 トゥグルグ得る。ここでは 1 トゥグルグ持っている
  • 2日目、Поликарпは役職 1 にいて 役職 2 に移る。ここでは 0 トゥグルグ持っている
  • 3日目、Поликарпは役職 2 にいて 3 トゥグルグ得る。ここでは 3 トゥグルグ持っている
  • 4日目、Поликарпは役職 2 にいて 役職 3 に移る。ここでは 1 トゥグルグ持っている
  • 5日目、Поликарпは役職 3 にいて 10 トゥグルグ得る。ここでは 11 トゥグルグ持っている
  • 6日目、Поликарпは役職 3 にいて 10 トゥグルグ得る。ここでは 21 トゥグルグ持っている
  • 6日後、Поликарпはコンピュータを買うことができる

Поликарпが新しいコンピュータを買えるようになる最短日数を求めて下さい。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる。そののち t 個のテストケースが続く。

各テストケースの1行目には2つの整数 n,\,c (2 \leq n \leq 2 \cdot 10^5, 1 \leq c \leq 10^9) が与えられる、これらは会社内の役職の数と新しいコンピュータの費用である。

各テストケースの2行目には n 個の整数 a_1 \leq a_2 \leq \dots \leq a_n (1 \leq a_i \leq 10^9) が与えられる。

各テストケースの3行目には n-1 個の整数 b_1,\,b_2,\,\dots,\,b_{n-1} (1 \leq b_i \leq 10^9) が与えられる。

全てのテストケースでの n の和が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについてПоликарпが新しいコンピュータを買えるようになる最短日数を出力せよ。

入出力例

3
4 15
1 3 10 11
1 2 7
4 100
1 5 10 50
3 14 12
2 1000000000
1 1
1
6
13
1000000000

G. Short Task / Короткая задача

テストごとの時間制限: 2秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
数 n の約数全ての和を d(n) とします、即ち、\displaystyle d(n) = \sum_{k \mid n} k です。

例えば、d(1) = 1, d(4) = 1 + 2 + 4 = 7, d(6) = 1 + 2 + 3 + 6 = 12 となります。

与えられた数 c について d(n) = c となるような最小の n を求めて下さい。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる。そののち t 個のテストケースが続く。

各テストケースは1つの整数 c (1 \leq c \leq 10^7) で特徴づけられる。

出力

各テストケースについて以下を出力せよ。

  • d(n) = c となるような n が存在しない場合、"-1"
  • そうでない場合、n

入出力例

12
1
2
3
4
5
6
7
8
9
10
39
691
1
-1
2
3
-1
5
4
7
-1
-1
18
-1

*1:露[pəlʲɪˈkarp]、ポリカルプ、ポリカープ、Polycarp: 古希Πολύκαρπος/po.lý.kar.pos/、ポリュカルポスに由来する人名

*2:モンゴルの通貨。人民共和国時代においてソ連ルーブルと等価であった

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

Codeforces 競技プログラミング Codeforces 和訳 インタラクティブ 和訳 Codeforces Div. 2 和訳

A. Déjà Vu / Дежавю (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
回文とは、前から読んでも後ろから読んでも同じように読める文字列のことです。例えば、文字列"z"や"aaa", "aba", "abccba"は回文ですが、"codeforces"や"ab"は回文ではありません。回文には既視感を覚えるので嫌いです。

文字列 s が与えられます。s のどこかに文字'a'をちょうど1文字挿入しなければなりません。回文でない文字列を作ることができるならその例を求めてください。そうでなければ、それが不可能であることを報告してください。

例えば s = "cbabc"とします。'a'を挿入することで"acbabc"や"cababc", "cbaabc", "cbabac", "cbabca"を作ることができます。しかし"cbaabc"は回文ですので、他の選択肢のいずれかを出力しなければなりません。

入力

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

各テストケースについての唯一の行には小文字の英字から成る文字列 s が与えられる。

全ての文字列の長さの合計は 3 \cdot 10^5 を超えない。

出力

各テストケースについて解が存在しない場合、"NO"と出力せよ。

そうでない場合、"YES"と出力し、次の行に構築した長さ |s| + 1 の文字列を出力せよ。解が複数存在する場合、そのいずれかを出力せよ。

"YES"と"NO"の各文字はどのケース(大文字、小文字)でもよい。

入出力例

6
cbabc
ab
zza
ba
a
nutforajaroftuna
YES
cbabac
YES
aab
YES
zaza
YES
baa
NO
YES
nutforajarofatuna

注記

1つ目のテストケースは、問題文で説明されています。

2つ目のテストケースでは、"aab"と "aba"を作ることができます。しかし、"aba"は回文なので、"aab"が唯一の正解となります。

3つ目のテストケースでは、"zaza"と"zzaa"は正解ですが、"azza"は正解ではありません。

4つ目のテストケースでは、"baa"が唯一の正解です。

5つ目のテストケースでは、"aa"しか作ることができませんが、これは回文です。そのため、答えは"NO"になります 。

6つ目のテストケースでは、"anutforajaroftuna"は回文ですが、他の場所に'a'を挿入すると正解になります。

B. Flip the Bits / Меняем биты (1000点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
長さ n の二進文字列 a があります。1回の操作で a の接頭辞であり 0 と 1 の文字数が等しいものを任意に選ぶことができます。そうすると、その接頭辞に含まれる全ての記号が反転します: それぞれの 0 が 1 に、それぞれの 1 が 0 になります。

例えば、a = 0111010000 とします。

  • 1回目の操作では、長さ 8 の接頭辞は 0 を4つ、1 を4つ持つためこれを選ぶことができる: [01110100]00 \to [10001011]00
  • 2回目の操作では、長さ 2 の接頭辞は 0 を1つ、1 を1つ持つためこれを選ぶことができる: [10]00101100 \to [01]00101100
  • 3回目の操作では、長さ 4 の接頭辞を選ぶことは 0 を3つ、1 を1つ持つためルール違反となります。

文字列 a を有限個の演算(0回でもよい)で文字列 b に変換できるでしょうか?

入力

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

各テストケースの1行目には単一の整数 n (1 \leq n \leq 3 \cdot 10^5) が与えられる、これは文字列 a と b の長さである。

続く2行には長さ n の 0 と 1 の文字から成る文字列 a と b が与えられる。

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

出力

各テストケースについて、a を b に変換することが可能であれば"YES"と、不可能であれば"NO"と出力せよ。各文字はどのケース(大文字、小文字)でもよい。

入出力例

5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100
YES
YES
NO
YES
NO

注記

1つ目のテストケースは、問題文で説明されています。

2つ目のテストケースでは、0回の操作で a を b に変換します。

3つ目のテストケースでは、合法的な操作がないので、 a を b に変換することは不可能です。

4つ目のテストケースでは、次のような変換を行います。

  • 長さ 2 の接頭辞を選び 1001010101 を得る
  • 長さ 12 の接頭辞を選び 011010101010 を得る
  • 長さ 8 の接頭辞を選び 100101011010 を得る
  • 長さ 4 の接頭辞を選び 011001011010 を得る
  • 長さ 6 の接頭辞を選び 100110011010 を得る

5つ目のテストケースでは、唯一の合法的な操作は a を 111000 に変換することです。そこから先は、最初に入力した文字列に戻ることしかできないので、a を b に変換することはできません。

C. Balance the Bits / Сбалансируйте биты (1750点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
括弧列は文字'+'と'1'を追加することで有効な数学的表現に変換することができるとき、バランスが取れているといいます。例えば、'(())()'や'()', '(()(())'はバランスが取れていますが、')('や'(()', '(()))('はそうではありません。

長さ n の二進文字列 s が与えられます。全ての 1 \leq i \leq n について以下を満たすような長さ n のバランス取れた2つの文字列 a,\,b を構築してください。

  • s_i = 1 の場合 a_i = b_i
  • s_i = 0 の場合 a_i \neq b_i

不可能な場合、そのことを報告してください。

入力

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

各テストケースの1行目には単一の整数 n (2 \leq n \leq 2 \cdot 10^5, n\,は素数) が与えられる。

次の行には長さ n の0と1の文字から成る文字列 s が与えられる。

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

出力

このような2つのバランスの取れた括弧列が存在すれば、1行目に"YES"と、そうでなければ"NO"と出力せよ。各文字はどのケース(大文字、小文字)でもよい。

答えが"YES"の場合は、次の2行に条件を満たすバランスの取れた括弧列 a と b を出力せよ。

解が複数存在する場合、そのいずれかを出力せよ。

入出力例

3
6
101101
10
1001101101
4
1100
YES
()()()
((()))
YES
()()((()))
(())()()()
NO

注記

1つ目のテストケースでは、a = "()()()", b = "((()))"となっています。位置 1, 3, 4, 6 の文字は等しく、これらは s_i = 1 の位置と全く同じです。

2つ目のテストケースでは、a = "()()((()))", b = "(())()()()"となっています。位置 1, 4, 5, 7, 8, 10 の文字は等しく、これらは s_i = 1 の位置と全く同じです。

3つ目のテストケースでは、解がありません。

D. 3-Coloring / 3-раскраска (2000点)

テストごとの時間制限: 3秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
これはインタラクティブ問題です。

AliceとBobはあるゲームをしています。n \times n の格子があり、初期状態では空です。1 \leq i,\,j \leq n について i 行 j 列のセルを (i,\,j) と表記します。1, 2, 3 という番号の 3 色のトークンが無限にあります。

ゲームは次のようにターンが進んでいきます。各ターンはAliceが3色のうちの1色を選びます、これを a とします。Bobが b \neq a である色と空のセルを選び、そのマスに色 b のトークンを置きます。

同じ色のトークンが置かれた隣接する2つのセルが存在する場合、コンフリクトが発生しているといいます。2つのセルは共通の辺を共有している場合、隣接していると見なされます。

ある瞬間コンフリクトが発生した場合、Aliceが勝利します。そうではなく、n^2 ターンがコンフリクトが発生せずに完了した(即ち、全てのセルが埋まっている)場合、Bobが勝利します。

Bobが勝利戦略を持っているという証拠があります。Bobとしてゲームをプレイして買ってください。

相互入出力機は適応性があります。つまり、Aliceの色の選択は、Bobのそれまでの動きに依存し得ます。

相互入出力

相互入出力は単一の整数 n (2 \leq n \leq 100) を読むことから始まる、これはグリッドのサイズである。

その後、ゲームのターンが始まります。各ターンは1つの整数 a (1 \leq a \leq 3) を読むことから始まる、これはAliceの選択した色である。

次に3つの整数 b,\,i,\,j (1 \leq b \leq 3, b \neq a, 1 \leq i,\,j \leq n) を出力しなければならない、これらはBobが色 b のトークンをセル (i,\,j) に置くことを表している。セル (i,\,j) には前のターンでのトークンがおかれていてはいけません。手番が無効であったり、ゲームに負けた場合、相互入出力は終了し、Wrong Answerの評価を得る。

n^2 ターンが終了したら、予想外の判定を避けるため、すぐに終了せよ。

何かを出力した後、忘れず改行を出力し、出力をflushせよ。そうでなければIdleness limit exceededを得る。出力のflushのためには、次を利用せよ。

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

ハックを行うには、次のテスト形式に従いなさい。

1行目に単一の整数 n (2 \leq n \leq 100) を出力せよ。

2行目に n^2 個の整数 a_1,\,\dots,\,a_{n^2} (1 \leq a_i \leq 3) を出力せよ、ここで a_i は i ターン目のAliceの色を表す。

相互入出力機はハックの色のリストから逸脱するかもしれませんが、それはBobが負ける原因になる場合だけである。

入出力例

2
1

2

1

3
2 1 1

3 1 2

3 2 1

1 2 2

注記

サンプルの最終的なグリッドは下図の通りです。同じ色のトークンを持つ隣接する2つのセルがないので、Bobの勝ちです。

\begin{matrix}2&3\\3&1\end{matrix}
このサンプルは入出力の形式を示すためのものです。Bobの最適戦略や相互入出力機の実際の行動を示すことを保証するものではありません。

E. Travelling Salesman Problem / Задача коммивояжёра (2250点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
1 から n までの番号がついた n 個の都市があり、都市 i の美しさは a_i です。

セールスマンは都市 1 から出発し、全ての都市をちょうど1回訪れ、都市 1 に戻りたいと考えています。

全ての i \neq j について都市 i から都市 j へのフライトの費用は \max(c_i,\,a_j - a_i) ドルです、ここで c_i は都市 i からの最低金額です。絶対値ではないことに注意してください。セールスマンが旅行を終えるための最小総費用を求めてください。

入力

1行目には単一の整数 n (2 \leq n \leq 10^5) が与えられる、これは都市数である。

続く n 行の i 行目には2つの整数 a_i,\,c_i (0 \leq a_i,\,c_i \leq 10^9) が与えられる、これは都市 i の美しさと最低金額である。

出力

単一の整数を出力せよ、これは最小総費用である。

入出力例

3
1 9
2 1
4 1
11
6
4 2
8 4
3 0
2 3
7 1
0 1
13

注記

1つ目のテストケースでは、1 \to 3 \to 2 \to 1 の順に移動することができます。

  • フライト 1 \to 3 のコストは \max(c_1,\,a_3 - a_1) = \max(9,\,4 - 1) = 9 である
  • フライト 3 \to 2 のコストは \max(c_3,\,a_2 - a_3) = \max(1,\,2 - 4) = 1 である
  • フライト 2 \to 1 のコストは \max(c_2,\,a_1 - a_2) = \max(1,\,1 - 2) = 1 である

総費用は 11 であり、これ以上改善することはできません。

F. Flip the Cards / Переверните карты (3000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n 枚のカードの山があります。i 枚目のカードの表には数 a_i が、裏には数 b_i が書かれています。1 から 2n までの各整数がカード上にちょうど1回現れます。

表の数字が大きい順、裏の数字が小さい順に並んでいれば、山札はソートされているといいます。つまり、全ての 1 \leq i \lt n について a_i \lt a_{i+1}, b_i \gt b_{i+1} である場合です。

カード i をめくるということは、a_i と b_i の値を入れ替えることです。カードのある部分集合(空でもよい)をめくり、全てのカードを好きな順番に並べなければなりません。山札をソートするためにめくらなければならないカードの最小枚数は何枚でしょうか?

入力

1行目には単一の整数 n (1 \leq n \leq2 \cdot 10^5) が与えられる、これはカードの枚数である。

続く n 行はカードの説明である。これらの i 行目には2つの整数 a_i,\,b_i (1 \leq a_i,\,b_i \leq 2n) が与えられる。1 から 2n までの各整数はちょうど1回現れる。

出力

デッキをソートすることが不可能な場合、"-1"を出力せよ。それ以外の場合は、デックをソートするのにめくらなければならないカードの最小枚数を出力せよ。

入出力例

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

注記

1つ目のテストケースでは、(1,\,9) と(2,\,7) のカードをめくります。すると、山札は (3,\,10), (5,\,8), (6,\,4), (7,\,2), (9,\,1) の順に並びます。3 \lt 5 \lt 6 \lt 7 \lt 9 であり 10 \gt 8 \gt 4 \gt 2 \gt 1 なので、ソートされています。

2つ目のテストケースでは、デッキをソートすることは不可能です。

Codeforces Round #711 (Div. 2)のきろく

Codeforces 競技プログラミング Codeforces Div. 2 参戦記 インタラクティブ問題

微減...。問題文和訳はこちら

A. GCD Sum (500点)

3 の倍数は各桁の数字の和も 3 の倍数であり、N, N+1, N+2 のいずれかは 3 の倍数であるため、少なくともこの中に \mathrm{gcdSum} が 1 ではないものが存在します。よって N から順に試していくことで答えが得られます。

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

大きい方から和が W を超えないように選んでいくのを長方形がなくなるまで繰り返していけばいいです。これはある金額を支払うのに必要な効果の枚数を最小にする問題の考え方を利用できるのですが、それは 2 の累乗のみであるため、大きさが隣り合う長方形の幅が割り切れる関係であるため貪欲法で求めることができます(参照)。

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

まずDPを考えます。
$$ {\mathrm{dp}}_{i,j} = (\text{崩壊齢が \(i\) である粒子が \(j\) 枚の平面を通過した後の粒子の数}) $$ とすると、$$ {\mathrm{dp}}_{1,j} = 1 $$ で、$$ {\mathrm{dp}}_{i,0} = 1 $$であり、 $$ {\mathrm{dp}}_{i,j} = \sum_{l = n-j}^{n-1} {\mathrm{dp}}_{i-1,l}$$ という漸化式が成り立ち、答えは {\mathrm{dp}}_{k,n} ですが、このままだと計算量が O(n^2 k) であり間に合いません。そこで累積和を用いることで計算量を O(nk) に落とすことができ、これで間に合います。

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

分かりません...

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

コンテスト後に適当に提出したらACしました。ちゃんと分かるまで保留します。

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

分かりません...

結果、感想

f:id:Flkanjin:20210331000900p:plain
微減... もっと早く通せれば...

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

Codeforces 競技プログラミング Codeforces 和訳 インタラクティブ 和訳 Codeforces Div. 2 和訳

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 番目のテストケースの答えである単一の整数を出力せよ。

入出力例

3
11
31
75
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つを示しています。

f:id:Flkanjin:20210330023851p:plain
上図では、各長方形内部の数字がその幅を表しています。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. 1枚目の平面が左向きに D(2) を生成し、D(3) を右に通過させる
  2. 2枚目の平面が左向きに D(2) を生成し、D(3) を右に通過させる
  3. 1枚目の平面が D(2) を左に通過させ、左向きに D(1) を生成する
  4. 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 個目のテストケースの答えである。

入出力例

4
2 3
2 2
3 1
1 3
4
3
1
2
3
1 1
1 500
500 250
1
2
257950823

注記

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

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

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

f:id:Flkanjin:20210330124454p:plain

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

  1. 1枚目の平面が左向きに D(1) を生成し、D(2) を右に通過させる
  2. 2枚目の平面が左向きに D(1) を生成し、D(2) を右に通過させる
  3. 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
? 2 1
? 1 3
? 4 1
? 2 3
? 4 2
? 4 3
! 0 0

注記

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も最適にプレイをする。手番を打てなくなったプレイヤーが負けです。

木の根として可能なものそれぞれについて、AliceとBobのどちらがゲームに勝つかを求めてください。

注意: 根が r であるような木のノード i の深さはノード r からノード i への単純パス上の辺の本数として定義されます。根 r 自身の深さは0です。

入力

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

続く n - 1 行のそれぞれには2つの整数 x,\,y (1 \leq x,\,y \leq n, x \neq y) が与えられる、これらは2つのノード x,\,y 間の無向辺を表す。これらの辺は n ノードの木を形成する。

次の行には配列 a を表すスペースで区切られた n 個の整数が与えられる (0 \leq a_i \leq 10^9)。

出力

n 個の整数を出力せよ、i 番目の整数は、木の根がノード i にあるときにAliceがゲームに勝った場合は 1、そうでない場合は 0 である。

入出力例

5 1
1 2
1 3
5 2
4 3
0 3 2 4 4
1 0 0 1 1

注記

サンプル入力で根ノードを1とした場合と2とした場合の答えを計算しましょう。

根ノード1

このケースではAliceが勝利します。AlilceとBobの間で考えられるゲームプレイの1つは次のようなものです。

  • Aliceがプレゼントを1つノード4からノード3に移動させる
  • Bobがプレゼントを4つノード5からノード2に移動させる
  • Aliceがプレゼントを4つノード2からノード1に移動させる
  • Bobがプレゼントを3つノード2からノード1に移動させる
  • Aliceがプレゼントを3つノード3からノード1に移動させる
  • Bobがプレゼントを3つノード4からノード3に移動させる
  • Aliceがプレゼントを3つノード3からノード1に移動させる

ここでBobは手番を行うことはできず、負けとなります。

根ノード2

このケースではBobが勝利します。考えられるゲームプレイの1つは次のようなものです。

  • Aliceがプレゼントを4つノード4からノード3に移動させる
  • Bobがプレゼントを4つノード5からノード2に移動させる
  • Aliceがプレゼントを6つノード3からノード1に移動させる
  • Bobがプレゼントを6つノード1からノード2に移動させる

ここでAliceは手番を行うことはできず、負けとなります。

*1:数字和という

*2:インド人名

*3:原語では否定語(no/не)が大文字

*4:インド人名

*5:ハイデラバードにあるインド情報技術大学が開催する年一度のオンラインプログラミングコンテスト

*6:この N は小文字の筈であるが原文では大文字