AtCoder Daily Training EASY 2026/07/10 16:00start

A - Exponential Plant

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君は植物を育てています。その植物の発芽時の高さは 0\,\mathrm{cm} です。発芽した日を 0 日目としたとき、発芽してから i (0 \le i) 日目の夜には 2^i\,\mathrm{cm} 植物の高さが伸びます。

高橋君の身長は H\,\mathrm{cm} です。

高橋君は毎朝この植物と背比べをします。植物の高さが高橋君の身長より高くなるのは発芽から何日目の朝か求めてください。

制約

1 \leq H \leq 10^{9}
入力は全て整数である。

入力

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

出力

植物の高さが高橋君の身長より高くなる日は発芽から何日目の朝か出力せよ。

入力例 1

出力例 1

植物が発芽してからの 1 日ごとの朝の高さは 1\,\mathrm{cm},3\,\mathrm{cm},7\,\mathrm{cm}, 15\,\mathrm{cm},31\,\mathrm{cm},63\,\mathrm{cm} となります。 6 日目の朝に高橋君より高くなるため、 6 を出力します。

入力例 2

出力例 2

植物が発芽してから 3 日目の朝の高さは 7\,\mathrm{cm} で、 4 日目の朝の高さは 15\,\mathrm{cm} です。 4 日目の朝に高橋君より高くなるため、 4 を出力します。3 日目の朝のときは高橋君と同じ高さですが、高橋君より高くないことに注意してください。

入力例 3

出力例 3

Score : 100 points

Problem Statement

Takahashi is growing a plant. Its height at the time of germination is 0\,\mathrm{cm}. Considering the day of germination as day 0, its height increases by 2^i\,\mathrm{cm} day i's night (0 \le i).

Takahashi's height is H\,\mathrm{cm}.

Every morning, Takahashi measures his height against this plant. Find the first day such that the plant's height is strictly greater than Takahashi's height in the morning.

Constraints

1 \leq H \leq 10^{9}
All input values are integers.

Input

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

Output

Print an integer representing the first day such that the plant's height is greater than Takahashi's height in the morning.

Sample Input 1

Sample Output 1

The plant's height in the mornings of days 1, 2, 3, 4, 5, 6 will be 1\,\mathrm{cm}, 3\,\mathrm{cm}, 7\,\mathrm{cm}, 15\,\mathrm{cm}, 31\,\mathrm{cm}, 63\,\mathrm{cm}, respectively. The plant becomes taller than Takahashi in the morning day 6, so print 6.

Sample Input 2

Sample Output 2

The plant's height will be 7\,\mathrm{cm} in the morning of day 3 and 15\,\mathrm{cm} in the morning day 4. The plant becomes taller than Takahashi in the morning of day 4, so print 4. Note that, in the morning of day 3, the plant is as tall as Takahashi, but not taller.

Sample Input 3

Sample Output 3

B - 3,2,1,GO

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

正の整数 N が与えられます。

N,N-1,\dots,1 をこの順にカンマ , で区切って出力してください。

制約

1\leq N \leq 9
N は整数

入力

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

出力

N,N-1,\dots,1 をこの順にカンマ区切りで出力せよ。

入力例 1

出力例 1

9,8,7,6,5,4,3,2,1

入力例 2

出力例 2

5,4,3,2,1

入力例 3

出力例 3

Score : 100 points

Problem Statement

You are given a positive integer N.

Output N, N-1, \dots, 1 in this order, separated by commas ,.

Constraints

1 \leq N \leq 9
N is an integer.

Input

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

Output

Output N, N-1, \dots, 1 in this order, separated by commas.

Sample Input 1

Sample Output 1

9,8,7,6,5,4,3,2,1

Sample Input 2

Sample Output 2

5,4,3,2,1

Sample Input 3

Sample Output 3

C - 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

D - Pick Two

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

一直線状の倉庫があります。この倉庫に 偶数個 の荷物が保管されています。
倉庫の情報は文字列 S として与えらます。
倉庫は区画 1,2,\dots,|S| の |S| 個の区画からなり、 S の各文字は以下の情報を表します。

S の i 文字目が # であるとき、区画 i に荷物が 1 つ置かれている。
S の i 文字目が . であるとき、区画 i に荷物が置かれていない。

この倉庫にはロボットがあり、このロボットは以下の行動を倉庫から荷物が無くなるまで繰り返します。

荷物をその荷物がある区画番号の小さい方から 2 つ回収する。回収された荷物は倉庫の外へ運び出される。

繰り返しの各回で運び出された 2 つの荷物が倉庫のどの区画にあったものかを求めてください。

制約

S は # と . からなる長さ 2 以上 1000 以下の文字列
倉庫には偶数個の荷物が保管されている
倉庫には 2 つ以上の荷物が保管されている

入力

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

出力

倉庫に保管されている荷物の総数を m とすると、 m/2 行出力せよ。
そのうち i 行目には、 i 回目の繰り返しで運び出された荷物が元々あった区画の番号を小さい方から順に カンマ区切り で出力せよ。

入力例 1

.#.##..##.#.###....#

出力例 1

2,4
5,8
9,11
13,14
15,20

区画 2,4,5,8,9,11,13,14,15,20 に荷物が保管されています。

1 回目の繰り返しでは区画 2,4 にあった荷物が運び出されます。
2 回目の繰り返しでは区画 5,8 にあった荷物が運び出されます。
3 回目の繰り返しでは区画 9,11 にあった荷物が運び出されます。
4 回目の繰り返しでは区画 13,14 にあった荷物が運び出されます。
5 回目の繰り返しでは区画 15,20 にあった荷物が運び出されます。

Score : 200 points

Problem Statement

There is a linear warehouse, which stores an even number of packages.
The layout of the warehouse is represented by a string S.
The warehouse has |S| sections, numbered 1,2,\dots,|S|, and the string S describes them as follows:

When the i-th character of S is #, one package is placed in section i.
When the i-th character of S is ., no package is placed in section i.

The warehouse has a robot, which repeats the following action until there are no more packages in the warehouse:

Collect two packages from the sections with the smallest section numbers among the sections containing packages. The collected packages are carried out of the warehouse.

For each iteration, determine which sections of the warehouse the two packages that were carried out were originally located.

Constraints

S is a string consisting of # and . with length between 2 and 1000, inclusive.
The warehouse stores an even number of packages.
The warehouse stores at least two packages.

Input

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

Output

Let m be the total number of packages stored in the warehouse. Output m/2 lines.
The i-th line should contain the section numbers where the packages carried out in the i-th iteration were originally located, in ascending order, separated by a comma.

Sample Input 1

.#.##..##.#.###....#

Sample Output 1

2,4
5,8
9,11
13,14
15,20

Packages are stored in sections 2,4,5,8,9,11,13,14,15,20.

In the 1st iteration, packages from sections 2,4 are carried out.
In the 2nd iteration, packages from sections 5,8 are carried out.
In the 3rd iteration, packages from sections 9,11 are carried out.
In the 4th iteration, packages from sections 13,14 are carried out.
In the 5th iteration, packages from sections 15,20 are carried out.

E - Shortest Duplicate Subarray

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正整数 N と、長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

A の空でない連続部分列であって、同じ値を複数個含むようなものが存在するか判定してください。存在するならばそのようなもののうち最も短いものの長さを求めてください。

制約

1\leq N\leq 2\times 10^5
1\leq A_i\leq 10^6 (1\leq i\leq N)
入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

問題文中の条件を満たす連続部分列が存在しないならば -1 と出力せよ。存在するならば、そのようなもののうち最も短いものの長さを出力せよ。

入力例 1

5
3 9 5 3 1

出力例 1

(3,9,5,3) と (3,9,5,3,1) が条件を満たします。短いのは (3,9,5,3) で、その長さは 4 です。

入力例 2

4
2 5 3 1

出力例 2

-1

条件を満たす連続部分列は存在しません。

入力例 3

10
1 1 2 3 5 8 13 21 34 55

出力例 3

Score : 300 points

Problem Statement

You are given a positive integer N and an integer sequence A = (A_1,A_2,\dots,A_N) of length N.

Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^6 \ (1 \leq i \leq N)
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

Output

If there is no (contiguous) subarray satisfying the condition in the problem statement, print -1. Otherwise, print the length of the shortest such subarray.

Sample Input 1

5
3 9 5 3 1

Sample Output 1

(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.

Sample Input 2

4
2 5 3 1

Sample Output 2

-1

There is no subarray that satisfies the condition.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55