AtCoder Daily Training MEDIUM 2025/06/25 16:00start

C - Rotate

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 行 N 列のマス目が与えられます。上から i 行目、左から j 列目のマスには整数 A_{i,j} が書かれています。ここで、A_{i,j} は 0 か 1 であることが保証されます。

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目を出力してください。

ただし外側のマスとは、1 行目、N 行目、1 列目、N 列目のいずれか 1 つ以上に属するマスの集合のことを指します。

制約

2 \le N \le 100
0 \le A_{i,j} \le 1(1 \le i,j \le N)
入力は全て整数

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

出力

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目において、上から i 行目、左から j 列目のマスに書かれている整数を B_{i,j} と置く。このとき、以下の形式で出力せよ。

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

入力例 1

出力例 1

上から i 行目、左から j 列目のマスを (i,j) と呼ぶこととします。

外側のマスは (1,1) から時計回りに列挙すると (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1),(2,1) の 12 個です。

これらのマスに書かれている整数を、時計回りに 1 個ずつ動かすと出力欄のようになります。

入力例 2

2
11
11

出力例 2

11
11

入力例 3

出力例 3

Score : 200 points

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

2 \le N \le 100
0 \le A_{i,j} \le 1(1 \le i,j \le N)
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

Output

Let B_{i,j} be the integer written on the square at the i-th row from the top and j-th column from the left in the grid resulting from shifting the outer squares clockwise by one square each. Print them in the following format:

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

Sample Input 1

Sample Output 1

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

Sample Output 3

D - Maritozzo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる 3 つの文字列 S_1, S_2, S_3 と、1、2、3 のみからなる文字列 T が与えられます。

T の各文字に対応する文字列を連結してできる文字列を出力してください。より厳密には、以下の指示にしたがって文字列を出力してください。

1 \leq i \leq |T| を満たす整数 i に対し、文字列 s_i を次のように定める。
- T の i 文字目が 1 のとき、S_1
- T の i 文字目が 2 のとき、S_2
- T の i 文字目が 3 のとき、S_3
s_1, s_2, \dots, s_{|T|} をこの順に連結してできる文字列を出力する。

制約

1 \leq |S_1|, |S_2|, |S_3| \leq 10
1 \leq |T| \leq 1000
S_1, S_2, S_3 は英小文字からなる。
T は 1、2、3 のみからなる。

入力

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

S_1
S_2
S_3
T

出力

答えを出力せよ。

入力例 1

mari
to
zzo
1321

出力例 1

marizzotomari

s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari であるので、これらを連結してできる文字列である marizzotomari を出力します。

入力例 2

abra
cad
abra
123

出力例 2

abracadabra

入力例 3

a
b
c
1

出力例 3

Score : 200 points

Problem Statement

You are given three strings S_1, S_2, S_3 consisting of lowercase English letters, and a string T consisting of 1, 2, 3.

Concatenate the three strings according to the characters in T and print the resulting string. Formally, conform to the following instructions.

For each integer i such that 1 \leq i \leq |T|, let the string s_i be defined as follows:
- S_1, if the i-th character of T is 1;
- S_2, if the i-th character of T is 2;
- S_3, if the i-th character of T is 3.
Concatenate the strings s_1, s_2, \dots, s_{|T|} in this order and print the resulting string.

Constraints

1 \leq |S_1|, |S_2|, |S_3| \leq 10
1 \leq |T| \leq 1000
S_1, S_2, and S_3 consist of lowercase English letters.
T consists of 1, 2, and 3.

Input

Input is given from Standard Input in the following format:

S_1
S_2
S_3
T

Output

Print the answer.

Sample Input 1

mari
to
zzo
1321

Sample Output 1

marizzotomari

We have s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari. Concatenate these and print the resulting string: marizzotomari.

Sample Input 2

abra
cad
abra
123

Sample Output 2

abracadabra

Sample Input 3

a
b
c
1

Sample Output 3

E - Prepare Another Box

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

1 から N までの番号が付けられた N 個のおもちゃと、1 から N-1 までの番号が付けられた N-1 個の箱があります。おもちゃ i\ (1\leq i\leq N) の大きさは A_i、箱 i\ (1\leq i\leq N-1) の大きさは B_i です。

すべてのおもちゃを別々の箱にしまいたいと考えている高橋君は、今から以下の操作を順に行うことにしました。

任意の正整数 x を選んで、大きさ x の箱を 1 つ購入する。
N 個のおもちゃそれぞれを、（元々あった箱と新しく購入した箱を合わせた）N 個の箱のいずれかに入れる。ただし、各おもちゃはそのおもちゃの大きさ以上の大きさを持つ箱にしか入れることはできず、また 1 つの箱に 2 つ以上のおもちゃを入れることもできない。

高橋君は、操作 1 で十分な大きさの箱を購入することで操作 2 が実行できるようにしたいですが、大きな箱ほど値段が高いため、可能な限り小さな箱を購入したいです。

高橋君が操作 2 を実行できるような x の値が存在するか判定し、存在するならばその最小値を求めてください。

制約

2\leq N \leq 2\times 10^5
1\leq A_i,B_i \leq 10^9
入力は全て整数

入力

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_{N-1}

出力

高橋君が操作 2 を実行できるような x の値が存在するならばその最小値を、存在しないならば -1 を出力せよ。

入力例 1

4
5 2 3 7
6 2 8

出力例 1

x=3 とした場合（すなわち、操作 1 で大きさ 3 の箱を購入した場合）を考えます。

新しく購入した箱を箱 4 と呼ぶことにすると、おもちゃ 1,\dots,4 の大きさはそれぞれ 5,2,3,7、箱 1,\dots,4 の大きさはそれぞれ 6,2,8,3 となります。よって、おもちゃ 1 を箱 1 に、おもちゃ 2 を箱 2 に、おもちゃ 3 を箱 4 に、おもちゃ 4 を箱 3 にそれぞれ入れることができます。

逆に、x\leq 2 のときは N 個のおもちゃすべてを別々の箱に入れることができません。よって答えは 3 です。

入力例 2

4
3 7 2 5
8 1 6

出力例 2

-1

操作 1 でどのような大きさの箱を購入したとしても、箱 2 に入れられる大きさのおもちゃが存在しないため、操作 2 を実行することができません。

入力例 3

8
2 28 17 39 57 56 37 32
34 27 73 28 76 61 27

出力例 3

Score : 350 points

Problem Statement

There are N toys numbered from 1 to N, and N-1 boxes numbered from 1 to N-1. Toy i\ (1 \leq i \leq N) has a size of A_i, and box i\ (1 \leq i \leq N-1) has a size of B_i.

Takahashi wants to store all the toys in separate boxes, and he has decided to perform the following steps in order:

Choose an arbitrary positive integer x and purchase one box of size x.
Place each of the N toys into one of the N boxes (the N-1 existing boxes plus the newly purchased box). Here, each toy can only be placed in a box whose size is not less than the toy's size, and no box can contain two or more toys.

He wants to execute step 2 by purchasing a sufficiently large box in step 1, but larger boxes are more expensive, so he wants to purchase the smallest possible box.

Determine whether there exists a value of x such that he can execute step 2, and if it exists, find the minimum such x.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq A_i, B_i \leq 10^9
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_{N-1}

Output

If there exists a value of x such that Takahashi can execute step 2, print the minimum such x. Otherwise, print -1.

Sample Input 1

4
5 2 3 7
6 2 8

Sample Output 1

Consider the case where x=3 (that is, he purchases a box of size 3 in step 1).

If the newly purchased box is called box 4, toys 1,\dots,4 have sizes of 5, 2, 3, and 7, respectively, and boxes 1,\dots,4 have sizes of 6, 2, 8, and 3, respectively. Thus, toy 1 can be placed in box 1, toy 2 in box 2, toy 3 in box 4, and toy 4 in box 3.

On the other hand, if x \leq 2, it is impossible to place all N toys into separate boxes. Therefore, the answer is 3.

Sample Input 2

4
3 7 2 5
8 1 6

Sample Output 2

-1

No matter what size of box is purchased in step 1, no toy can be placed in box 2, so it is impossible to execute step 2.

Sample Input 3

8
2 28 17 39 57 56 37 32
34 27 73 28 76 61 27

Sample Output 3

F - Many Balls

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

空の箱があります。
髙橋君は以下の 2 種類の魔法を好きな順番で好きな回数使えます。

魔法 A ：箱の中にボールを 1 つ増やす
魔法 B ：箱の中のボールの数を 2 倍にする

合計 \mathbf{120} 回以内の魔法で、箱の中のボールの数をちょうど N 個にする方法を 1 つ教えてください。
なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。

魔法以外の方法でボールの数を変化させることはできません。

制約

1 \leq N \leq 10^{18}
入力は全て整数

入力

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

出力

A , B のみからなる文字列 S を出力せよ。
S の i 文字目が A ならば、髙橋君が i 回目に使う魔法が魔法 A であることを表し、B ならば魔法 B であることを表す。

S の長さは \mathbf{120} 以下でなければならない。

入力例 1

出力例 1

AABA

ボールの数は、0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5 と変化します。
AAAAA などの答えも正解になります。

入力例 2

出力例 2

BBABBAAAB

ボールの数は、0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14 と変化します。
S の長さを最小化する必要はありません。

Score : 300 points

Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

Spell A: puts one new ball into the box.
Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

1 \leq N \leq 10^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

Print a string S consisting of A and B. The i-th character of S should represent the spell for the i-th cast.

S must have at most \mathbf{120} characters.

Sample Input 1

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

G - Strange Balls

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は 2 以上の整数が書かれた N 個のボールを持っており、これらを細長い筒の中に落としていきます。i \, (1 \leq i \leq N) 回目には、a_i が書かれたボールを落とします。

ボールは特殊な材質でできており、筒の中において k \, (k \geq 2) が書かれたボールが k 個連続すると、それら k 個のボールは全て消えてしまいます。

各 i \, (1 \leq i \leq N) について、i 個目のボールを筒の中に落とした後、筒の中に何個のボールがあるか求めてください。

制約

1 \leq N \leq 2 \times 10^5
2 \leq a_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
入力は全て整数

入力

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

N
a_1 \ldots a_N

出力

N 行出力せよ。i \, (1 \leq i \leq N) 行目には、i 個目のボールを筒の中に落とした後、筒の中にあるボールの個数を出力せよ。

入力例 1

5
3 2 3 2 2

出力例 1

筒の中は次のように変化します。

1 個目のボールを落とす。筒の中にあるボールに書かれた整数は 3 である。
2 個目のボールを落とす。筒の中にあるボールに書かれた整数は下から順に 3, 2 である。
3 個目のボールを落とす。筒の中にあるボールに書かれた整数は下から順に 3, 2, 3 である。
4 個目のボールを落とす。筒の中にあるボールに書かれた整数は下から順に 3, 2, 3, 2 である。
5 個目のボールを落とす。筒の中にあるボールに書かれた整数は下から順に 3, 2, 3, 2, 2 となるが、2 が書かれたボールが 2 個連続しているのでこれらは消え、下から順に 3, 2, 3 となる。

入力例 2

10
2 3 2 3 3 3 2 3 3 2

出力例 2

Score : 400 points

Problem Statement

Takahashi has N balls. Each ball has an integer not less than 2 written on it. He will insert them in a cylinder one by one. The integer written on the i-th ball is a_i.

The balls are made of special material. When k balls with k (k \geq 2) written on them line up in a row, all these k balls will disappear.

For each i (1 \leq i \leq N), find the number of balls after inserting the i-th ball.

Constraints

1 \leq N \leq 2 \times 10^5
2 \leq a_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the number of balls after inserting the i-th ball.

Sample Input 1

5
3 2 3 2 2

Sample Output 1

The content of the cylinder changes as follows.

After inserting the 1-st ball, the cylinder contains the ball with 3.
After inserting the 2-nd ball, the cylinder contains 3, 2 from bottom to top.
After inserting the 3-rd ball, the cylinder contains 3, 2, 3 from bottom to top.
After inserting the 4-th ball, the cylinder contains 3, 2, 3, 2 from bottom to top.
After inserting the 5-th ball, the cylinder momentarily has 3, 2, 3, 2, 2 from bottom to top. The two consecutive balls with 2 disappear, and the cylinder eventually contains 3, 2, 3 from bottom to top.

Sample Input 2

10
2 3 2 3 3 3 2 3 3 2

Sample Output 2