AtCoder Daily Training EASY 2025/06/24 17:30start

A - Candy Button

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

不思議なボタンがあります。このボタンを押すと飴を 1 つもらえますが、前回飴をもらってからの経過時間が C 秒未満である場合はもらえません。

高橋君はこのボタンを N 回押してみることにしました。 i 回目にボタンを押すのは今から T_i 秒後です。

高橋君は何個の飴をもらうことができますか？

制約

1\leq N \leq 100
1\leq C\leq 1000
0\leq T_1 < T_2 < \dots < T_N \leq 1000
入力は全て整数

入力

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

N C
T_1 T_2 \dots T_N

出力

高橋君がもらうことのできる飴の個数を出力せよ。

入力例 1

6 5
1 3 7 8 10 12

出力例 1

高橋君はボタンを 6 回押します。

1 回目（今から 1 秒後）：初めてボタンを押すときは必ず飴を 1 つもらえます。
2 回目（今から 3 秒後）：前回飴をもらってからの経過時間が 3-1=2<C 秒なので、飴はもらえません。
3 回目（今から 7 秒後）：前回飴をもらってからの経過時間が 7-1=6\geq C 秒なので、飴を 1 つもらえます。
4 回目（今から 8 秒後）：前回飴をもらってからの経過時間が 8-7=1<C 秒なので、飴はもらえません。
5 回目（今から 10 秒後）：前回飴をもらってからの経過時間が 10-7=3<C 秒なので、飴はもらえません。
6 回目（今から 12 秒後）：前回飴をもらってからの経過時間が 12-7=5\geq C 秒なので、飴を 1 つもらえます。

よって、高橋君は飴を 3 個もらうことができます。

入力例 2

3 2
0 2 4

出力例 2

入力例 3

10 3
0 3 4 6 9 12 15 17 19 20

出力例 3

Score : 150 points

Problem Statement

There is a mysterious button. When you press this button, you receive one candy, unless less than C seconds have elapsed since you last received a candy.

Takahashi decided to press this button N times. He will press the button for the i-th time T_i seconds from now.

How many candies will he receive?

Constraints

1 \leq N \leq 100
1 \leq C \leq 1000
0 \leq T_1 < T_2 < \dots < T_N \leq 1000
All input values are integers.

Input

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

N C
T_1 T_2 \dots T_N

Output

Print the number of candies that Takahashi will receive.

Sample Input 1

6 5
1 3 7 8 10 12

Sample Output 1

Takahashi will press the button six times.

1st press (1 second from now): You always receive a candy when pressing the button for the first time.
2nd press (3 seconds from now): 3 - 1 = 2 < C seconds have elapsed since he last received a candy, so he does not receive a candy.
3rd press (7 seconds from now): 7 - 1 = 6 \geq C seconds have elapsed since he last received a candy, so he receives a candy.
4th press (8 seconds from now): 8 - 7 = 1 < C second has elapsed since he last received a candy, so he does not receive a candy.
5th press (10 seconds from now): 10 - 7 = 3 < C seconds have elapsed since he last received a candy, so he does not receive a candy.
6th press (12 seconds from now): 12 - 7 = 5 \geq C seconds have elapsed since he last received a candy, so he receives a candy.

Therefore, he receives three candies.

Sample Input 2

3 2
0 2 4

Sample Output 2

Sample Input 3

10 3
0 3 4 6 9 12 15 17 19 20

Sample Output 3

B - Buildings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 個のビルが横一列に並んでいて、左から i 番目のビルの高さは H_i です。

左から 1 番目のビルより高いビルが存在するか判定し、存在する場合その内最も左のビルは左から何番目か求めてください。

制約

1\leq N\leq 100
1\leq H_i \leq 100
入力される数値は全て整数

入力

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

N 
H_1 H_2 \ldots H_N

出力

左から 1 番目のビルより高いビルが存在しない場合 -1 を出力せよ。

存在する場合、その内最も左のビルは左から何番目か出力せよ。

入力例 1

4
3 2 5 2

出力例 1

左から 1 番目のビルより高いビルは、左から 3 番目のビルです。

入力例 2

3
4 3 2

出力例 2

-1

左から 1 番目のビルより高いビルは存在しません。

入力例 3

7
10 5 10 2 10 13 15

出力例 3

左から 1 番目のビルより高いビルは、左から 6 番目のビルと左から 7 番目のビルです。その内最も左のビルは左から 6 番目のビルです。

Score: 100 points

Problem Statement

There are N buildings aligned in a row. The i-th building from the left has a height of H_i.

Determine if there is a building taller than the first one from the left. If such a building exists, find the position of the leftmost such building from the left.

Constraints

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

Input

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

N
H_1 H_2 \ldots H_N

Output

If no building is taller than the first one from the left, print -1.

If such a building exists, print the position (index) of the leftmost such building from the left.

Sample Input 1

4
3 2 5 2

Sample Output 1

The building taller than the first one from the left is the third one from the left.

Sample Input 2

3
4 3 2

Sample Output 2

-1

No building is taller than the first one from the left.

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.

C - Glass and Mug

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 社はグラスとマグカップを販売しています。

高橋君は容量が G ml のグラスと、容量が M ml のマグカップを 1 つずつ持っています。
ここで、G,M は G<M をみたします。

最初、グラスとマグカップはいずれも空です。
以下の操作を K 回繰り返した後で、グラスとマグカップに水がそれぞれ何 ml ずつ入っているか求めてください。

グラスが水で満たされているとき、すなわちグラスにちょうど G ml 入っているとき、グラスの水をすべて捨てる。
そうでなく、マグカップが空であるとき、マグカップを水で満たす。
上のいずれでもないとき、マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。

制約

1\leq K\leq 100
1\leq G<M\leq 1000
G,M,K は整数

入力

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

K G M

出力

操作を K 回行った後で、グラスとマグカップに水がそれぞれ何 ml ずつ入っているか、この順に空白区切りで出力せよ。

入力例 1

5 300 500

出力例 1

200 500

操作は次の順で行われます。最初、グラスとマグカップはいずれも空です。

マグカップを水で満たす。グラスには 0 ml, マグカップには 500 ml 入った状態になる。
グラスが満たされるまでマグカップからグラスに水を移す。グラスには 300 ml, マグカップには 200 ml 入った状態になる。
グラスの水をすべて捨てる。グラスには 0 ml, マグカップには 200 ml 入った状態になる。
マグカップが空になるまでマグカップからグラスに水を移す。グラスには 200 ml, マグカップには 0 ml 入った状態になる。
マグカップを水で満たす。グラスには 200 ml, マグカップには 500 ml 入った状態になる。

よって、5 回の操作の後でグラスには 200 ml, マグカップには 500 ml 入った状態になります。ゆえに、200, 500 を空白区切りでこの順に出力します。

入力例 2

5 100 200

出力例 2

0 0

Score : 200 points

Problem Statement

AtCoder Inc. sells glasses and mugs.

Takahashi has a glass with a capacity of G milliliters and a mug with a capacity of M milliliters.
Here, G<M.

Initially, both the glass and the mug are empty.
After performing the following operation K times, determine how many milliliters of water are in the glass and the mug, respectively.

When the glass is filled with water, that is, the glass contains exactly G milliliters of water, discard all the water from the glass.
Otherwise, if the mug is empty, fill the mug with water.
Otherwise, transfer water from the mug to the glass until the mug is empty or the glass is filled with water.

Constraints

1\leq K\leq 100
1\leq G<M\leq 1000
G, M, and K are integers.

Input

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

K G M

Output

Print the amounts, in milliliters, of water in the glass and the mug, in this order, separated by a space, after performing the operation K times.

Sample Input 1

5 300 500

Sample Output 1

200 500

The operation will be performed as follows. Initially, both the glass and the mug are empty.

Fill the mug with water. The glass has 0 milliliters, and the mug has 500 milliliters of water.
Transfer water from the mug to the glass until the glass is filled. The glass has 300 milliliters, and the mug has 200 milliliters of water.
Discard all the water from the glass. The glass has 0 milliliters, and the mug has 200 milliliters of water.
Transfer water from the mug to the glass until the mug is empty. The glass has 200 milliliters, and the mug has 0 milliliters of water.
Fill the mug with water. The glass has 200 milliliters, and the mug has 500 milliliters of water.

Thus, after five operations, the glass has 200 milliliters, and the mug has 500 milliliters of water. Hence, print 200 and 500 in this order, separated by a space.

Sample Input 2

5 100 200

Sample Output 2

0 0

D - Booby Prize

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1,\ldots,N の番号のついた N 人の選手がゲームを行いました。選手 i のスコアは A_i であり、スコアが小さい方が上位になります。

ブービー賞に該当する選手、すなわち、下位から 2 番目の選手の番号を求めてください。

制約

2 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^9
A_i は相異なる
入力に含まれる値は全て整数である

入力

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

N
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

6
1 123 12345 12 1234 123456

出力例 1

6 人中 5 位になるのは、選手 3 です。

入力例 2

5
3 1 4 15 9

出力例 2

Score : 200 points

Problem Statement

N players, who are numbered 1, \ldots, N, have played a game. Player i has scored A_i, and a player with a smaller score ranks higher.

The player who ranks the second lowest will receive a booby prize. Who is this player? Answer with an integer representing the player.

Constraints

2 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^9
A_i are distinct.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

6
1 123 12345 12 1234 123456

Sample Output 1

It is Player 3 who ranks fifth among the six players.

Sample Input 2

5
3 1 4 15 9

Sample Output 2

E - Path Graph?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, 2, \dots, N の番号が、辺には 1, 2, \dots, M の番号が付けられています。
辺 i \, (i = 1, 2, \dots, M) は頂点 u_i, v_i を結んでいます。

このグラフがパスグラフであるか判定してください。

単純無向グラフとは

単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

パスグラフとは

頂点に 1, 2, \dots, N の番号が付けられたN 頂点のグラフがパスグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。

全ての i = 1, 2, \dots, N-1 に対して、頂点 v_i, v_{i+1} を結ぶ辺が存在する
整数 i, j が 1 \leq i, j \leq N, |i - j| \geq 2 を満たすならば、頂点 v_i, v_j を結ぶ辺は存在しない

制約

2 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
入力される値は全て整数
入力で与えられるグラフは単純

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

与えられたグラフがパスグラフなら Yes、そうでないなら No と出力せよ。

入力例 1

出力例 1

Yes

与えらえたグラフは下図のようであり、これはパスグラフです。

example_00

入力例 2

2 0

出力例 2

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_01

入力例 3

出力例 3

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_02

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

What is a simple undirected graph?

A simple undirected graph is a graph without self-loops or multiple edges whose edges do not have a direction.

What is a path graph?

A graph with N vertices numbered 1, 2, \dots, N is said to be a path graph if and only if there is a sequence (v_1, v_2, \dots, v_N) that is a permutation of (1, 2, \dots, N) and satisfies the following conditions:

For all i = 1, 2, \dots, N-1, there is an edge connecting vertices v_i and v_{i+1}.
If integers i and j satisfies 1 \leq i, j \leq N and |i - j| \geq 2, then there is no edge that connects vertices v_i and v_j.

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
All values in the input are integers.
The graph given in the input is simple.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print Yes if the given graph is a path graph; print No otherwise.

Sample Input 1

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

example_00

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

example_01

Sample Input 3

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

example_02