AtCoder Daily Training ALL 2025/08/26 17:30start

A - Spread

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英大文字からなる文字列 S が与えられます。S の各文字を空白で区切り、その順で 1 文字ずつ出力してください。

制約

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

入力

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

出力

S の各文字を空白で区切り、1 文字ずつ出力せよ。

入力例 1

ABC

出力例 1

A B C

A, B, C を空白で区切り、1 文字ずつ出力してください。

C の後ろに空白を出力する必要がないことに注意してください。

入力例 2

ZZZZZZZ

出力例 2

Z Z Z Z Z Z Z

入力例 3

OOXXOO

出力例 3

O O X X O O

Score : 100 points

Problem Statement

You are given a string S consisting of uppercase English letters. Separate each character of S with a space and print them one by one in order.

Constraints

S is a string consisting of uppercase English letters with a length between 2 and 100, inclusive.

Input

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

Output

Separate each character of S with a space and print them one by one.

Sample Input 1

ABC

Sample Output 1

A B C

Separate A, B, and C with spaces and print them one by one.

There is no need to print a space after C.

Sample Input 2

ZZZZZZZ

Sample Output 2

Z Z Z Z Z Z Z

Sample Input 3

OOXXOO

Sample Output 3

O O X X O O

B - 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

C - Tetrahedral Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

整数 N が与えられます。

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを辞書順で小さい方から順に全て出力してください。

非負整数の組の辞書順とは？

非負整数の組 (x,y,z) が (x',y',z') より辞書順で小さいとは、下記のいずれかが成り立つことを言います。

x < x' である
x=x' かつ y< y' である
x=x' かつ y=y' かつ z< z' である

制約

0 \leq N \leq 21
N は整数である

入力

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

出力

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを、1 行に 1 組ずつ x,y,z を空白区切りで、辞書順で小さい方から順に全て出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

Score : 150 points

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

What is lexicographical order for non-negative integer triples?

A triple of non-negative integers (x,y,z) is said to be lexicographically smaller than (x',y',z') if and only if one of the following holds:

x < x';
x=x' and y< y';
x=x' and y=y' and z< z'.

Constraints

0 \leq N \leq 21
N is an integer.

Input

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

Output

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order, with x,y,z separated by spaces, one triple per line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

D - ASCII Art

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

0 以上 26 以下の整数からなる H 行 W 列の行列 A が与えられます。A の上から i 行目、左から j 列目の要素は A_{i,j} です。

H 個の長さ W の文字列 S_1, S_2, \dots, S_H を次の条件を満たすように定めます。

S_i の j 文字目は、 A_{i,j} が 0 ならばピリオド (.)、そうでなければ A_{i,j} 番目の大文字アルファベットである。

S_1, S_2, \dots, S_H を順に出力してください。

制約

1 \leq H \leq 100
1 \leq W \leq 100
0 \leq A_{i,j} \leq 26
入力される値はすべて整数

入力

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

H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}

出力

H 行出力せよ。i 行目には S_i を出力せよ。

入力例 1

2 3
0 1 2
0 0 3

出力例 1

.AB
..C

S_1 = .AB、S_2 = ..C です。この 2 つを順に出力します。

入力例 2

出力例 2

X..
.Y.
..Z

入力例 3

出力例 3

B
I
D

入力例 4

24 60
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0
0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0
0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0
0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0
0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0
0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例 4

................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................

Score : 200 points

Problem Statement

You are given an H-by-W matrix A consisting of integers between 0 and 26. The element at the i-th row from the top and j-th column from the left is A_{i,j}.

Let S_1, S_2, \dots, S_H be H strings of length W that satisfy the following.

The j-th character of S_i is a period (.) if A_{i,j} is 0, and the A_{i,j}-th uppercase English letter otherwise. (For instance, the 4-th letter is D.)

Print S_1, S_2, \dots, S_H in order.

Constraints

1 \leq H \leq 100
1 \leq W \leq 100
0 \leq A_{i,j} \leq 26
All values in the input are integers.

Input

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

H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}

Output

Print H lines. The i-th line should contain S_i.

Sample Input 1

2 3
0 1 2
0 0 3

Sample Output 1

.AB
..C

We have S_1 = .AB and S_2 = ..C. Print these in order.

Sample Input 2

Sample Output 2

X..
.Y.
..Z

Sample Input 3

Sample Output 3

B
I
D

Sample Input 4

24 60
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0
0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0
0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0
0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0
0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0
0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 4

................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................

E - Cheese

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

ピザ屋で働く高橋くんは、まかないとして美味しいチーズピザを作ることにしました。
今、高橋くんの目の前に N 種類のチーズがあります。
i 種類目のチーズは 1 [g] あたりのおいしさが A_i で、 B_i [g] あります。
ピザのおいしさは、ピザに乗せたチーズのおいしさの総和で決まります。
但し、チーズを使いすぎると怒られてしまうため、乗せたチーズの重さは合計で W [g] 以下である必要があります。
この条件のもとで、可能なピザのおいしさの最大値を求めてください。

制約

入力は全て整数
1 \le N \le 3 \times 10^5
1 \le W \le 3 \times 10^8
1 \le A_i \le 10^9
1 \le B_i \le 1000

入力

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

N W
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

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

入力例 1

出力例 1

1 種類目のチーズを 1 [g] 、 2 種類目のチーズを 2 [g] 、 3 種類目のチーズを 2 [g] 乗せるのが最適です。
このとき、ピザのおいしさは 15 となります。

入力例 2

出力例 2

チーズの重量の総和が W [g] に満たないケースもあります。

入力例 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

出力例 3

2357689932073

Score : 300 points

Problem Statement

Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.

Constraints

All values in input are integers.
1 \le N \le 3 \times 10^5
1 \le W \le 3 \times 10^8
1 \le A_i \le 10^9
1 \le B_i \le 1000

Input

Input is given from Standard Input in the following format:

N W
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.

Sample Input 2

Sample Output 2

There may be less than W grams of cheese in total.

Sample Input 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Sample Output 3

2357689932073

F - Rotate Colored Subsequence

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。 S の各文字は色 1 、色 2 、\ldots 、色 M の M 色のうちのいずれかで塗られており、 i = 1, 2, \ldots, N について、S の i 文字目は色 C_i で塗られています。

各 i = 1, 2, \ldots, M について、この順番に下記の操作を行います。

S の色 i で塗られた文字からなる部分を、右に 1 つ巡回シフトする。すなわち、S の色 i で塗られた文字の位置が先頭のものから順に p_1, p_2, p_3, \ldots, p_k 文字目であるとき、 S の p_1, p_2, p_3, \ldots, p_k 文字目を、それぞれ、S の p_k, p_1,p_2, \ldots, p_{k-1} 文字目で同時に置き換える。

上記の操作をすべて行った後の、最終的な S を出力してください。

なお、M 色あるどの色についても、その色で塗られた S の文字が必ず 1 つ以上存在することが、制約として保証されます。

制約

1 \leq M \leq N \leq 2 \times 10^5
1 \leq C_i \leq M
N, M, C_i はすべて整数
S は英小文字からなる長さ N の文字列
任意の整数 1 \leq i \leq M に対して、ある整数 1 \leq j \leq N が存在して C_j = i が成り立つ

入力

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

N M
S
C_1 C_2 \ldots C_N

出力

答えを出力せよ。

入力例 1

8 3
apzbqrcs
1 2 3 1 2 2 1 2

出力例 1

cszapqbr

はじめ、S = apzbqrcs です。

i = 1 に対する操作では、S の 1, 4, 7 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S = cpzaqrbs となります。
i = 2 に対する操作では、S の 2, 5, 6, 8 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S = cszapqbr となります。
i = 3 に対する操作では、S の 3 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S = cszapqbr となります（操作の前後で S は変わりません）。

よって、最終的な S である cszapqbr を出力します。

入力例 2

2 1
aa
1 1

出力例 2

aa

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters. Each character of S is painted in one of the M colors: color 1, color 2, ..., color M; for each i = 1, 2, \ldots, N, the i-th character of S is painted in color C_i.

For each i = 1, 2, \ldots, M in this order, let us perform the following operation.

Perform a right circular shift by 1 on the part of S painted in color i. That is, if the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters are painted in color i from left to right, then simultaneously replace the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters of S with the p_k-th, p_1-th, p_2-th, \ldots, p_{k-1}-th characters of S, respectively.

Print the final S after the above operations.

The constraints guarantee that at least one character of S is painted in each of the M colors.

Constraints

1 \leq M \leq N \leq 2 \times 10^5
1 \leq C_i \leq M
N, M, and C_i are all integers.
S is a string of length N consisting of lowercase English letters.
For each integer 1 \leq i \leq M, there is an integer 1 \leq j \leq N such that C_j = i.

Input

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

N M
S
C_1 C_2 \ldots C_N

Output

Print the answer.

Sample Input 1

8 3
apzbqrcs
1 2 3 1 2 2 1 2

Sample Output 1

cszapqbr

Initially, S = apzbqrcs.

For i = 1, perform a right circular shift by 1 on the part of S formed by the 1-st, 4-th, 7-th characters, resulting in S = cpzaqrbs.
For i = 2, perform a right circular shift by 1 on the part of S formed by the 2-nd, 5-th, 6-th, 8-th characters, resulting in S = cszapqbr.
For i = 3, perform a right circular shift by 1 on the part of S formed by the 3-rd character, resulting in S = cszapqbr (here, S is not changed).

Thus, you should print cszapqbr, the final S.

Sample Input 2

2 1
aa
1 1

Sample Output 2

aa

G - Synchronized Players

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 行 N 列のグリッドがあり、各マスは空きマスか障害物のあるマスのいずれかです。グリッドの上から i 行目、左から j 列目のマスを (i, j) と表記します。

また、2 人のプレイヤーがグリッド上の相異なる空きマス上におり、各マスの情報は N 個の長さ N の文字列 S_1, S_2, \ldots, S_N として以下の形式で与えられます。

S_i の j 文字目が P であるとき、(i, j) は空きマスであり、プレイヤーがいる
S_i の j 文字目が . であるとき、(i, j) は空きマスであり、プレイヤーがいない
S_i の j 文字目が # であるとき、(i, j) は障害物のあるマスである

以下の操作を繰り返し 2 人のプレイヤーを同じマスに集めるために必要な操作回数の最小値を求めてください。ただし、操作の繰り返しにより 2 人のプレイヤーを同じマスに集めることができない場合には -1 を出力してください。

上下左右のいずれかの方向を決める。そして各プレイヤーはともにその方向に隣接するマスへの移動を試みる。各プレイヤーは移動先のマスが存在し、かつ空きマスであるならば移動し、そうでないならば移動しない。

制約

N は 2 以上 60 以下の整数
S_i は長さ N の P, ., # からなる文字列
S_i の j 文字目が P であるような組 (i, j) の個数はちょうど 2 つ

入力

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

N
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

5
....#
#..#.
.P...
..P..
....#

出力例 1

はじめに (3, 2) にいるプレイヤーをプレイヤー 1、(4, 3) にいるプレイヤーをプレイヤー 2 とします。

例えば以下のようにすることで、3 回の操作で 2 人のプレイヤーが同じマスに集まります。

左を選択する。プレイヤー 1 は (3, 1) に移動し、プレイヤー 2 は (4, 2) に移動する。
上を選択する。プレイヤー 1 は移動せず、プレイヤー 2 は (3, 2) に移動する。
左を選択する。プレイヤー 1 は移動せず、プレイヤー 2 は (3, 1) に移動する。

入力例 2

2
P#
#P

出力例 2

-1

入力例 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

出力例 3

Score: 400 points

Problem Statement

There is an N \times N grid, where each cell is either empty or contains an obstacle. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

There are also two players on distinct empty cells of the grid. The information about each cell is given as N strings S_1, S_2, \ldots, S_N of length N, in the following format:

If the j-th character of S_i is P, then (i, j) is an empty cell with a player on it.
If the j-th character of S_i is ., then (i, j) is an empty cell without a player.
If the j-th character of S_i is #, then (i, j) contains an obstacle.

Find the minimum number of moves required to bring the two players to the same cell by repeating the following operation. If it is impossible to bring the two players to the same cell by repeating the operation, print -1.

Choose one of the four directions: up, down, left, or right. Then, each player attempts to move to the adjacent cell in that direction. Each player moves if the destination cell exists and is empty, and does not move otherwise.

Constraints

N is an integer between 2 and 60, inclusive.
S_i is a string of length N consisting of P, ., and #.
There are exactly two pairs (i, j) where the j-th character of S_i is P.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

5
....#
#..#.
.P...
..P..
....#

Sample Output 1

Let us call the player starting at (3, 2) Player 1 and the player starting at (4, 3) Player 2.

For example, doing the following brings the two players to the same cell in three moves:

Choose left. Player 1 moves to (3, 1), and Player 2 moves to (4, 2).
Choose up. Player 1 does not move, and Player 2 moves to (3, 2).
Choose left. Player 1 does not move, and Player 2 moves to (3, 1).

Sample Input 2

2
P#
#P

Sample Output 2

-1

Sample Input 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

Sample Output 3

H - Unfair Sugoroku

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

高橋君と青木君がすごろくをします。
高橋君ははじめ地点 A、青木君ははじめ地点 B にいて、交互にサイコロを振ります。
高橋君が振るサイコロは 1, 2, \ldots, P の出目が一様ランダムに出るサイコロで、青木君が振るサイコロは 1, 2, \ldots, Q の出目が一様ランダムに出るサイコロです。
地点 x にいるときに自分の振ったサイコロの出目が i であるとき、地点 \min(x + i, N) に進みます。
地点 N に先に着いた人をすごろくの勝者とします。
高橋君が先にサイコロを振るとき、高橋君が勝つ確率を \text{mod }998244353 で求めてください。

確率 \text{mod }998244353 とは

この問題で求める確率は必ず有理数になることが証明できます。また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod {998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。

制約

2 \leq N \leq 100
1 \leq A, B < N
1 \leq P, Q \leq 10
入力はすべて整数

入力

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

N A B P Q

出力

答えを出力せよ。

入力例 1

4 2 3 3 2

出力例 1

665496236

高橋君が最初の手番で 2 あるいは 3 の出目を出すと、高橋君は地点 4 に進んで高橋君が勝利します。
高橋君が最初の手番で 1 の出目を出すと、高橋君は地点 3 に進み、青木君は次の手番で必ず地点 4 に進んで青木君が勝利します。
よって、高橋君が勝つ確率は \frac{2}{3} です。

入力例 2

6 4 2 1 1

出力例 2

サイコロの出目は常に 1 です。
このとき高橋君が地点 5 に進み、次いで青木君が地点 3 に進み、次いで高橋君が地点 6 に進むので、高橋君は必ず勝ちます。

入力例 3

100 1 1 10 10

出力例 3

264077814

Score : 500 points

Problem Statement

Takahashi and Aoki will play a game of sugoroku.
Takahashi starts at point A, and Aoki starts at point B. They will take turns throwing dice.
Takahashi's die shows 1, 2, \ldots, P with equal probability, and Aoki's shows 1, 2, \ldots, Q with equal probability.
When a player at point x throws his die and it shows i, he goes to point \min(x + i, N).
The first player to reach point N wins the game.
Find the probability that Takahashi wins if he goes first, modulo 998244353.

How to find a probability modulo 998244353

It can be proved that the sought probability is always rational. Additionally, the constraints of this problem guarantee that, if that probability is represented as an irreducible fraction \frac{y}{x}, then x is indivisible by 998244353.
Here, there is a unique integer z between 0 and 998244352 such that xz \equiv y \pmod {998244353}. Report this z.

Constraints

2 \leq N \leq 100
1 \leq A, B < N
1 \leq P, Q \leq 10
All values in the input are integers.

Input

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

N A B P Q

Output

Print the answer.

Sample Input 1

4 2 3 3 2

Sample Output 1

665496236

If Takahashi's die shows 2 or 3 in his first turn, he goes to point 4 and wins.
If Takahashi's die shows 1 in his first turn, he goes to point 3, and Aoki will always go to point 4 in the next turn and win.
Thus, Takahashi wins with the probability \frac{2}{3}.

Sample Input 2

6 4 2 1 1

Sample Output 2

The dice always show 1.
Here, Takahashi goes to point 5, Aoki goes to point 3, and Takahashi goes to point 6, so Takahashi always wins.

Sample Input 3

100 1 1 10 10

Sample Output 3

264077814

I - Fighter Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

N 頂点の木があります。 1 番目の頂点が根であり、i 番目 (2\leq i\leq N) の頂点の親は p _ i\ (1\leq p _ i\lt i) です。

根でない頂点には、敵か薬のどちらか一方が配置されています。高橋くんは、すべての敵を倒したいです。はじめ、高橋くんの強さは 1 で、頂点 1 にいます。 i=2,\ldots,N について、i 番目の頂点の情報は整数の組 (t _ i,s _ i,g _ i) を用いて次のように表されます。

t _ i=1 ならば i 番目の頂点には敵がいます。この頂点に高橋くんが初めて訪れたとき、高橋くんの強さが s _ i 未満だった場合高橋くんは敵に倒されて敗北し、高橋くんは他の頂点に移動できなくなります。そうでなかった場合、高橋くんは敵を倒し、強さが g _ i 上昇します。
t _ i=2 ならば i 番目の頂点には薬があります。この頂点に高橋くんが初めて訪れたとき、高橋くんは薬を飲み、強さが g _ i 倍になります。（薬がある頂点では、s _ i=0 です。）

薬がある頂点はたかだか 10 個です。

高橋くんは、隣接する頂点に移動することができます。高橋くんがすべての敵を倒すことができるか判定してください。

制約

2\leq N\leq 500
1\leq p _ i\lt i\ (2\leq i\leq N)
t _ i\in\lbrace1,2\rbrace\ (2\leq i\leq N)
t _ i=1\implies1\leq s _ i\leq 10 ^ 9\ (2\leq i\leq N)
t _ i=2\implies s _ i=0\ (2\leq i\leq N)
1\leq g _ i\leq 10 ^ 9\ (2\leq i\leq N)
t _ i=2 である頂点は 10 個以下
入力はすべて整数

入力

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

N
p _ 2 t _ 2 s _ 2 g _ 2
p _ 3 t _ 3 s _ 3 g _ 3
\vdots
p _ N t _ N s _ N g _ N

出力

答え（Yes または No）を 1 行で出力せよ。

入力例 1

出力例 1

Yes

はじめ、木は以下のようになっています。

高橋くんは、頂点 1 から 2,3,2,1,6,7,6,1,4,5,8 の順に移動することで、すべての敵を倒すことができます。このとき、高橋くんがいる頂点と高橋くんの強さは以下の図のように変化します（図では、すでに訪れたことのある頂点への移動は省略しています）。

例えば、頂点 1 から 4,5,8 の順に移動すると、頂点 8 に訪れた時点での強さが s _ 8=140 より小さいので高橋くんは敗北してしまい、すべての敵を倒すことができません。

入力例 2

12
1 1 166 619
1 1 17 592
2 1 222 983
2 1 729 338
5 1 747 62
3 1 452 815
3 2 0 1
4 2 0 40
4 1 306 520
6 1 317 591
1 1 507 946

出力例 2

No

入力例 3

12
1 1 1 791
2 2 0 410
2 1 724 790
2 1 828 599
5 2 0 13
3 1 550 803
1 1 802 506
5 1 261 587
6 1 663 329
8 1 11 955
9 1 148 917

出力例 3

Yes

入力例 4

12
1 2 0 1000000000
2 2 0 1000000000
3 2 0 1000000000
4 2 0 1000000000
5 2 0 1000000000
6 2 0 1000000000
7 2 0 1000000000
8 2 0 1000000000
9 2 0 1000000000
10 2 0 1000000000
11 1 1 1

出力例 4

Yes

Score : 550 points

Problem Statement

There is a tree with N vertices. The 1-st vertex is the root, and the parent of the i-th vertex (2\leq i\leq N) is p _ i\ (1\leq p _ i\lt i).

Each non-root vertex has an enemy or a medicine on it. Takahashi wants to defeat all the enemies. Initially, his strength is 1, and he is at vertex 1. For i=2,\ldots,N, the information of the i-th vertex is represented by a triple of integers (t _ i,s _ i,g _ i) as follows.

If t _ i=1, there is an enemy at the i-th vertex. When Takahashi visits this vertex for the first time, if his strength is less than s _ i, Takahashi is defeated by the enemy and loses, after which he cannot move to other vertices. Otherwise, he defeats the enemy, and his strength increases by g _ i.
If t _ i=2, there is a medicine at the i-th vertex. When Takahashi visits this vertex for the first time, he takes the medicine, and his strength is multiplied by g _ i. (For a vertex with a medicine, s _ i=0.)

There are at most 10 vertices with a medicine.

Takahashi can repeatedly move to an adjacent vertex. Determine if he can defeat all the enemies.

Constraints

2\leq N\leq 500
1\leq p _ i\lt i\ (2\leq i\leq N)
t _ i\in\lbrace1,2\rbrace\ (2\leq i\leq N)
t _ i=1\implies1\leq s _ i\leq 10 ^ 9\ (2\leq i\leq N)
t _ i=2\implies s _ i=0\ (2\leq i\leq N)
1\leq g _ i\leq 10 ^ 9\ (2\leq i\leq N)
There are at most 10 vertices with t _ i=2.
All input values are integers.

Input

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

N
p _ 2 t _ 2 s _ 2 g _ 2
p _ 3 t _ 3 s _ 3 g _ 3
\vdots
p _ N t _ N s _ N g _ N

Output

Print the answer (Yes or No) in one line.

Sample Input 1

Sample Output 1

Yes

Initially, the tree looks like this:

Takahashi can defeat all the enemies by moving from vertex 1 to 2,3,2,1,6,7,6,1,4,5,8 in this order. Here, his position and strength change as shown in the following figure (movements to vertices that have already been visited are omitted).

On the other hand, if he moves from vertex 1 to 4,5,8 in this order, for example, his strength when visiting vertex 8 will be less than s _ 8=140, so he will lose without defeating all the enemies.

Sample Input 2

12
1 1 166 619
1 1 17 592
2 1 222 983
2 1 729 338
5 1 747 62
3 1 452 815
3 2 0 1
4 2 0 40
4 1 306 520
6 1 317 591
1 1 507 946

Sample Output 2

No

Sample Input 3

12
1 1 1 791
2 2 0 410
2 1 724 790
2 1 828 599
5 2 0 13
3 1 550 803
1 1 802 506
5 1 261 587
6 1 663 329
8 1 11 955
9 1 148 917

Sample Output 3

Yes

Sample Input 4

12
1 2 0 1000000000
2 2 0 1000000000
3 2 0 1000000000
4 2 0 1000000000
5 2 0 1000000000
6 2 0 1000000000
7 2 0 1000000000
8 2 0 1000000000
9 2 0 1000000000
10 2 0 1000000000
11 1 1 1

Sample Output 4

Yes