AtCoder Daily Training EASY 2025/04/30 20:00start

A - Tomorrow

実行時間制限: 2 sec / メモリ制限: 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

B - Strictly Increasing?

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

配点 : 100 点

問題文

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

A が狭義単調増加であるとは、 1\leq i\lt N なるすべての整数 i について A_i\lt A_{i+1} が成り立つことをを指します。

A が狭義単調増加であるか判定してください。

制約

2\leq N\leq 100
1\leq A_i\leq 1000 (1\leq i\leq N)
入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

A が狭義単調増加であるならば Yes と、そうでないならば No と出力せよ。

正誤判定器は大文字と小文字を区別せず、どちらも受理する。例えば、答えが Yes となるときに yes や YES、yEs などと出力しても正解と判定される。

入力例 1

3
1 2 5

出力例 1

Yes

A_1\lt A_2 かつ A_2\lt A_3 なので A は狭義単調増加です。

入力例 2

3
3 9 5

出力例 2

No

A_1\lt A_2 ですが、A_2\lt A_3 でないので A は狭義単調増加ではありません。

入力例 3

10
1 1 2 3 5 8 13 21 34 55

出力例 3

No

A_1\lt A_2 でないので A は狭義単調増加ではありません。

Score : 100 points

Problem Statement

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

Determine whether A is strictly increasing, that is, whether A_i < A_{i+1} holds for every integer i with 1 \leq i < N.

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 1000 \ (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 A is strictly increasing, print Yes; otherwise, print No.

The judge is case-insensitive. For example, if the correct answer is Yes, any of yes, YES, and yEs will be accepted.

Sample Input 1

3
1 2 5

Sample Output 1

Yes

A_1 < A_2 and A_2 < A_3, so A is strictly increasing.

Sample Input 2

3
3 9 5

Sample Output 2

No

A_1 < A_2, but A_2 < A_3 does not hold, so A is not strictly increasing.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

No

A_1 < A_2 does not hold, so A is not strictly increasing.

C - Slimes

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

配点 : 200 点

問題文

A 匹のスライムがいます。

すぬけくんが 1 回叫ぶたびに、スライムは K 倍に増殖します。

スライムが B 匹以上になるには、すぬけくんは最小で何回叫ぶ必要があるでしょうか？

制約

1 \leq A \leq B \leq 10^9
2 \leq K \leq 10^9
入力は全て整数

入力

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

A B K

出力

答えを出力せよ。

入力例 1

1 4 2

出力例 1

はじめ、スライムが 1 匹います。すぬけくんが 1 回叫ぶとスライムは 2 匹になり、 2 回叫ぶとスライムは 4 匹になります。4 匹以上になるためには、最小で 2 回叫ぶ必要があります。

入力例 2

7 7 10

出力例 2

はじめからスライムは 7 匹います。

入力例 3

31 415926 5

出力例 3

Score : 200 points

Problem Statement

There are A slimes.

Each time Snuke shouts, the slimes multiply by K times.

In order to have B or more slimes, at least how many times does Snuke need to shout?

Constraints

1 \leq A \leq B \leq 10^9
2 \leq K \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B K

Output

Print the answer.

Sample Input 1

1 4 2

Sample Output 1

We start with one slime. After Snuke's first shout, we have two slimes; after his second shout, we have four slimes. Thus, he needs to shout at least twice to have four or more slimes.

Sample Input 2

7 7 10

Sample Output 2

We have seven slimes already at the start.

Sample Input 3

31 415926 5

Sample Output 3

D - Trimmed Mean

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

配点 : 200 点

問題文

高橋君は体操の大会に参加しています。
大会では、5N 人の審査員それぞれが高橋君の演技に対して評点をつけ、それらを元に次のように高橋君の得点が決定されます。

高い評点をつけた方から順に N 人の審査員による評点を無効にする。
低い評点をつけた方から順に N 人の審査員による評点を無効にする。
残りの 3N 人の審査員による評点の平均点を高橋君の得点とする。

より厳密には、審査員がつけた得点の多重集合 S (|S|=5N) に対して次の操作を行って得られたものが高橋君の得点となります。

「S の最大の要素(複数ある場合はそのうちの 1 つ)を選び、S から取り除く」という操作を N 回繰り返す。
「S の最小の要素(複数ある場合はそのうちの 1 つ)を選び、S から取り除く」という操作を N 回繰り返す。
S に残った 3N 個の要素の平均を高橋君の得点とする。

高橋君の演技に対する、i 人目 (1\leq i\leq 5N) の審査員の評点は X_i 点でした。高橋君の得点を計算してください。

制約

1\leq N\leq 100
0\leq X_i\leq 100
入力はすべて整数

入力

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

N
X_1 X_2 \ldots X_{5N}

出力

高橋君の得点を出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。

入力例 1

1
10 100 20 50 30

出力例 1

33.333333333333336

N=1 であるので、評点が高い方と低い方からそれぞれ 1 人ずつの審査員による評点を無効にします。
1 番高い評点をつけた審査員は 2 人目 (100 点) であるため、これを無効にします。
また、1 番低い評点をつけた審査員は 1 人目 (10 点) であるため、これも無効にします。
よって、最終的な平均点は \displaystyle\frac{20+50+30}{3}=33.333\cdots となります。

出力は、真の値との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる事に注意してください。

入力例 2

2
3 3 3 4 5 6 7 8 99 100

出力例 2

5.500000000000000

N=2 であるので、評点が高い方と低い方からそれぞれ 2 人ずつの審査員による評点を無効にします。
1,2 番目に高い評点をつけた審査員は順に 10 人目 (100 点), 9 人目 (99 点) であるため、これを無効にします。
1 番低い評点をつけた審査員は 1,2,3 人目 (3 点) の 3 人がいるため、このうち 2 人を無効とします。
よって、答えは \displaystyle\frac{3+4+5+6+7+8}{6}=5.5 となります。

1 番低い評点をつけた 3 人のうちどの 2 人を無効にしたかは、答えに影響しない事に注意してください。

Score : 200 points

Problem Statement

Takahashi is participating in a gymnastic competition.
In the competition, each of 5N judges grades Takahashi's performance, and his score is determined as follows:

Invalidate the grades given by the N judges who gave the highest grades.
Invalidate the grades given by the N judges who gave the lowest grades.
Takahashi's score is defined as the average of the remaining 3N judges' grades.

More formally, Takahashi's score is obtained by performing the following procedure on the multiset of the judges' grades S (|S|=5N):

Repeat the following operation N times: choose the maximum element (if there are multiple such elements, choose one of them) and remove it from S.
Repeat the following operation N times: choose the minimum element (if there are multiple such elements, choose one of them) and remove it from S.
Takahashi's score is defined as the average of the 3N elements remaining in S.

The i-th (1\leq i\leq 5N) judge's grade for Takahashi's performance was X_i points. Find Takahashi's score.

Constraints

1\leq N\leq 100
0\leq X_i\leq 100
All values in the input are integers.

Input

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

N
X_1 X_2 \ldots X_{5N}

Output

Print Takahashi's score.
Your answer will be considered correct if the absolute or relative error from the true value is at most 10^{-5}.

Sample Input 1

1
10 100 20 50 30

Sample Output 1

33.333333333333336

Since N=1, the grade given by one judge who gave the highest grade, and one with the lowest, are invalidated.
The 2-nd judge gave the highest grade (100 points), which is invalidated.
Additionally, the 1-st judge gave the lowest grade (10 points), which is also invalidated.
Thus, the average is \displaystyle\frac{20+50+30}{3}=33.333\cdots.

Note that the output will be considered correct if the absolute or relative error from the true value is at most 10^{-5}.

Sample Input 2

2
3 3 3 4 5 6 7 8 99 100

Sample Output 2

5.500000000000000

Since N=2, the grades given by the two judges who gave the highest grades, and two with the lowest, are invalidated.
The 10-th and 9-th judges gave the highest grades (100 and 99 points, respectively), which are invalidated.
Three judges, the 1-st, 2-nd, and 3-rd, gave the lowest grade (3 points), so two of them are invalidated.
Thus, the average is \displaystyle\frac{3+4+5+6+7+8}{6}=5.5.

Note that the choice of the two invalidated judges from the three with the lowest grades does not affect the answer.

E - Festival

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

配点 : 250 点

問題文

AtCoder 王国では、これから N 日間のお祭りが開催されます。そのうち、A_1 日目、A_2 日目、\dots、A_M 日目の M 日では花火が上がります。ここで、お祭りの最終日には花火が上がることが保証されます。(つまり、A_M=N が保証されます。)

i=1,2,\dots,N に対して、以下の問題を解いてください。

i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後か？ただし、i 日目に花火が上がる場合 0 日後とする。

制約

1 \le M \le N \le 2 \times 10^5
1 \le A_1 < A_2 < \dots < A_M = N
入力は全て整数

入力

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

N M
A_1 A_2 \dots A_M

出力

N 行出力せよ。

i(1 \le i \le N) 行目には、i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後かを整数として出力せよ。

入力例 1

3 2
2 3

出力例 1

1
0
0

AtCoder 王国ではお祭りを 3 日間開催し、2,3 日目に花火が上がります。

1 日目以降で初めて花火が上がるのは 2 日目なので、1 日目から数えて 1 日後です。
2 日目以降で初めて花火が上がるのは 2 日目なので、2 日目から数えて 0 日後です。
3 日目以降で初めて花火が上がるのは 3 日目なので、3 日目から数えて 0 日後です。

入力例 2

8 5
1 3 4 7 8

出力例 2

Score : 250 points

Problem Statement

The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)

For each i=1,2,\dots,N, solve the following problem.

How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.

Constraints

1 \le M \le N \le 2 \times 10^5
1 \le A_1 < A_2 < \dots < A_M = N
All input values are integers.

Input

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

N M
A_1 A_2 \dots A_M

Output

Print N lines.

The i-th line (1 \le i \le N) should contain an integer representing the number of days from the i-th day until fireworks are launched for the first time on or after the i-th day.

Sample Input 1

3 2
2 3

Sample Output 1

1
0
0

The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.

From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.

Sample Input 2

8 5
1 3 4 7 8

Sample Output 2