AtCoder Daily Training EASY 2026/09/08 16:00start

A - Alloy

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋くんは A グラムの純金と B グラムの純銀 (0 \leq A,B,\ 0 \lt A+B) をよく溶かした上で混ぜ合わせ、新たな金属を生成しました。

生成された金属は「純金」「純銀」「合金」のいずれでしょうか？

なお、生成された金属は

0 \lt A かつ B=0 なら「純金」
A=0 かつ 0 \lt B なら「純銀」
0 \lt A かつ 0 \lt B なら「合金」

であるとみなします。

制約

0 \leq A,B \leq 100
0 \lt A+B
A,B は整数

入力

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

A B

出力

生成された金属が「純金」なら Gold と、「純銀」なら Silver と、「合金」なら Alloy と出力せよ。

入力例 1

50 50

出力例 1

Alloy

0 \lt A かつ 0 \lt B であるため、生成された金属は「合金」です。

入力例 2

100 0

出力例 2

Gold

0 \lt A かつ B=0 であるため、生成された金属は「純金」です。

入力例 3

0 100

出力例 3

Silver

A=0 かつ 0 \lt B であるため、生成された金属は「純銀」です。

入力例 4

100 2

出力例 4

Alloy

Score : 100 points

Problem Statement

Takahashi melted and mixed A grams of gold and B grams of silver (0 \leq A,B,\ 0 \lt A+B) to produce new metal.

What metal did he produce: pure gold, pure silver, or an alloy?

Formally, the product is called as follows.

Pure gold, if 0 \lt A and B=0.
Pure silver, if A=0 and 0 \lt B.
An alloy, if 0 \lt A and 0 \lt B.

Constraints

0 \leq A,B \leq 100
1 \leq A+B
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B

Output

If the product is pure gold, print Gold; if it is pure silver, print Silver; if it is an alloy, print Alloy.

Sample Input 1

50 50

Sample Output 1

Alloy

We have 0 \lt A and 0 \lt B, so the product is an alloy.

Sample Input 2

100 0

Sample Output 2

Gold

We have 0 \lt A and B=0, so the product is pure gold.

Sample Input 3

0 100

Sample Output 3

Silver

We have A=0 and 0 \lt B, so the product is pure silver.

Sample Input 4

100 2

Sample Output 4

Alloy

B - Subsegment Reverse

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

正整数 N,L,R が与えられます。
長さ N の数列 A=(1,2,\dots,N) に対し、 L 項目から R 項目までを逆順に並べ替えるという操作を一度行いました。
操作後の数列を出力してください。

制約

入力は全て整数
1 \le L \le R \le N \le 100

入力

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

N L R

出力

操作後の数列を A'=(A'_1,A'_2,\dots,A'_N) として、以下の形式で出力せよ。

A'_1 A'_2 \dots A'_N

入力例 1

5 2 3

出力例 1

1 3 2 4 5

最初、 A=(1,2,3,4,5) です。
2 項目から 3 項目までを逆順に並べ替えた後の数列は (1,3,2,4,5) なので、これを出力してください。

入力例 2

7 1 1

出力例 2

1 2 3 4 5 6 7

L=R である場合もあります。

入力例 3

10 1 10

出力例 3

10 9 8 7 6 5 4 3 2 1

L=1 や R=N である場合もあります。

Score : 100 points

Problem Statement

You are given positive integers N, L, and R.
For a sequence A = (1, 2, \dots, N) of length N, an operation of reversing the L-th through R-th elements was performed once.
Print the sequence after this operation.

Constraints

All input values are integers.
1 \leq L \leq R \leq N \leq 100

Input

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

N L R

Output

Let A' = (A'_1, A'_2, \dots, A'_N) be the sequence after the operation. Print it in the following format:

A'_1 A'_2 \dots A'_N

Sample Input 1

5 2 3

Sample Output 1

1 3 2 4 5

Initially, A = (1, 2, 3, 4, 5).
After reversing the second through third elements, the sequence becomes (1, 3, 2, 4, 5), which should be printed.

Sample Input 2

7 1 1

Sample Output 2

1 2 3 4 5 6 7

It is possible that L = R.

Sample Input 3

10 1 10

Sample Output 3

10 9 8 7 6 5 4 3 2 1

It is possible that L = 1 or R = N.

C - A^A

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 B が与えられます。
A^A = B であるような正の整数 A が存在するならばその値を、存在しないならば -1 を出力してください。

制約

1 \leq B \leq 10^{18}
B は整数

入力

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

出力

A^A = B であるような正の整数 A が存在するならばその値を、存在しないならば -1 を出力せよ。
A^A = B を満たす正の整数 A が複数ある場合は、どれを出力しても正解とみなされる。

入力例 1

出力例 1

3^3 = 27 なので 3 を出力します。

入力例 2

出力例 2

-1

A^A = B を満たす A は存在しません。

入力例 3

10000000000

出力例 3

Score : 200 points

Problem Statement

You are given an integer B.
If there exists a positive integer A such that A^A = B, print its value; otherwise, output -1.

Constraints

1 \leq B \leq 10^{18}
B is an integer.

Input

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

Output

If there exists a positive integer A such that A^A = B, print its value; otherwise, print -1.
If there are multiple positive integers A such that A^A = B, any of them will be accepted.

Sample Input 1

Sample Output 1

3^3 = 27, so print 3.

Sample Input 2

Sample Output 2

-1

There is no A such that A^A = B.

Sample Input 3

10000000000

Sample Output 3

D - Arrays

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 個の数列 A_1, A_2, \ldots, A_N が与えられます。

数列 A_i の長さは L_i であり A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i}) です。

その後、整数 X, Y が与えられます。 A_{X,Y} の値を出力してください。

制約

1 \le N \le 2 \times 10^5
1 \le L_i
L_i の総和は 2 \times 10^5 以下
1 \le A_{i,j} \le 1000
1 \le X \le N
1 \le Y \le L_X
入力される値はすべて整数

入力

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

N
L_1 A_{1,1} A_{1,2} \ldots A_{1,L_1}
L_2 A_{2,1} A_{2,2} \ldots A_{2,L_2}
\vdots
L_N A_{N,1} A_{N,2} \ldots A_{N,L_N}
X Y

出力

A_{X,Y} の値を出力せよ。

入力例 1

出力例 1

(A_1, A_2, A_3) = ((10,20,30), (7), (5,6, 7,8)) です。
A_3 = (5, 6, 7, 8) であり、 A_{3,4} = 8 なので 8 を出力してください。

入力例 2

出力例 2

A_2 = (8, 2, 6) なので、A_{2,2} = 2 です。

入力例 3

1
5 100 200 300 400 500
1 5

出力例 3

Score : 200 points

Problem Statement

You are given N sequences A_1, A_2, \ldots, A_N.

The length of sequence A_i is L_i, and A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i}).

After that, integers X and Y are given. Output the value of A_{X,Y}.

Constraints

1 \le N \le 2 \times 10^5
1 \le L_i
The sum of L_i is at most 2 \times 10^5.
1 \le A_{i,j} \le 1000
1 \le X \le N
1 \le Y \le L_X
All input values are integers.

Input

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

N
L_1 A_{1,1} A_{1,2} \ldots A_{1,L_1}
L_2 A_{2,1} A_{2,2} \ldots A_{2,L_2}
\vdots
L_N A_{N,1} A_{N,2} \ldots A_{N,L_N}
X Y

Output

Output the value of A_{X,Y}.

Sample Input 1

Sample Output 1

We have (A_1, A_2, A_3) = ((10,20,30), (7), (5,6, 7,8)).
Since A_3 = (5, 6, 7, 8) and A_{3,4} = 8, output 8.

Sample Input 2

Sample Output 2

Since A_2 = (8, 2, 6), we have A_{2,2} = 2.

Sample Input 3

1
5 100 200 300 400 500
1 5

Sample Output 3

E - Snake Queue

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

ヘビの待ち行列があります。最初、列は空です。

クエリが Q 個与えられるので、与えられた順に処理してください。クエリは以下の 3 種類です。

タイプ 1 : 1 l の形式で与えられる。長さ l のヘビが列の末尾に追加される。このとき追加するヘビの頭の位置は、元の列が空の場合は座標 0、そうでない場合は最後尾のヘビの頭の座標に最後尾のヘビの長さを加えた座標となる。
タイプ 2 : 2 の形式で与えられる。列の先頭にいるヘビが列から抜ける。このとき、列が空でないことは保証される。抜けたヘビの長さを m として、列に残っている全てのヘビの頭の座標が m だけ減少する。
タイプ 3 : 3 k の形式で与えられる。列の先頭から数えて k 番目にいるヘビの頭の座標を出力せよ。このとき、列には少なくとも k 匹のヘビがいることが保証される。

制約

1 \leq Q \leq 3 \times 10^{5}
タイプ 1 のクエリにおいて、1 \leq l \leq 10^{9}
タイプ 2 のクエリにおいて、列が空でないことが保証される
タイプ 3 のクエリにおいて、列にいるヘビの数を n として、1 \leq k \leq n
入力は全て整数

入力

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

ただし、\text{query}_i は i 個目のクエリを表し、以下のいずれかの形式である。

1 l

3 k

出力

タイプ 3 のクエリの個数を q として、q 行出力せよ。i 行目には、i 個目のタイプ 3 のクエリに対する答えを出力せよ。

入力例 1

出力例 1

5
10

1 個目のクエリ : 長さ 5 のヘビが列に追加される。列にヘビはいないため、追加されたヘビの頭の座標は 0 となる。
2 個目のクエリ : 長さ 7 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 0 で長さが 5 のため、追加されたヘビの頭の座標は 5 となる。
3 個目のクエリ : 前から 2 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 5 であるため、5 を出力する。
4 個目のクエリ : 長さ 3 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 5 で長さが 7 のため、追加されたヘビの頭の座標は 12 となる。
5 個目のクエリ : 長さ 4 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 12 で長さが 3 のため、追加されたヘビの頭の座標は 15 となる。
6 個目のクエリ : 先頭のヘビが列から抜ける。抜けたヘビの長さが 5 であるため、列にいるヘビの頭の座標は 5 だけ減少する。列に残っているヘビの頭の座標は先頭から順に 0,7,10 となる。
7 個目のクエリ : 前から 3 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 7, 10 であるため、10 を出力する。

入力例 2

出力例 2

タイプ 3 のクエリが 1 つもない場合もあります。

入力例 3

出力例 3

20
5

Score : 300 points

Problem Statement

There is a queue of snakes. Initially, the queue is empty.

You are given Q queries, which should be processed in the order they are given. There are three types of queries:

Type 1: Given in the form 1 l. A snake of length l is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is 0; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length.
Type 2: Given in the form 2. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let m be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by m.
Type 3: Given in the form 3 k. Output the head coordinate of the snake that is k-th from the front of the queue. It is guaranteed that there are at least k snakes in the queue at this time.

Constraints

1 \leq Q \leq 3 \times 10^{5}
For a query of type 1, 1 \leq l \leq 10^{9}
For a query of type 2, it is guaranteed that the queue is not empty.
For a query of type 3, let n be the number of snakes in the queue, then 1 \leq k \leq n.
All input values are integers.

Input

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Here, \text{query}_i is the i-th query in one of the following forms:

1 l

3 k

Output

Let q be the number of queries of type 3. Print q lines. The i-th line should contain the answer to the i-th type 3 query.

Sample Input 1

Sample Output 1

5
10

1st query: A snake of length 5 is added to the queue. Since the queue was empty, the head coordinate of this snake is 0.
2nd query: A snake of length 7 is added to the queue. Before adding, the last snake has head coordinate 0 and length 5, so the newly added snake’s head coordinate is 5.
3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are 0, 5, so output 5.
4th query: A snake of length 3 is added to the queue. Before adding, the last snake has head coordinate 5 and length 7, so the new snake’s head coordinate is 12.
5th query: A snake of length 4 is added to the queue. Before adding, the last snake has head coordinate 12 and length 3, so the new snake’s head coordinate is 15.
6th query: The snake at the front leaves the queue. The length of the snake that left is 5, so the head coordinate of each remaining snake decreases by 5. The remaining snake’s head coordinate becomes 0, 7, 10.
7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are 0, 7, 10, so output 10.

Sample Input 2

Sample Output 2

It is possible that there are no queries of type 3.

Sample Input 3

Sample Output 3

20
5