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

A. Spy Detected! / Шпион обнаружен!
B. Almost Rectangle / Почти прямоугольник
C. A-B Palindrome / A-B палиндром
D. Corrupted Array / Испорченный массив
E. Permutation by Sum / Перестановка по сумме
F. Education / Образование
G. Short Task / Короткая задача

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

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

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

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

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

入出力例

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$

入出力例

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

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