AtCoder Daily Training EASY 2026/07/22 18:00start

A - Water Station

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

全長 100\;\mathrm{km} のマラソンコースがあります。マラソンコースにはスタートから 5\;\mathrm{km} おきに給水所が設置されており、スタート地点・ゴール地点とあわせて 21 箇所の給水所があります。

高橋くんは、このマラソンコースの N\;\mathrm{km} 地点にいます。高橋くんに最も近い給水所は何 \mathrm{km} 地点の給水所か求めてください。

この問題の制約のもとで、最も近い給水所が 1 つに定まることが証明できます。

制約

0\leq N\leq100
N は整数

入力

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

出力

高橋くんがいる地点に最も近い給水所が何 \mathrm{km} 地点にあるかを 1 行で出力せよ。

入力例 1

出力例 1

高橋くんは、マラソンコースの 53\;\mathrm{km} 地点にいます。 55\;\mathrm{km} 地点の給水所までの距離は 2\;\mathrm{km} で、これより近い給水所はありません。よって、55 を出力してください。

入力例 2

出力例 2

高橋くんはマラソンコースを戻ることもできます。

入力例 3

出力例 3

給水所はスタートやゴールにもあります。また、高橋くんはすでに給水所にいることもあります。

Score : 100 points

Problem Statement

There is an ultramarathon course totaling 100\;\mathrm{km}. Water stations are set up every 5\;\mathrm{km} along the course, including the start and goal, for a total of 21.

Takahashi is at the N\;\mathrm{km} point of this course. Find the position of the nearest water station to him.

Under the constraints of this problem, it can be proven that the nearest water station is uniquely determined.

Constraints

0\leq N\leq100
N is an integer.

Input

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

Output

Print the distance between the start and the water station nearest to Takahashi, in kilometers, in a single line.

Sample Input 1

Sample Output 1

Takahashi is at the 53\;\mathrm{km} point of the course. The water station at the 55\;\mathrm{km} point is 2\;\mathrm{km} away, and there is no closer water station. Therefore, you should print 55.

Sample Input 2

Sample Output 2

Takahashi could also go back the way.

Sample Input 3

Sample Output 3

There are also water stations at the start and goal. Additionally, Takahashi may already be at a water station.

B - Odd Position Sum

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

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

A の奇数番目の要素の総和を求めてください。すなわち、N 以下の最大の奇数を m としたとき A_1+A_3+A_5+\ldots+A_m を求めてください。

制約

1\leq N\leq 100
1\leq A_i\leq 100
入力は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

7
3 1 4 1 5 9 2

出力例 1

A の奇数番目の要素の総和は A_1+A_3+A_5+A_7=3+4+5+2=14 です。

入力例 2

1
100

出力例 2

入力例 3

14
100 10 1 10 100 10 1 10 100 10 1 10 100 10

出力例 3

Score : 100 points

Problem Statement

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

Find the sum of the odd-indexed elements of A. That is, find A_1 + A_3 + A_5 + \dots + A_m, where m is the largest odd number not exceeding N.

Constraints

1 \le N \le 100
1 \le A_i \le 100
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

Print the answer.

Sample Input 1

7
3 1 4 1 5 9 2

Sample Output 1

The sum of the odd-indexed elements of A is A_1+A_3+A_5+A_7=3+4+5+2=14.

Sample Input 2

1
100

Sample Output 2

Sample Input 3

14
100 10 1 10 100 10 1 10 100 10 1 10 100 10

Sample Output 3

C - Base 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

0 と 1 からなる長さ 64 の数列 A=(A_0,A_1,\dots,A_{63}) が与えられます。

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} を求めてください。

制約

A_i は 0 または 1

入力

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

A_0 A_1 \dots A_{63}

出力

答えを整数として出力せよ。

入力例 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例 1

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13 です。

入力例 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

出力例 2

766067858140017173

Score : 200 points

Problem Statement

You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.

Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.

Constraints

A_i is 0 or 1.

Input

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

A_0 A_1 \dots A_{63}

Output

Print the answer as an integer.

Sample Input 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.

Sample Input 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

Sample Output 2

766067858140017173

D - Fill the Gaps

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

正整数からなる長さ N の数列 A=(A_1,\ldots,A_N) があります。どの隣接する 2 項の値も相異なります。

この数列に対し、次の操作によりいくつか数を挿入します。

数列 A のどの隣接する 2 項の差の絶対値も 1 であるとき、操作を終了する。
数列 A の先頭から見て、隣接する 2 項の差の絶対値が 1 でない最初の箇所を A_i,A_{i+1} とする。
- A_i < A_{i+1} ならば、A_i と A_{i+1} の間に、A_i+1,A_i+2,\ldots,A_{i+1}-1 を挿入する。
- A_i > A_{i+1} ならば、A_i と A_{i+1} の間に、A_i-1,A_i-2,\ldots,A_{i+1}+1 を挿入する。
手順 1 に戻る。

操作が終了したときの数列を出力してください。

制約

2 \leq N \leq 100
1 \leq A_i \leq 100
A_i \neq A_{i+1}
入力は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

操作が終了したときの数列の各要素を空白区切りで出力せよ。

入力例 1

4
2 5 1 2

出力例 1

2 3 4 5 4 3 2 1 2

最初、数列は (2,5,1,2) です。操作は以下のように行われます。

1 項目の 2 と 2 項目の 5 の間に 3,4 を挿入する。数列は (2,3,4,5,1,2) となる。
4 項目の 5 と 5 項目の 1 の間に 4,3,2 を挿入する。数列は (2,3,4,5,4,3,2,1,2) となる。

入力例 2

6
3 4 5 6 5 4

出力例 2

3 4 5 6 5 4

一度も挿入が行われないこともあります。

Score : 200 points

Problem Statement

We have a sequence of length N consisting of positive integers: A=(A_1,\ldots,A_N). Any two adjacent terms have different values.

Let us insert some numbers into this sequence by the following procedure.

If every pair of adjacent terms in A has an absolute difference of 1, terminate the procedure.
Let A_i, A_{i+1} be the pair of adjacent terms nearest to the beginning of A whose absolute difference is not 1.
- If A_i < A_{i+1}, insert A_i+1,A_i+2,\ldots,A_{i+1}-1 between A_i and A_{i+1}.
- If A_i > A_{i+1}, insert A_i-1,A_i-2,\ldots,A_{i+1}+1 between A_i and A_{i+1}.
Return to step 1.

Print the sequence when the procedure ends.

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 100
A_i \neq A_{i+1}
All values in the input are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the terms in the sequence when the procedure ends, separated by spaces.

Sample Input 1

4
2 5 1 2

Sample Output 1

2 3 4 5 4 3 2 1 2

The initial sequence is (2,5,1,2). The procedure goes as follows.

Insert 3,4 between the first term 2 and the second term 5, making the sequence (2,3,4,5,1,2).
Insert 4,3,2 between the fourth term 5 and the fifth term 1, making the sequence (2,3,4,5,4,3,2,1,2).

Sample Input 2

6
3 4 5 6 5 4

Sample Output 2

3 4 5 6 5 4

No insertions may be performed.

E - The Kth Time Query

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

長さ N の数列 A = (a_1, a_2, \dots, a_N) があります。
以下で説明される Q 個のクエリに答えてください。

クエリ i : 整数の組 (x_i, k_i) が与えられます。A の要素を a_1, a_2, \dots と前から順に見ていったときに、数 x_i が k_i 回目に登場するのは A の前から何番目の要素を見たときかを出力してください。
ただし条件を満たす要素が存在しない場合は -1 を出力してください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
0 \leq a_i \leq 10^9 (1 \leq i \leq N)
0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
1 \leq k_i \leq N (1 \leq i \leq Q)
入力はすべて整数である。

入力

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

N Q
a_1 a_2 \dots a_N
x_1 k_1
x_2 k_2
\vdots
x_Q k_Q

出力

Q 行出力せよ。i 行目ではクエリ i に対する答えを出力せよ。

入力例 1

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

出力例 1

A の中で 1 は a_1, a_2, a_5 に登場します。よって、クエリ 1 からクエリ 4 の答えは順に 1, 2, 5, -1 となります。

入力例 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

出力例 2

2
-1

Score : 300 points

Problem Statement

We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.

Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
Print the index of that element, or -1 if there is no such element.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
0 \leq a_i \leq 10^9 (1 \leq i \leq N)
0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
1 \leq k_i \leq N (1 \leq i \leq Q)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 a_2 \dots a_N
x_1 k_1
x_2 k_2
\vdots
x_Q k_Q

Output

Print Q lines. The i-th line should contain the answer to Query i.

Sample Input 1

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

Sample Output 1

1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.

Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1