AtCoder Daily Training EASY 2026/06/22 16:00start

A - To Be Saikyo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 から N までの番号が付けられた N 人の人がいます。それぞれの人にはプログラミング力という整数値が定まっており、人 i のプログラミング力は P_i です。人 1 が最強になるためには、あといくつプログラミング力を上げる必要がありますか？すなわち、すべての i \neq 1 に対して P_1 + x > P_i を満たすような最小の非負整数 x は何ですか？

制約

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

入力

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

N
P_1 P_2 \dots P_N

出力

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

入力例 1

4
5 15 2 10

出力例 1

人 1 が最強になるためには、プログラミング力を 16 以上にする必要があります。よって、答えは 16-5=11 です。

入力例 2

4
15 5 2 10

出力例 2

人 1 は既に最強なので、これ以上プログラミング力を上げる必要はありません。

入力例 3

3
100 100 100

出力例 3

Score : 100 points

Problem Statement

There are N people numbered 1 through N. Each person has a integer score called programming ability; person i's programming ability is P_i points. How many more points does person 1 need, so that person 1 becomes the strongest? In other words, what is the minimum non-negative integer x such that P_1 + x > P_i for all i \neq 1?

Constraints

1\leq N \leq 100
1\leq P_i \leq 100
All input values are integers.

Input

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

N
P_1 P_2 \dots P_N

Output

Print the answer as an integer.

Sample Input 1

4
5 15 2 10

Sample Output 1

Person 1 becomes the strongest when their programming skill is 16 points or more, so the answer is 16-5=11.

Sample Input 2

4
15 5 2 10

Sample Output 2

Person 1 is already the strongest, so no more programming skill is needed.

Sample Input 3

3
100 100 100

Sample Output 3

B - Tomorrow

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder 国の暦では、1 年は 1 月から M 月までの M ヶ月からなり、どの月も 1 日から D 日までの D 日からなります。

AtCoder 国の暦で y 年 m 月 d 日の翌日は何年何月何日であるか求めてください。

制約

1000 \leq y \leq 9000
1 \leq m \leq M \leq 99
1 \leq d \leq D \leq 99
入力は全て整数である

入力

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

M D
y m d

出力

AtCoder 国の暦で y 年 m 月 d 日の翌日が y' 年 m' 月 d' 日であるとき、y',m',d' をこの順に空白区切りで出力せよ。

入力例 1

12 30
2023 12 30

出力例 1

2024 1 1

AtCoder 国の暦では 1 年は 12 ヶ月であり、どの月も 30 日からなります。よって、2023 年 12 月 30 日の翌日は 2024 年 1 月 1 日になります。

入力例 2

36 72
6789 23 45

出力例 2

6789 23 46

AtCoder 国の暦では 1 年は 36 ヶ月であり、どの月も 72 日からなります。よって、6789 年 23 月 45 日の翌日は 6789 年 23 月 46 日になります。

入力例 3

12 30
2012 6 20

出力例 3

2012 6 21

Score : 100 points

Problem Statement

In the calendar of AtCoder Kingdom, a year consists of M months from month 1 to month M, and each month consists of D days from day 1 to day D.

What day follows year y, month m, day d in this calendar?

Constraints

1000 \leq y \leq 9000
1 \leq m \leq M \leq 99
1 \leq d \leq D \leq 99
All input values are integers.

Input

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

M D
y m d

Output

If the day following year y, month m, day d in the calendar of AtCoder Kingdom is year y', month m', day d', print y', m', and d' in this order, separated by spaces.

Sample Input 1

12 30
2023 12 30

Sample Output 1

2024 1 1

In the calendar of the kingdom, a year consists of 12 months, and each month consists of 30 days. Thus, the day following year 2023, month 12, day 30 is year 2024, month 1, day 1.

Sample Input 2

36 72
6789 23 45

Sample Output 2

6789 23 46

In the calendar of the kingdom, one year consists of 36 months, and each month consists of 72 days. Thus, the day following year 6789, month 23, day 45 is year 6789, month 23, day 46.

Sample Input 3

12 30
2012 6 20

Sample Output 3

2012 6 21

C - AtCoder Quiz

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder では現在、 ABC , ARC , AGC , AHC の 4 つのコンテストが定期的に開催されています。

AtCoder で現在定期的に開催されているコンテストは S_1 , S_2 , S_3 とあと 1 つは何ですか?

制約

S_1 , S_2 , S_3 はそれぞれ、 ABC , ARC , AGC , AHC のいずれかである。
S_1 , S_2 , S_3 は相異なる。

入力

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

S_1
S_2
S_3

出力

答えを出力せよ。

入力例 1

ARC
AGC
AHC

出力例 1

ABC

ARC , AGC , AHC の 3つが入力として与えられているので、残りの 1 つはABC です。

入力例 2

AGC
ABC
ARC

出力例 2

AHC

Score : 200 points

Problem Statement

AtCoder currently holds four series of regular contests: ABC, ARC, AGC, and AHC.

What is the series of regular contests currently held by AtCoder in addition to S_1, S_2, and S_3?

Constraints

Each of S_1, S_2, and S_3 is ABC, ARC, AGC, or AHC.
S_1, S_2, and S_3 are pairwise different.

Input

Input is given from Standard Input in the following format:

S_1
S_2
S_3

Output

Print the answer.

Sample Input 1

ARC
AGC
AHC

Sample Output 1

ABC

Given in input are ARC, AGC, and AHC. The rest is ABC.

Sample Input 2

AGC
ABC
ARC

Sample Output 2

AHC

D - Fill the Gaps

Time Limit: 2 sec / Memory Limit: 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 - Lining Up 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

人 1, 人 2,\ldots, 人 N の N 人が一列に並んでいます。

並び方の情報が長さ N の数列 A=(A _ 1,A _ 2,\ldots,A _ N) として与えられます。

A _ i\ (1\leq i\leq N) は次のような情報を表しています。

A _ i=-1 のとき、人 i は先頭に並んでいる。
A _ i\neq -1 のとき、人 i は人 A _ i のすぐ後ろに並んでいる。

列に並んでいる人の番号を先頭から順番に出力してください。

制約

1\leq N\leq3\times10 ^ 5
A _ i=-1 もしくは 1\leq A _ i\leq N\ (1\leq i\leq N)
情報と矛盾しないような N 人の並び方がただ 1 通り存在する
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N

出力

人 s _ 1, 人 s _ 2,\ldots, 人 s _ N がこの順に列に並んでいるとき、s _ 1,s _ 2,\ldots,s _ N をこの順に空白を区切りとして出力せよ。

入力例 1

6
4 1 -1 5 3 2

出力例 1

3 5 4 1 2 6

先頭から、人 3, 人 5, 人 4, 人 1, 人 2, 人 6 がこの順に列に並んでいるとき、与えられた情報と一致しています。

実際、

人 1 は人 4 のすぐ後ろに並んでいます。
人 2 は人 1 のすぐ後ろに並んでいます。
人 3 は先頭に並んでいます。
人 4 は人 5 のすぐ後ろに並んでいます。
人 5 は人 3 のすぐ後ろに並んでいます。
人 6 は人 2 のすぐ後ろに並んでいます。

となり、与えられた情報と一致していることが確認できます。

よって、3,5,4,1,2,6 をこの順に空白区切りで出力してください。

入力例 2

10
-1 1 2 3 4 5 6 7 8 9

出力例 2

1 2 3 4 5 6 7 8 9 10

入力例 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

出力例 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

Score: 300 points

Problem Statement

There are N people standing in a line: person 1, person 2, \ldots, person N.

You are given the arrangement of the people as a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

A _ i\ (1\leq i\leq N) represents the following information:

if A _ i=-1, person i is at the front of the line;
if A _ i\neq -1, person i is right behind person A _ i.

Print the people's numbers in the line from front to back.

Constraints

1\leq N\leq3\times10 ^ 5
A _ i=-1 or 1\leq A _ i\leq N\ (1\leq i\leq N)
There is exactly one way to arrange the N people consistent with the information given.
All input values are integers.

Input

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

N
A _ 1 A _ 2 \ldots A _ N

Output

If person s _ 1, person s _ 2, \ldots, person s _ N are standing in the line in this order, print s _ 1, s _ 2, \ldots, and s _ N in this order, separated by spaces.

Sample Input 1

6
4 1 -1 5 3 2

Sample Output 1

3 5 4 1 2 6

If person 3, person 5, person 4, person 1, person 2, and person 6 stand in line in this order from front to back, the arrangement matches the given information.

Indeed, it can be seen that:

person 1 is standing right behind person 4,
person 2 is standing right behind person 1,
person 3 is at the front of the line,
person 4 is standing right behind person 5,
person 5 is standing right behind person 3, and
person 6 is standing right behind person 2.

Thus, print 3, 5, 4, 1, 2, and 6 in this order, separated by spaces.

Sample Input 2

10
-1 1 2 3 4 5 6 7 8 9

Sample Output 2

1 2 3 4 5 6 7 8 9 10

Sample Input 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

Sample Output 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14