AtCoder Daily Training EASY 2026/09/02 18:00start

A - Christmas Present

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

野球少年の高橋君は今年とても良い子にしていたので、サンタさんはバットかグローブのうち値段が高い方を高橋君にプレゼントすることにしました。

バットの値段が B 円、グローブの値段が G 円 (B\neq G) のとき、サンタさんが高橋君にプレゼントするのはどちらですか？

制約

B,G は 1 以上 1000 以下の相異なる整数

入力

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

B G

出力

サンタさんが高橋君にプレゼントするのがバットであるとき Bat を、グローブであるとき Glove を出力せよ。

入力例 1

300 100

出力例 1

Bat

バットの方がグローブより値段が高いので、サンタさんは高橋君にバットをプレゼントします。

入力例 2

334 343

出力例 2

Glove

グローブの方がバットより値段が高いので、サンタさんは高橋君にグローブをプレゼントします。

Score : 100 points

Problem Statement

Takahashi, a young baseball enthusiast, has been a very good boy this year, so Santa has decided to give him a bat or a glove, whichever is more expensive.

If a bat costs B yen and a glove costs G yen (B\neq G), which one will Santa give to Takahashi?

Constraints

B and G are different integers between 1 and 1000, inclusive.

Input

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

B G

Output

If Santa gives Takahashi a bat, print Bat; if Santa gives him a glove, print Glove.

Sample Input 1

300 100

Sample Output 1

Bat

The bat is more expensive than the glove, so Santa will give Takahashi the bat.

Sample Input 2

334 343

Sample Output 2

Glove

The glove is more expensive than the bat, so Santa will give Takahashi the glove.

B - Zero Sum Game

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 から N の番号が付けられた N 人の人がおり、この中で一対一の勝敗のつくゲームを何度か行いました。N 人は最初にそれぞれ持ち点として 0 を持っており、各ゲームでは勝者の持ち点が 1 増え、敗者の持ち点が 1 減ります（持ち点が負になることもあります）。最終的に人 i\ (1\leq i\leq N-1) の持ち点が A_i になったとき、人 N の持ち点を求めてください。なお、ゲームの進行によらず最終的な人 N の持ち点は一意に定まることが示せます。

制約

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

入力

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

N
A_1 A_2 \ldots A_{N-1}

出力

答えを出力せよ。

入力例 1

4
1 -2 -1

出力例 1

最終的に人 1,2,3 の持ち点が 1,-2,-1 となるような進行として、例えば次のようなものが考えられます。

最初、人 1,2,3,4 の持ち点はそれぞれ 0,0,0,0 である。
人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-1,0,0 である。
人 1 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 0,-1,0,1 である。
人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-2,0,1 である。
人 2 と 3 が対戦して、人 2 が勝利する。4 人の持ち点はそれぞれ 1,-1,-1,1 である。
人 2 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 1,-2,-1,2 である。

この場合、人 4 の持ち点は 2 になります。ほかにも別の進行が考えられますが、どのような進行であっても人 4 の持ち点は 2 になります。

入力例 2

3
0 0

出力例 2

入力例 3

6
10 20 30 40 50

出力例 3

-150

Score: 100 points

Problem Statement

There are N people labeled 1 to N, who have played several one-on-one games without draws. Initially, each person started with 0 points. In each game, the winner's score increased by 1 and the loser's score decreased by 1 (scores can become negative). Determine the final score of person N if the final score of person i\ (1\leq i\leq N-1) is A_i. It can be shown that the final score of person N is uniquely determined regardless of the sequence of games.

Constraints

2 \leq N \leq 100
-100 \leq A_i \leq 100
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-1}

Output

Print the answer.

Sample Input 1

4
1 -2 -1

Sample Output 1

Here is one possible sequence of games where the final scores of persons 1, 2, 3 are 1, -2, -1, respectively.

Initially, persons 1, 2, 3, 4 have 0, 0, 0, 0 points, respectively.
Persons 1 and 2 play, and person 1 wins. The players now have 1, -1, 0, 0 point(s).
Persons 1 and 4 play, and person 4 wins. The players now have 0, -1, 0, 1 point(s).
Persons 1 and 2 play, and person 1 wins. The players now have 1, -2, 0, 1 point(s).
Persons 2 and 3 play, and person 2 wins. The players now have 1, -1, -1, 1 point(s).
Persons 2 and 4 play, and person 4 wins. The players now have 1, -2, -1, 2 point(s).

In this case, the final score of person 4 is 2. Other possible sequences of games exist, but the score of person 4 will always be 2 regardless of the progression.

Sample Input 2

3
0 0

Sample Output 2

Sample Input 3

6
10 20 30 40 50

Sample Output 3

-150

C - Yellow and Red Card

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号がついた N 人の選手がサッカーの試合をします。
選手が反則を犯したとき、その選手には イエローカード と レッドカード のどちらかが提示されます。
以下の条件のうち一方を満たした選手は 退場処分 と呼ばれるペナルティを受けます。

イエローカードを累計 2 回提示される。
レッドカードを提示される。

なお、退場処分を受けた選手にそれ以降カードが提示されることはありません。

あなたはこの試合を観戦します。はじめ、すべての選手はカードを 1 回も提示されていません。
Q 個のイベントが発生するので、イベントで聞かれる質問に正しく答えてください。
イベントは 3 種類あり、c x (c は 1, 2, 3 のいずれか) という形式で入力から与えられます。イベントの説明は次の通りです。

1 x : 選手 x にイエローカードが提示される。
2 x : 選手 x にレッドカードが提示される。
3 x : あなたは選手 x が退場処分を受けたかを質問される。選手 x が退場処分を受けていれば Yes と、そうでなければ No と答える。

制約

1 \leq N \leq 100
1 \leq Q \leq 100
全てのイベントにおいて 1 \leq x \leq N
3 種類目のイベントは少なくとも 1 個以上存在する
すでに退場処分を受けた選手にカードが提示されることはない
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ただし、\text{event}_i は i 番目に発生するイベントを意味する。

N Q
\text{event}_1
\text{event}_2
\vdots
\text{event}_Q

イベントは次の 3 つのいずれかの形式で入力される。

1 x

2 x

3 x

出力

入力で与えられる 3 種類目のイベントの個数を X として、X 行出力せよ。
i 行目には、3 種類目のイベントのうち i 番目のもので聞かれる質問について、選手 x が退場処分を受けていれば Yes を、そうでなければ No を出力せよ。

入力例 1

出力例 1

No
No
Yes
No
Yes
No

イベントを時系列順にすべて説明すると次の通りです。

1 番目のイベントでは、あなたは選手 1 が退場処分を受けたかを質問されます。選手 1 は退場処分を受けていないので No を出力します。
2 番目のイベントでは、あなたは選手 2 が退場処分を受けたかを質問されます。選手 2 は退場処分を受けていないので No を出力します。
3 番目のイベントでは、選手 2 にイエローカードが提示されます。
4 番目のイベントでは、選手 1 にレッドカードが提示されます。選手 1 は退場処分を受けます。
5 番目のイベントでは、あなたは選手 1 が退場処分を受けたかを質問されます。選手 1 は退場処分を受けたので Yes を出力します。
6 番目のイベントでは、あなたは選手 2 が退場処分を受けたかを質問されます。選手 2 は退場処分を受けていないので No を出力します。
7 番目のイベントでは、選手 2 にイエローカードが提示されます。選手 2 は退場処分を受けます。
8 番目のイベントでは、あなたは選手 2 が退場処分を受けたかを質問されます。選手 2 は退場処分を受けたので Yes を出力します。
9 番目のイベントでは、あなたは選手 3 が退場処分を受けたかを質問されます。選手 3 は退場処分を受けていないので No を出力します。

Score : 200 points

Problem Statement

N players numbered 1 to N will play a soccer game.
When a player commits an offense, that player will receive a yellow card or a red card.
A player who satisfies one of the following conditions will be removed from the game.

Accumulates two yellow cards.
Receives a red card.

Once a player is removed, that player will no longer receive any cards.

You will watch this game. Initially, the players have not received any cards.
There will be Q events. Correctly answer the questions asked in the events.
There are three kinds of events, which are given in the format c x from the input, where c is 1, 2, or 3. The events are as follows.

1 x: Player x receives a yellow card.
2 x: Player x receives a red card.
3 x: You are asked whether player x has been removed from the game. Answer Yes or No.

Constraints

1 \leq N \leq 100
1 \leq Q \leq 100
1 \leq x \leq N in all events.
There is at least one event of the third kind.
A player who has been removed will no longer receive any cards.
All values in the input are integers.

Input

The input is given from Standard Input in the following format, where \text{event}_i denotes the i-th event.

N Q
\text{event}_1
\text{event}_2
\vdots
\text{event}_Q

Each event is in one of the following formats:

1 x

2 x

3 x

Output

Print X lines, where X is the number of events of the third kind in the input.
The i-th line should contain Yes if, for the i-th event of the third kind, player x has been removed from the game, and No otherwise.

Sample Input 1

Sample Output 1

No
No
Yes
No
Yes
No

Here are all the events in chronological order.

In the 1-st event, you are asked whether player 1 has been removed from the game. Player 1 has not been removed, so you should print No.
In the 2-nd event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 3-rd event, player 2 receives a yellow card.
In the 4-th event, player 1 receives a red card and is removed from the game.
In the 5-th event, you are asked whether player 1 has been removed from the game. Player 1 has been removed, so you should print Yes.
In the 6-th event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 7-th event, player 2 receives a yellow card and is removed from the game.
In the 8-th event, you are asked whether player 2 has been removed from the game. Player 2 has been removed, so you should print Yes.
In the 9-th event, you are asked whether player 3 has been removed from the game. Player 3 has not been removed, so you should print No.

D - Decrease 2 max elements

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の正整数列 A = (A_1, A_2, \dots ,A_N) が与えられます。高橋くんは、以下の操作を A に含まれる正の要素の個数が 1 つ以下になるまで繰り返します。

A を要素の降順に並び替える。それから、 A_1, A_2 を 1 減らす。

高橋くんが操作をする回数を求めてください。

制約

2 \leq N \leq 100
1 \leq A_i \leq 100
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ。

入力例 1

4
1 2 3 3

出力例 1

操作は以下のように進みます。

1 回目の操作で A = (2, 2, 2, 1) となる。
2 回目の操作で A = (1, 1, 2, 1) となる。
3 回目の操作で A = (1, 0, 1, 1) となる。
4 回目の操作で A = (0, 0, 1, 0) となる。A に含まれる正の要素の個数が 1 つ以下になったので、ここで操作を終了する。

入力例 2

3
1 1 100

出力例 2

Score : 200 points

Problem Statement

You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N). Takahashi repeats the following operation until A contains one or fewer positive elements:

Sort A in descending order. Then, decrease both A_1 and A_2 by 1.

Find the number of times he performs this operation.

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 100
All input values are integers.

Input

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

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

4
1 2 3 3

Sample Output 1

The process goes as follows:

After the 1st operation, A is (2, 2, 2, 1).
After the 2nd operation, A is (1, 1, 2, 1).
After the 3rd operation, A is (1, 0, 1, 1).
After the 4th operation, A is (0, 0, 1, 0). A no longer contains more than one positive elements, so the process ends here.

Sample Input 2

3
1 1 100

Sample Output 2

E - Festival

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