AtCoder Daily Training EASY 2025/08/26 19:30start

A - Exponential or Quadratic

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

2^n \gt n^2 ですか？

制約

n は 1 以上 10^9 以下の整数

入力

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

出力

2^n \gt n^2 なら Yes を、そうでないなら No を出力せよ。

入力例 1

出力例 1

Yes

2^5=32,\ 5^2=25 より 2^n \gt n^2 であるため、Yes を出力します。

入力例 2

出力例 2

No

n=2 の場合 2^n=n^2=2^2 となり、故に 2^n \gt n^2 ではありません。よって No を出力します。

入力例 3

623947744

出力例 3

Yes

Score : 100 points

Problem Statement

Does 2^n \gt n^2 hold?

Constraints

n is an integer between 1 and 10^9 (inclusive).

Input

Input is given from Standard Input in the following format:

Output

If 2^n \gt n^2, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.

Sample Input 2

Sample Output 2

No

For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.

Sample Input 3

623947744

Sample Output 3

Yes

B - 2UP3DOWN

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君が 100 階建てのビルにいます。

高橋君は 2 階分までの上り、または、3 階分までの下りであれば移動には階段を使い、そうでないときエレベーターを使います。

高橋君が X 階から Y 階への移動に使うのは階段ですか？

制約

1 \leq X,Y \leq 100
X \neq Y
入力は全ては整数である

入力

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

X Y

出力

移動に使うのが階段ならば Yes、エレベーターならば No を出力せよ。

入力例 1

1 4

出力例 1

No

1 階から 4 階への移動は 3 階分の上りなのでエレベーターを使います。

入力例 2

99 96

出力例 2

Yes

99 階から 96 階への移動は 3 階分の下りなので階段を使います。

入力例 3

100 1

出力例 3

No

Score : 100 points

Problem Statement

Takahashi is in a building with 100 floors.

He uses the stairs for moving up two floors or less or moving down three floors or less, and uses the elevator otherwise.

Does he use the stairs to move from floor X to floor Y?

Constraints

1 \leq X,Y \leq 100
X \neq Y
All input values are integers.

Input

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

X Y

Output

If Takahashi uses the stairs for the move, print Yes; if he uses the elevator, print No.

Sample Input 1

1 4

Sample Output 1

No

The move from floor 1 to floor 4 involves going up three floors, so Takahashi uses the elevator.

Sample Input 2

99 96

Sample Output 2

Yes

The move from floor 99 to floor 96 involves going down three floors, so Takahashi uses the stairs.

Sample Input 3

100 1

Sample Output 3

No

C - Tournament Result

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の人が総当り戦の試合をしました。

N 行 N 列からなる試合の結果の表 A が与えられます。A の i 行目 j 列目の要素を A_{i,j} と表します。
A_{i,j} は i=j のとき - であり、それ以外のとき W, L, D のいずれかです。
A_{i,j} が W, L, D であることは、人 i が人 j との試合に勝った、負けた、引き分けたことをそれぞれ表します。

与えられた表に矛盾があるかどうかを判定してください。

次のいずれかが成り立つとき、与えられた表には矛盾があるといいます。

ある組 (i,j) が存在して、人 i が人 j に勝ったが、人 j が人 i に負けていない
ある組 (i,j) が存在して、人 i が人 j に負けたが、人 j が人 i に勝っていない
ある組 (i,j) が存在して、人 i が人 j に引き分けたが、人 j が人 i に引き分けていない

制約

2 \leq N \leq 1000
A_{i,i} は - である
i\neq j のとき、A_{i,j} は W, L, D のいずれかである

入力

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

N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}

出力

与えられた表に矛盾がないとき correct、矛盾があるとき incorrect と出力せよ。

入力例 1

4
-WWW
L-DD
LD-W
LDW-

出力例 1

incorrect

人 3 が人 4 に勝ったにもかかわらず、人 4 も人 3 に勝ったことになっており、矛盾しています。

入力例 2

2
-D
D-

出力例 2

correct

矛盾はありません。

Score : 200 points

Problem Statement

N players played a round-robin tournament.

You are given an N-by-N table A containing the results of the matches. Let A_{i,j} denote the element at the i-th row and j-th column of A.
A_{i,j} is - if i=j, and W, L, or D otherwise.
A_{i,j} is W if Player i beat Player j, L if Player i lost to Player j, and D if Player i drew with Player j.

Determine whether the given table is contradictory.

The table is said to be contradictory when some of the following holds:

There is a pair (i,j) such that Player i beat Player j, but Player j did not lose to Player i;
There is a pair (i,j) such that Player i lost to Player j, but Player j did not beat Player i;
There is a pair (i,j) such that Player i drew with Player j, but Player j did not draw with Player i.

Constraints

2 \leq N \leq 1000
A_{i,i} is -.
A_{i,j} is W, L, or D, for i\neq j.

Input

Input is given from Standard Input in the following format:

N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}

Output

If the given table is not contradictory, print correct; if it is contradictory, print incorrect.

Sample Input 1

4
-WWW
L-DD
LD-W
LDW-

Sample Output 1

incorrect

Player 3 beat Player 4, while Player 4 also beat Player 3, which is contradictory.

Sample Input 2

2
-D
D-

Sample Output 2

correct

There is no contradiction.

D - Extended ABC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

拡張 A 文字列、拡張 B 文字列、拡張 C 文字列および拡張 ABC 文字列を以下のように定義します。

文字列 S が拡張 A 文字列であるとは、S のすべての文字が A であることをいいます。
文字列 S が拡張 B 文字列であるとは、S のすべての文字が B であることをいいます。
文字列 S が拡張 C 文字列であるとは、S のすべての文字が C であることをいいます。
文字列 S が拡張 ABC 文字列であるとは、ある拡張 A 文字列 S _ A 、拡張 B 文字列 S _ B 、拡張 C 文字列 S _ C が存在して、S _ A,S _ B,S _ C をこの順に連結した文字列が S と等しいことをいいます。

例えば、ABC や A 、AAABBBCCCCCCC などは拡張 ABC 文字列ですが、ABBAAAC 、BBBCCCCCCCAAA などは拡張 ABC 文字列ではありません。空文字列は拡張 A 文字列でも拡張 B 文字列でも拡張 C 文字列でもあることに注意してください。

A, B, C からなる文字列 S が与えられます。 S が拡張 ABC 文字列ならば Yes を、そうでなければ No を出力してください。

制約

S は A, B, C からなる文字列
1\leq|S|\leq 100\ (|S| は文字列 S の長さ)

入力

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

出力

S が拡張 ABC 文字列ならば Yes を、そうでなければ No を出力せよ。

入力例 1

AAABBBCCCCCCC

出力例 1

Yes

AAABBBCCCCCCC は長さ 3 の拡張 A 文字列 AAA 、長さ 3 の拡張 B 文字列 BBB 、長さ 7 の拡張 C 文字列 CCCCCCC をこの順に連結した文字列なので、拡張 ABC 文字列です。

よって、Yes を出力してください。

入力例 2

ACABABCBC

出力例 2

No

どのような拡張 A 文字列 S _ A, 拡張 B 文字列 S _ B, 拡張 C 文字列 S _ C についても、S _ A,S _ B,S _ C をこの順に連結した文字列が ACABABCBC と等しくなることはありません。

よって、No を出力してください。

入力例 3

出力例 3

Yes

入力例 4

ABBBBBBBBBBBBBCCCCCC

出力例 4

Yes

Score: 200 points

Problem Statement

We define Extended A strings, Extended B strings, Extended C strings, and Extended ABC strings as follows:

A string S is an Extended A string if all characters in S are A.
A string S is an Extended B string if all characters in S are B.
A string S is an Extended C string if all characters in S are C.
A string S is an Extended ABC string if there is an Extended A string S_A, an Extended B string S_B, and an Extended C string S_C such that the string obtained by concatenating S_A, S_B, S_C in this order equals S.

For example, ABC, A, and AAABBBCCCCCCC are Extended ABC strings, but ABBAAAC and BBBCCCCCCCAAA are not. Note that the empty string is an Extended A string, an Extended B string, and an Extended C string.

You are given a string S consisting of A, B, and C. If S is an Extended ABC string, print Yes; otherwise, print No.

Constraints

S is a string consisting of A, B, and C.
1\leq|S|\leq 100 (|S| is the length of the string S.)

Input

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

Output

If S is an Extended ABC string, print Yes; otherwise, print No.

Sample Input 1

AAABBBCCCCCCC

Sample Output 1

Yes

AAABBBCCCCCCC is an Extended ABC string because it is a concatenation of an Extended A string of length 3, AAA, an Extended B string of length 3, BBB, and an Extended C string of length 7, CCCCCCC, in this order.

Thus, print Yes.

Sample Input 2

ACABABCBC

Sample Output 2

No

There is no triple of Extended A string S_A, Extended B string S_B, and Extended C string S_C such that the string obtained by concatenating S_A, S_B, and S_C in this order equals ACABABCBC.

Therefore, print No.

Sample Input 3

Sample Output 3

Yes

Sample Input 4

ABBBBBBBBBBBBBCCCCCC

Sample Output 4

Yes

E - PC on the Table

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は部屋に PC を沢山置こうとしています。そこで最大何台の PC を部屋に置けるか調べるプログラムを書くことにしました。

H 個の長さ W の ., T からなる文字列 S_1,S_2,\ldots,S_H が与えられます。

高橋君は以下の操作を 0 回以上何回でも行うことができます。

1\leq i \leq H, 1 \leq j \leq W-1 を満たす整数であって、 S_i の j 番目の文字も j+1 番目の文字も T であるようなものを選ぶ。 S_i の j 番目の文字を P で置き換え、S_i の j+1 番目の文字を C で置き換える。

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を出力してください。

制約

1\leq H \leq 100
2\leq W \leq 100
H と W は整数である
S_i は ., T からなる長さ W の文字列

入力

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

H W 
S_1
S_2
\vdots
S_H

出力

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を改行区切りで出力せよ。

解が複数存在する場合、どれを出力しても正答とみなされる。

入力例 1

2 3
TTT
T.T

出力例 1

PCT
T.T

可能な操作回数の最大値は 1 です。

例えば、 (i,j)=(1,1) として操作を行うと、S_1 が PCT に変化します。

入力例 2

3 5
TTT..
.TTT.
TTTTT

出力例 2

PCT..
.PCT.
PCTPC

Score : 300 points

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

1\leq H \leq 100
2\leq W \leq 100
H and W are integers.
S_i is a string of length W consisting of . and T.

Input

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

H W 
S_1
S_2
\vdots
S_H

Output

Print a sequence of strings, S_1,S_2,\ldots,S_H, separated by newlines, possibly resulting from maximizing the number of times he performs the operation.

If multiple solutions exist, print any of them.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC