AtCoder Daily Training EASY 2026/09/17 16:00start

A - Job Interview

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君はある会社の採用面接を受けました。

面接官の人数 N と、各面接官の高橋君への評価を表す長さ N の文字列 S が与えられます。
i=1,2,\ldots,N に対し S の i 文字目が i 番目の面接官の評価に対応し、o は「良」、- は「可」、x は「不可」を表します。

高橋君は以下の 2 つの条件を両方満たすならば合格、そうでなければ不合格です。

「良」と評価した面接官が少なくとも 1 人いる
「不可」と評価した面接官がいない

高橋君が合格かどうかを判定してください。

制約

1 \leq N \leq 100
S は o, -, x のみからなる長さが N の文字列

入力

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

N
S

出力

高橋君が合格ならば Yes と、そうでなければ No と出力せよ。

入力例 1

4
oo--

出力例 1

Yes

1, 2 番目の面接官が「良」と評価していて、さらに「不可」と評価した面接官がいないため合格です。

入力例 2

3
---

出力例 2

No

「良」と評価した面接官が 1 人もいないため不合格です。

入力例 3

1
o

出力例 3

Yes

入力例 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

出力例 4

No

100 番目の面接官が「不可」と評価しているため不合格です。

Score : 100 points

Problem Statement

Takahashi had a job interview.

You are given the number of interviewers, N, and a string S of length N representing the interviewers' evaluations of him.
For each i=1,2,\ldots,N, the i-th character of S corresponds to the i-th interviewer's evaluation; o means Good, - means Fair, and x means Poor.

Takahashi will pass if both of the following conditions are satisfied, and fail otherwise.

At least one interviewer's evaluation is Good.
No interviewer's evaluation is Poor.

Determine whether Takahashi passes.

Constraints

1 \leq N \leq 100
S is a string of length N consisting of o, -, and x.

Input

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

N
S

Output

If Takahashi passes, print Yes; otherwise, print No.

Sample Input 1

4
oo--

Sample Output 1

Yes

The first and second interviewers' evaluations are Good, and no interviewer's evaluation is Poor, so he passes.

Sample Input 2

3
---

Sample Output 2

No

No interviewer's evaluation is Good, so he fails.

Sample Input 3

1
o

Sample Output 3

Yes

Sample Input 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

Sample Output 4

No

The 100-th interviewer's evaluation is Poor, so he fails.

B - Balloon Trip

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 W,B が与えられるので、以下の問題を解いてください。

高橋君の体重は W {\rm [kg]} です。 (単位が {\rm kg} であることに注意してください)
風船を n 個付けられた物体は、物体の質量が nB {\rm [g]} 未満である時、またその時に限り、空に飛び立ちます。
高橋君を空に飛ばすためには、最低何個の風船を付ける必要がありますか？

制約

1 \le W \le 100
1 \le B \le 100
入力される値は全て整数

入力

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

W B

出力

答えを出力せよ。

入力例 1

80 5

出力例 1

高橋君の体重は 80 {\rm kg} = 80000 {\rm g} です。
高橋君に風船を 16001 個付けると、高橋君の質量は 16001 \times 5=80005 {\rm g} 未満であるため、空に飛び立ちます。
16000 個では不十分であることに注意してください。

入力例 2

70 6

出力例 2

入力例 3

100 100

出力例 3

Score : 100 points

Problem Statement

Given integers W and B, solve the following problem.

Takahashi's weight is W {\rm [kg]}. (Note that the unit is {\rm kg}.)
An object attached with n balloons will fly into the sky if and only if the mass of the object is strictly less than nB {\rm [g]}.
What is the minimum number of balloons needed to make Takahashi fly into the sky?

Constraints

1 \le W \le 100
1 \le B \le 100
All input values are integers.

Input

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

W B

Output

Output the answer.

Sample Input 1

80 5

Sample Output 1

Takahashi's weight is 80 {\rm kg} = 80000 {\rm g}.
If he is attached with 16001 balloons, his mass is less than 16001 \times 5=80005 {\rm g}, so he will fly into the sky.
Note that 16000 balloons are not sufficient.

Sample Input 2

70 6

Sample Output 2

Sample Input 3

100 100

Sample Output 3

C - Call the ID Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

人 1 、人 2 、\ldots 、人 N と番号をつけられた N 人の人がいます。

N 人は、人 1 、人 2 、\ldots 、人 N の順番に下記の行動をちょうど 1 回ずつ行います。

人 i 自身がまだ一度も番号を呼ばれていないなら、人 A_i の番号を呼ぶ。

最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙してください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq N
A_i \neq i
入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

下記の形式にしたがって、最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙せよ。

K
X_1 X_2 \ldots X_K

すなわち、まず 1 行目に、最後まで番号を一度も呼ばれない人の人数 K を出力し、 2 行目に、最後まで番号を一度も呼ばれない人全員の番号を昇順に並べた列 (X_1, X_2, \ldots, X_K) を空白区切りで出力せよ。

入力例 1

5
3 1 4 5 4

出力例 1

2
2 4

5 人の行動は下記の通りです。

人 1 はまだ番号を一度も呼ばれていないので、人 1 は人 3 の番号を呼びます。
人 2 はまだ番号を一度も呼ばれていないので、人 2 は人 1 の番号を呼びます。
人 3 はすでに人 1 によって番号を呼ばれているので、何もしません。
人 4 はまだ番号を一度も呼ばれていないので、人 4 は人 5 の番号を呼びます。
人 5 はすでに人 4 によって番号を呼ばれているので、何もしません。

よって、最後まで番号を一度も呼ばれないのは人 2 と人 4 です。

入力例 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

出力例 2

10
1 2 5 6 8 11 14 17 18 20

Score : 200 points

Problem Statement

There are N people whose IDs are 1, 2, \ldots, and N.

Each of person 1, person 2, \ldots, and person N performs the following action once in this order:

If person i's ID has not been called out yet, call out person A_i's ID.

Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq N
A_i \neq i
All values in the input are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Enumerate the IDs of all the people whose IDs are not called out until the end in ascending order in the following format:

K
X_1 X_2 \ldots X_K

In other words, the first line should contain the number of people, K, whose IDs are never called out until the end; the second line should contain the sequence (X_1, X_2, \ldots, X_K) of IDs of such people in ascending order, with spaces in between.

Sample Input 1

5
3 1 4 5 4

Sample Output 1

2
2 4

The five people's actions are as follows.

Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
Person 3's ID has already been called out by person 1, so nothing happens.
Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
Person 5's ID has already been called out by person 4, so nothing happens.

Therefore, person 2 and 4's IDs are not called out until the end.

Sample Input 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

Sample Output 2

10
1 2 5 6 8 11 14 17 18 20

D - Nice Grid

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

次の図に示す、各マスが黒または白に塗られた縦 15 行 \times 横 15 列のグリッドにおいて、上から R 行目、左から C 列目のマスが何色かを出力して下さい。

制約

1 \leq R, C \leq 15
R, C は整数

入力

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

R C

出力

図のグリッドにおいて上から R 行目、左から C 列目のマスが黒色の場合は black と、白色の場合は white と出力せよ。ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入力例 1

3 5

出力例 1

black

図のグリッドにおいて上から 3 行目、左から 5 列目のマスは黒色です。よって、black と出力します。

入力例 2

4 5

出力例 2

white

図のグリッドにおいて上から 4 行目、左から 5 列目のマスは白色です。よって、white と出力します。

Score : 200 points

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

1 \leq R, C \leq 15
R and C are integers.

Input

Input is given from Standard Input in the following format:

R C

Output

In the grid above, if the color of the cell at the R-th row from the top and C-th column from the left is black, then print black; if the cell is white, then print white. Note that the judge is case-sensitive.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

E - Illuminate Buildings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

N 棟のビルが等間隔に一列に並んでいます。手前から i 番目のビルの高さは H_i です。

あなたは次の条件をともに満たすようにいくつかのビルを選んで電飾で飾ろうとしています。

選んだビルたちは高さが等しい
選んだビルたちは等間隔に並んでいる

最大でいくつのビルを選ぶことができますか？　なお、ちょうど 1 つのビルを選んだときは条件を満たすとみなします。

制約

1 \leq N \leq 3000
1 \leq H_i \leq 3000
入力は全て整数である

入力

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

N
H_1 \ldots H_N

出力

答えを出力せよ。

入力例 1

8
5 7 5 7 7 5 7 7

出力例 1

手前から 2,5,8 番目のビルを選ぶと条件を満たします。

入力例 2

10
100 200 300 400 500 600 700 800 900 1000

出力例 2

1つのビルを選んだときは条件を満たすとみなします。

入力例 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

出力例 3

Score : 350 points

Problem Statement

There are N buildings arranged in a line at equal intervals. The height of the i-th building from the front is H_i.

You want to decorate some of these buildings with illuminations so that both of the following conditions are satisfied:

The chosen buildings all have the same height.
The chosen buildings are arranged at equal intervals.

What is the maximum number of buildings you can choose? If you choose exactly one building, it is considered to satisfy the conditions.

Constraints

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

Input

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

N
H_1 \ldots H_N

Output

Print the answer.

Sample Input 1

8
5 7 5 7 7 5 7 7

Sample Output 1

Choosing the 2nd, 5th, and 8th buildings from the front satisfies the conditions.

Sample Input 2

10
100 200 300 400 500 600 700 800 900 1000

Sample Output 2

Choosing just one building is considered to satisfy the conditions.

Sample Input 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5