AtCoder Daily Training EASY 2025/12/16 17:30start

A - Majority

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある提案に対し、N 人の人が賛成か反対かを表明しています。なお、N は奇数です。

i \, (i = 1, 2, \dots, N) 番目の人の意見は文字列 S_i で表され、S_i = For のとき賛成しており、S_i = Against のとき反対しています。

過半数の人がこの提案に賛成しているかどうかを判定してください。

制約

N は 1 以上 99 以下の奇数
全ての i = 1, 2, \dots, N に対し、S_i = For または S_i = Against

入力

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

N
S_1
S_2
\vdots
S_N

出力

N 人のうち過半数が提案に賛成しているならば Yes、そうでなければ No と出力せよ。

入力例 1

3
For
Against
For

出力例 1

Yes

提案に賛成している人数は 2 人であり、これは半数を超えているので Yes と出力します。

入力例 2

5
Against
Against
For
Against
For

出力例 2

No

提案に賛成している人数は 2 人であり、これは半数以下なので No と出力します。

入力例 3

1
For

出力例 3

Yes

Score : 100 points

Problem Statement

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

N is an odd number between 1 and 99, inclusive.
S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print Yes if the majority of the N people agree with the proposal; print No otherwise.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

B - What month is it?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 以上 12 以下の整数 X,Y が与えられます。

X 月の Y ヶ月後が何月か求めてください。

制約

X,Y は 1 以上 12 以下の整数

入力

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

X Y

出力

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

入力例 1

5 9

出力例 1

5 月の 9 ヶ月後は 2 月です。したがって、 2 を出力してください。

入力例 2

1 1

出力例 2

入力例 3

12 12

出力例 3

Score : 100 points

Problem Statement

You are given integers X and Y between 1 and 12, inclusive.

Find what month it will be Y months after month X (for example, month 1 is January).

Constraints

X and Y are integers between 1 and 12, inclusive.

Input

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

X Y

Output

Output the answer as an integer.

Sample Input 1

5 9

Sample Output 1

Nine months after May is February. Therefore, output 2.

Sample Input 2

1 1

Sample Output 2

Sample Input 3

12 12

Sample Output 3

C - Longest Segment

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

二次元平面上に N 個の点があります。i 個目の点の座標は (x_i,y_i) です。

この中から 2 個の点を選ぶとき、それらを結ぶ線分の長さの最大値を求めてください。

制約

2 \leq N \leq 100
-1000 \leq x_i,y_i \leq 1000
(x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
入力はすべて整数

入力

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

N
x_1 y_1
x_2 y_2
\hspace{0.4cm} \vdots
x_N y_N

出力

2 点を結ぶ線分の長さの最大値を出力せよ。

想定解との絶対誤差または相対誤差が 10^{-6} 以下であれば正解とみなされる。

入力例 1

出力例 1

1.4142135624

1 個目の点と 3 個目の点を選んだときそれらを結ぶ線分の長さは \sqrt 2 = 1.41421356237\dots となり、これが最大です。

入力例 2

出力例 2

1455.7159750446

Score : 200 points

Problem Statement

There are N points in a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).

Find the maximum length of a segment connecting two of these points.

Constraints

2 \leq N \leq 100
-1000 \leq x_i,y_i \leq 1000
(x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
\hspace{0.4cm} \vdots
x_N y_N

Output

Print the maximum length of a segment connecting two of the points.

Your answer will be considered correct when the absolute or relative error from the judge's answer is at most 10^{-6}.

Sample Input 1

Sample Output 1

1.4142135624

For the 1-st and 3-rd points, the length of the segment connecting them is \sqrt 2 = 1.41421356237\dots, which is the maximum length.

Sample Input 2

Sample Output 2

1455.7159750446

D - Not All

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

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

A の末尾の要素を削除するという操作を 0 回以上 N 回以下行うことで、以下の条件が満たされないようにしたいです。

条件：A には 1 以上 M 以下の整数がすべて含まれている。

必要な操作回数の最小値を求めてください。

なお、本問題の制約下において、操作を 0 回以上 N 回以下行うことで上述の条件が満たされないようにすることが必ず可能であることが証明できます。

制約

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

入力

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

N M
A_1 A_2 \dots A_N

出力

条件が満たされなくなるために必要な操作回数の最小値を出力せよ。

入力例 1

5 3
3 2 3 1 2

出力例 1

最初、A=(3,2,3,1,2) です。このとき、A には 1 以上 3 以下の整数がすべて含まれるため条件を満たします。

A の末尾の要素を削除する操作を 1 回行うと、A=(3,2,3,1) となります。このとき、A には 1 以上 3 以下の整数がすべて含まれるため条件を満たします。

A の末尾の要素を削除する操作をもう 1 回行うと、A=(3,2,3) となります。このとき、A には 1 が含まれないため条件を満たしません。

よって、条件が満たされなくなるために必要な操作回数の最小値は 2 です。

入力例 2

4 3
1 3 1 3

出力例 2

A には最初から 2 が含まれず条件を満たさないため、操作を 1 回も行う必要がありません。

入力例 3

10 4
1 3 3 4 2 1 3 1 2 4

出力例 3

Score : 200 points

Problem Statement

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

Your goal is to make the following condition false by performing this operation between 0 and N times (inclusive): remove the last element of A.

Condition: A contains every integer from 1 through M.

Find the minimum number of operations required.

Under the constraints of this problem, it can be proved that it is always possible to make the condition false by performing the operation between 0 and N times.

Constraints

1 \le M \le N \le 100
1 \le A_i \le M
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_N

Output

Output the minimum number of operations required to make the condition false.

Sample Input 1

5 3
3 2 3 1 2

Sample Output 1

Initially, A = (3,2,3,1,2). Since A contains every integer from 1 through 3, the condition holds.

If you perform the operation once, A = (3,2,3,1). The condition still holds.

If you perform the operation once more, A = (3,2,3). The integer 1 is missing, so the condition no longer holds.

Therefore, the minimum required number of operations is 2.

Sample Input 2

4 3
1 3 1 3

Sample Output 2

Since A initially lacks the integer 2, the condition is already false, so no operation is needed.

Sample Input 3

10 4
1 3 3 4 2 1 3 1 2 4

Sample Output 3

E - Popcorn

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

AtCoder Land には 1 から N までの番号が付けられた N 個のポップコーン売り場があります。売られているポップコーンの味には味 1,2,\dots,M の M 種類がありますが、すべての売り場ですべての味のポップコーンを売っているわけではありません。

高橋君は、それぞれのポップコーン売り場でどの味のポップコーンを売っているかの情報を入手しました。この情報は N 個の長さ M の文字列 S_1,S_2,\dots,S_N によって表され、S_i の j 文字目が o であるとき売り場 i が味 j のポップコーンを売っていることを、 x であるとき売っていないことを示します。どの売り場も最低 1 種類の味のポップコーンを売っており、どの味のポップコーンも最低 1 つの売り場で売られています。

高橋君は全種類のポップコーンを食べたがっていますが、あまり何度も移動はしたくありません。高橋君がすべての味のポップコーンを購入するためには最低何個の売り場を訪れる必要があるか求めてください。

制約

N,M は整数
1\leq N,M \leq 10
S_i は o および x からなる長さ M の文字列
すべての i\ (1\leq i\leq N) について、S_i の中には o が 1 つ以上存在する
すべての j\ (1\leq j\leq M) について、S_i の j 文字目が o であるような i が 1 つ以上存在する

入力

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

N M
S_1
S_2
\vdots
S_N

出力

高橋君がすべての味のポップコーンを購入するために訪れる必要がある売り場の個数の最小値を出力せよ。

入力例 1

3 5
oooxx
xooox
xxooo

出力例 1

1 つめの売り場と 3 つめの売り場を訪れることで、すべての味のポップコーンを購入することができます。 1 つの売り場ですべての味のポップコーンを購入することはできないので、答えは 2 です。

入力例 2

3 2
oo
ox
xo

出力例 2

入力例 3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

出力例 3

Score : 300 points

Problem Statement

In AtCoder Land, there are N popcorn stands numbered 1 to N. They have M different flavors of popcorn, labeled 1, 2, \dots, M, but not every stand sells all flavors of popcorn.

Takahashi has obtained information about which flavors of popcorn are sold at each stand. This information is represented by N strings S_1, S_2, \dots, S_N of length M. If the j-th character of S_i is o, it means that stand i sells flavor j of popcorn. If it is x, it means that stand i does not sell flavor j. Each stand sells at least one flavor of popcorn, and each flavor of popcorn is sold at least at one stand.

Takahashi wants to try all the flavors of popcorn but does not want to move around too much. Determine the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Constraints

N and M are integers.
1 \leq N, M \leq 10
Each S_i is a string of length M consisting of o and x.
For every i (1 \leq i \leq N), there is at least one o in S_i.
For every j (1 \leq j \leq M), there is at least one i such that the j-th character of S_i is o.

Input

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

N M
S_1
S_2
\vdots
S_N

Output

Print the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Sample Input 1

3 5
oooxx
xooox
xxooo

Sample Output 1

By visiting the 1st and 3rd stands, you can buy all the flavors of popcorn. It is impossible to buy all the flavors from a single stand, so the answer is 2.

Sample Input 2

3 2
oo
ox
xo

Sample Output 2

Sample Input 3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo