AtCoder Daily Training EASY 2026/08/04 16:00start

A - Shampoo

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

配点 : 100 点

問題文

高橋君の家には、高橋君、高橋君の父、高橋君の母の 3 人が住んでおり、全員が毎晩風呂で髪を洗います。
風呂には、高橋君の父、高橋君の母、高橋君の順に入り、それぞれシャンプーを A,B,C ミリリットル使います。

今朝の時点で、ボトルには V ミリリットルのシャンプーが残っていました。このまま補充しない時、初めてシャンプーが不足するのは誰が使おうとした時ですか？

制約

1 \leq V,A,B,C \leq 10^5
入力に含まれる値は全て整数である

入力

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

V A B C

出力

初めてシャンプーが不足するのが、高橋君の父が使おうとしたときならば F、高橋君の母が使おうとしたときならば M、高橋君が使おうとしたときならば T を出力せよ。

入力例 1

25 10 11 12

出力例 1

シャンプーは 25 ミリリットル残っています。

まず高橋君の父が 10 ミリリットル使い、残りは 15 ミリリットルになります。
次に高橋君の母が 11 ミリリットル使い、残りは 4 ミリリットルになります。
最後に高橋君が 12 ミリリットル使おうとしますが、4 ミリリットルしか残っておらず、不足しています。

入力例 2

30 10 10 10

出力例 2

シャンプーは 30 ミリリットル残っています。

まず高橋君の父が 10 ミリリットル使い、残りは 20 ミリリットルになります。
次に高橋君の母が 10 ミリリットル使い、残りは 10 ミリリットルになります。
続いて高橋君が 10 ミリリットル使い、残りは 0 ミリリットルになります。
翌日、高橋君の父が 10 ミリリットル使おうとしますが、0 ミリリットルしか残っておらず、不足しています。

入力例 3

100000 1 1 1

出力例 3

Score : 100 points

Problem Statement

Three people live in Takahashi's house: Takahashi, his father, and his mother. All of them wash their hair in the bathroom each night.
His father, his mother, and Takahashi take a bath in this order and use A, B, and C milliliters of shampoo, respectively.

This morning, the bottle contained V milliliters of shampoo. Without refilling, who will be the first to run short of shampoo to wash their hair?

Constraints

1 \leq V,A,B,C \leq 10^5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

V A B C

Output

If the first person to run short of shampoo to wash their hair is Takahashi's father, print F; if it is Takahashi's mother, print M; if it is Takahashi, print T.

Sample Input 1

25 10 11 12

Sample Output 1

Now, they have 25 milliliters of shampoo.

First, Takahashi's father uses 10 milliliters, leaving 15.
Next, Takahashi's mother uses 11 milliliters, leaving 4.
Finally, Takahashi tries to use 12 milliliters and runs short of shampoo since only 4 is remaining.

Sample Input 2

30 10 10 10

Sample Output 2

Now, they have 30 milliliters of shampoo.

First, Takahashi's father uses 10 milliliters, leaving 20.
Next, Takahashi's mother uses 10 milliliters, leaving 10.
Then, Takahashi uses 10 milliliters, leaving 0.
Next day, Takahashi's father tries to use 10 milliliters and runs short of shampoo since only 0 is remaining.

Sample Input 3

100000 1 1 1

Sample Output 3

B - Sanitize Hands

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

配点 : 100 点

問題文

消毒液の入ったボトルがあり、その消毒液によってちょうど M 本の手を消毒することができます。

N 人の宇宙人が順に手の消毒を行いに来ます。
i 人目 (1\leq i\leq N) の宇宙人は H_i 本の手を持っており、それぞれ自身のすべての手を 1 回ずつ消毒したいと考えています。

何人目の宇宙人までがすべての手を消毒できるか求めてください。
ただし、ある宇宙人が消毒を始める時点で、自身のすべての手を消毒する分の消毒液が残っていなかったとしても、その宇宙人はその消毒液を使い切ってしまうものとします。

制約

1\leq N,M\leq 100
1\leq H_i\leq 100
入力はすべて整数

入力

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

N M
H_1 H_2 \ldots H_N

出力

何人目の宇宙人までが自身のすべての手を消毒できるか出力せよ。

入力例 1

5 10
2 3 2 5 3

出力例 1

次の手順で宇宙人は自身の手を消毒します。

1 人目の宇宙人は自身の 2 本の手を消毒します。残りの消毒液によって、10-2=8 本の手を消毒できます。
2 人目の宇宙人は自身の 3 本の手を消毒します。残りの消毒液によって、8-3=5 本の手を消毒できます。
3 人目の宇宙人は自身の 2 本の手を消毒します。残りの消毒液によって、5-2=3 本の手を消毒できます。
4 人目の宇宙人は 5 本の手を持っていますが、消毒液は 3 本分しかないため消毒液を使い切り、かつ自身のすべての手を消毒できません。

よって、3 人目の宇宙人までが自身のすべての手を消毒できるため、3 を出力します。

入力例 2

5 10
2 3 2 3 5

出力例 2

入力例 3

1 5
1

出力例 3

すべての宇宙人が自身の手を消毒することができます。

Score : 100 points

Problem Statement

There is a bottle of disinfectant that can disinfect exactly M hands.

N aliens come one by one to disinfect their hands.
The i-th alien (1 \leq i \leq N) has H_i hands and wants to disinfect all of their hands once.

Determine how many aliens can disinfect all of their hands.
Here, even if there is not enough disinfectant left for an alien to disinfect all of their hands when they start, they will use up the remaining disinfectant.

Constraints

1 \leq N, M \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 M
H_1 H_2 \ldots H_N

Output

Print the number of aliens who can disinfect all of their hands.

Sample Input 1

5 10
2 3 2 5 3

Sample Output 1

The aliens disinfect their hands in the following steps:

The first alien disinfects their two hands. The remaining disinfectant can disinfect 10-2=8 hands.
The second alien disinfects their three hands. The remaining disinfectant can disinfect 8-3=5 hands.
The third alien disinfects their two hands. The remaining disinfectant can disinfect 5-2=3 hands.
The fourth alien has five hands, but there is only enough disinfectant for three hands, so they use up the disinfectant without disinfecting all of their hands.

Thus, the first three aliens can disinfect all of their hands, so print 3.

Sample Input 2

5 10
2 3 2 3 5

Sample Output 2

Sample Input 3

1 5
1

Sample Output 3

All aliens can disinfect their hands.

C - Hard Calculation

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

配点 : 200 点

問題文

正整数 A,B が与えられます。
A+B を(十進法で)計算する時、繰り上がりが生じないなら Easy 、生じるなら Hard と出力してください。

制約

A,B は整数
1 \le A,B \le 10^{18}

入力

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

A B

出力

繰り上がりが生じないなら Easy 、生じるなら Hard と出力せよ。

入力例 1

229 390

出力例 1

Hard

229+390 を計算する際、十の位から百の位へと繰り上がりが発生します。よって、答えは Hard です。

入力例 2

123456789 9876543210

出力例 2

Easy

繰り上がりは発生しません。答えは Easy です。
また、入力が 32bit 整数に収まらないこともあります。

Score : 200 points

Problem Statement

You are given positive integers A and B.
Let us calculate A+B (in decimal). If it does not involve a carry, print Easy; if it does, print Hard.

Constraints

A and B are integers.
1 \le A,B \le 10^{18}

Input

Input is given from Standard Input in the following format:

A B

Output

If the calculation does not involve a carry, print Easy; if it does, print Hard.

Sample Input 1

229 390

Sample Output 1

Hard

When calculating 229+390, we have a carry from the tens digit to the hundreds digit, so the answer is Hard.

Sample Input 2

123456789 9876543210

Sample Output 2

Easy

We do not have a carry here; the answer is Easy.
Note that the input may not fit into a 32-bit integer.

D - Commencement

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

配点 : 200 点

問題文

英小文字からなる文字列 S が良い文字列であるとは、すべての 1 以上の整数 i について次の性質が成り立つことであるとします。

S にちょうど i 回現れる文字はちょうど 0 種類またはちょうど 2 種類ある

文字列 S が与えられるので、 S が良い文字列か判定してください。

制約

S は英小文字からなる長さ 1 以上 100 以下の文字列

入力

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

出力

S が良い文字列ならば Yes を、そうでないならば No を出力せよ。

入力例 1

commencement

出力例 1

Yes

文字列 commencement にちょうど i 回現れる文字の種類数は以下のとおりです。

i=1: o, t の 2 種類
i=2: c, n の 2 種類
i=3: e, m の 2 種類
i\geq 4: 0 種類

よって、commencement は良い文字列の条件を満たします。

入力例 2

banana

出力例 2

No

文字列 banana にちょうど 1 回現れる文字は b の 1 種類だけであり、良い文字列の条件を満たしません。

入力例 3

ab

出力例 3

Yes

Score: 200 points

Problem Statement

A string S consisting of lowercase English letters is a good string if and only if it satisfies the following property for all integers i not less than 1:

There are exactly zero or exactly two different letters that appear exactly i times in S.

Given a string S, determine if it is a good string.

Constraints

S is a string of lowercase English letters with a length between 1 and 100, inclusive.

Input

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

Output

Print Yes if S is a good string, and No otherwise.

Sample Input 1

commencement

Sample Output 1

Yes

For the string commencement, the number of different letters that appear exactly i times is as follows:

i=1: two letters (o and t)
i=2: two letters (c and n)
i=3: two letters (e and m)
i\geq 4: zero letters

Therefore, commencement satisfies the condition of a good string.

Sample Input 2

banana

Sample Output 2

No

For the string banana, there is only one letter that appears exactly one time, which is b, so it does not satisfy the condition of a good string.

Sample Input 3

ab

Sample Output 3

Yes

E - Path Graph?

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