AtCoder Daily Training EASY 2025/08/14 20:30start

A - 11/22 String

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

この問題における 11/22 文字列の定義は C 問題および E 問題と同じです。

文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。

|T| は奇数である。ここで、|T| は T の長さを表す。
1 文字目から \frac{|T|+1}{2} - 1 文字目までが 1 である。
\frac{|T|+1}{2} 文字目が / である。
\frac{|T|+1}{2} + 1 文字目から |T| 文字目までが 2 である。

例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。

1, 2, / からなる長さ N の文字列 S が与えられます。S が 11/22 文字列であるか判定してください。

制約

1 \leq N \leq 100
S は 1, 2, / からなる長さ N の文字列

入力

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

N
S

出力

S が 11/22 文字列であれば Yes を、そうでなければ No を出力せよ。

入力例 1

5
11/22

出力例 1

Yes

11/22 は問題文の 11/22 文字列の条件を満たします。

入力例 2

1
/

出力例 2

Yes

/ は問題文の 11/22 文字列の条件を満たします。

入力例 3

4
1/22

出力例 3

No

1/22 は問題文の 11/22 文字列の条件を満たしません。

入力例 4

5
22/11

出力例 4

No

Score : 150 points

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems C and E.

A string T is called an 11/22 string when it satisfies all of the following conditions:

|T| is odd. Here, |T| denotes the length of T.
The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
The (\frac{|T|+1}{2})-th character is /.
The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

Given a string S of length N consisting of 1, 2, and /, determine whether S is an 11/22 string.

Constraints

1 \leq N \leq 100
S is a string of length N consisting of 1, 2, and /.

Input

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

N
S

Output

If S is an 11/22 string, print Yes; otherwise, print No.

Sample Input 1

5
11/22

Sample Output 1

Yes

11/22 satisfies the conditions for an 11/22 string in the problem statement.

Sample Input 2

1
/

Sample Output 2

Yes

/ satisfies the conditions for an 11/22 string.

Sample Input 3

4
1/22

Sample Output 3

No

1/22 does not satisfy the conditions for an 11/22 string.

Sample Input 4

5
22/11

Sample Output 4

No

B - Insert

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の整数列 A と整数 K,X が与えられます。
整数列 A の K 要素目の直後に整数 X を 1 つ挿入した整数列 B を出力してください。

制約

入力は全て整数
1 \le K \le N \le 100
1 \le A_i,X \le 100

入力

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

N K X
A_1 A_2 \dots A_N

出力

整数列 A の K 要素目の直後に整数 X を 1 つ挿入した整数列 B を、以下の形式で出力せよ。

B_1 B_2 \dots B_{N+1}

入力例 1

4 3 7
2 3 5 11

出力例 1

2 3 5 7 11

K=3, X=7, A=(2,3,5,11) のとき、 B=(2,3,5,7,11) です。

入力例 2

1 1 100
100

出力例 2

100 100

入力例 3

8 8 3
9 9 8 2 4 4 3 5

出力例 3

9 9 8 2 4 4 3 5 3

Score : 100 points

Problem Statement

You are given an integer sequence A of length N and integers K and X.
Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A.

Constraints

All input values are integers.
1 \le K \le N \le 100
1 \le A_i, X \le 100

Input

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

N K X
A_1 A_2 \dots A_N

Output

Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A, in the following format:

B_1 B_2 \dots B_{N+1}

Sample Input 1

4 3 7
2 3 5 11

Sample Output 1

2 3 5 7 11

For K=3, X=7, and A=(2,3,5,11), we get B=(2,3,5,7,11).

Sample Input 2

1 1 100
100

Sample Output 2

100 100

Sample Input 3

8 8 3
9 9 8 2 4 4 3 5

Sample Output 3

9 9 8 2 4 4 3 5 3

C - Cat

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の文字列 S が与えられます。

S に連続して含まれる na を全て nya に置き換えて得られる文字列を答えてください。

制約

N は 1 以上 1000 以下の整数
S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

4
naan

出力例 1

nyaan

naan に連続して含まれる na を全て nya に置き換えて得られる文字列は nyaan です。

入力例 2

4
near

出力例 2

near

S に na が連続して含まれないこともあります。

入力例 3

8
national

出力例 3

nyationyal

Score : 200 points

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

N is an integer between 1 and 1000, inclusive.
S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print the answer.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

D - How many?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

a+b+c \leq S かつ a \times b \times c \leq T を満たす非負整数の組 (a,b,c) はいくつありますか？

制約

0 \leq S \leq 100
0 \leq T \leq 10000
S, T は整数である。

入力

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

S T

出力

条件を満たす非負整数の組 (a,b,c) の個数を出力せよ。

入力例 1

1 0

出力例 1

条件を満たす非負整数の組 (a,b,c) は (0,0,0), (0,0,1), (0,1,0), (1,0,0) の 4 つです。

入力例 2

2 5

出力例 2

入力例 3

10 10

出力例 3

入力例 4

30 100

出力例 4

Score : 200 points

Problem Statement

How many triples of non-negative integers (a, b, c) satisfy a+b+c \leq S and a \times b \times c \leq T?

Constraints

0 \leq S \leq 100
0 \leq T \leq 10000
S and T are integers.

Input

Input is given from Standard Input in the following format:

S T

Output

Print the number of triples of non-negative integers (a,b,c) satisfying the conditions.

Sample Input 1

1 0

Sample Output 1

The triples (a,b,c) satisfying the conditions are (0,0,0), (0,0,1), (0,1,0), and (1,0,0) ― there are four of them.

Sample Input 2

2 5

Sample Output 2

Sample Input 3

10 10

Sample Output 3

Sample Input 4

30 100

Sample Output 4

E - Virus

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1, 2, \ldots, N の番号がついた N 人の人が二次元平面上におり、人 i は座標 (X_i,Y_i) で表される地点にいます。

人 1 がウイルスに感染しました。ウイルスに感染した人から距離が D 以内にいる人にウイルスはうつります。

ただし、距離はユークリッド距離、すなわち 2 点 (a_1, a_2) と (b_1, b_2) に対し、この 2 点間の距離が \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2} であるものとして定められています。

十分に時間が経過した、すなわち人 i がウイルスに感染しているならば人 i との距離が D 以内にいるすべての人がウイルスに感染している状態になったときに、各 i について人 i がウイルスに感染しているか判定してください。

制約

1 \leq N, D \leq 2000
-1000 \leq X_i, Y_i \leq 1000
i \neq j のとき (X_i, Y_i) \neq (X_j, Y_j)
入力はすべて整数

入力

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

N D
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

N 行出力せよ。i 行目には、人 i がウイルスに感染しているならば Yes を、そうでないならば No を出力せよ。

入力例 1

出力例 1

Yes
Yes
No
Yes

人 1 と人 2 の距離は \sqrt 5 であるため、人 2 はウイルスに感染します。
また、人 2 と人 4 の距離は 5 であるため、人 4 はウイルスに感染します。
人 3 は距離 5 以内に人がいないので、ウイルスに感染することはありません。

入力例 2

3 1
0 0
-1000 -1000
1000 1000

出力例 2

Yes
No
No

入力例 3

出力例 3

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No

Score : 300 points

Problem Statement

There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).

Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.

Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.

After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.

Constraints

1 \leq N, D \leq 2000
-1000 \leq X_i, Y_i \leq 1000
(X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
All input values are integers.

Input

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

N D
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print N lines. The i-th line should contain Yes if person i is infected with the virus, and No otherwise.

Sample Input 1

Sample Output 1

Yes
Yes
No
Yes

The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.

Sample Input 2

3 1
0 0
-1000 -1000
1000 1000

Sample Output 2

Yes
No
No

Sample Input 3

Sample Output 3

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No