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

A - Weak Beats

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

0 と 1 からなる長さ 16 の文字列 S が与えられます。

2 以上 16 以下のすべての偶数 i について S の i 文字目が 0 ならば Yes を、そうでないならば No を出力してください。

制約

S は 0 と 1 からなる長さ 16 の文字列

入力

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

出力

2 以上 16 以下のすべての偶数 i について S の i 文字目が 0 ならば Yes を、そうでないならば No を出力せよ。

入力例 1

1001000000001010

出力例 1

No

S= 1001000000001010 の 4 文字目が 1 であるため、No を出力します。

入力例 2

1010100000101000

出力例 2

Yes

S= 1010100000101000 の偶数番目の文字はすべて 0 であるため、Yes を出力します。

入力例 3

1111111111111111

出力例 3

No

S の偶数文字目はすべて 1 となっています。特に「すべて 0 」ではないため、No を出力します。

Score : 100 points

Problem Statement

You are given a string S of length 16 consisting of 0 and 1.

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Constraints

S is a string of length 16 consisting of 0 and 1.

Input

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

Output

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Sample Input 1

1001000000001010

Sample Output 1

No

The 4-th character of S= 1001000000001010 is 1, so you should print No.

Sample Input 2

1010100000101000

Sample Output 2

Yes

Every even-positioned character in S= 1010100000101000 is 0, so you should print Yes.

Sample Input 3

1111111111111111

Sample Output 3

No

Every even-positioned character in S is 1. Particularly, they are not all 0, so you should print No.

B - Spread

実行時間制限: 2 sec / メモリ制限: 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

C - 1D Pawn

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

N 個のマスが左右一列に並んでおり、左から順にマス 1、マス 2、…、マス N と番号づけられています。
また、K 個のコマがあり、最初左から i 番目のコマはマス A_i に置かれています。
これらに対して、Q 回の操作を行います。 i 回目の操作では次の操作を行います。

左から L_i 番目のコマが一番右のマスにあるならば何も行わない。
そうでない時、左から L_i 番目のコマがあるマスの 1 つ右のマスにコマが無いならば、左から L_i 番目のコマを 1 つ右のマスに移動させる。 1 つ右のマスにコマがあるならば、何も行わない。

Q 回の操作が終了した後の状態について、i=1,2,\ldots,K に対して左から i 番目のコマがあるマスの番号を出力してください。

制約

1\leq K\leq N\leq 200
1\leq A_1<A_2<\cdots<A_K\leq N
1\leq Q\leq 1000
1\leq L_i\leq K
入力はすべて整数

入力

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

N K Q
A_1 A_2 \ldots A_K
L_1 L_2 \ldots L_Q

出力

K 個の整数を空白区切りで一行に出力せよ。ここで、i 個目の整数は、 Q 回の操作が終了した後の状態について、左から i 番目のコマの番号を表す。

入力例 1

5 3 5
1 3 4
3 3 1 1 2

出力例 1

2 4 5

最初、コマはマス 1, 3, 4 にあります。これに対して以下のように操作が行われます。

左から 3 番目のコマはマス 4 にあります。これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 3 番目のコマをマス 5 に動かします。コマはマス 1, 3, 5 にある状態になります。
左から 3 番目のコマはマス 5 にあります。これは一番右のマスなので、何も行いません。コマはマス 1, 3, 5 にある状態のままです。
左から 1 番目のコマはマス 1 にあります。これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 1 番目のコマをマス 2 に動かします。コマはマス 2, 3, 5 にある状態になります。
左から 1 番目のコマはマス 2 にあります。これは一番右のマスでありませんが、その 1 つ右のマス（マス 3 ）にコマが置かれているため、何も行いません。コマはマス 2, 3, 5 にある状態のままです。
左から 2 番目のコマはマス 3 にあります。これは一番右のマスでなく、その右のマスにもコマが置かれていないため、左から 2 番目のコマをマス 4 に動かします。コマはマス 2, 4, 5 にある状態になります。

よって、Q 回の操作が終わった後でコマはマス 2, 4, 5 に置かれているため、2,4,5 を空白区切りでこの順に出力します。

入力例 2

2 2 2
1 2
1 2

出力例 2

1 2

入力例 3

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

出力例 3

2 5 6 7 9 10

Score : 200 points

Problem Statement

There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them. The i-th operation is as follows:

If the L_i-th piece from the left is on its rightmost square, do nothing.
Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.

Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.

Constraints

1\leq K\leq N\leq 200
1\leq A_1<A_2<\cdots<A_K\leq N
1\leq Q\leq 1000
1\leq L_i\leq K
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K Q
A_1 A_2 \ldots A_K
L_1 L_2 \ldots L_Q

Output

Print K integers in one line, with spaces in between. The i-th of them should be the index of the square on which the i-th piece from the left is after the Q operations have ended.

Sample Input 1

5 3 5
1 3 4
3 3 1 1 2

Sample Output 1

2 4 5

At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:

The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.

Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.

Sample Input 2

2 2 2
1 2
1 2

Sample Output 2

1 2

Sample Input 3

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

Sample Output 3

2 5 6 7 9 10

D - Isolated Seats

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

o と x からなる長さ N の文字列 S が与えられます。
N 個の椅子が左右一列に並んでおり、左から i 番目の椅子には、S の i 文字目が o ならば人が座っており、x ならば人は座っていません。
以下の条件をすべて満たす椅子は何個あるか求めてください。

人が座っていない
左に椅子が無い、または左の椅子に人が座っていない
右に椅子が無い、または右の椅子に人が座っていない

制約

1 \leq N \leq 100
N は整数
S は o と x からなる長さ N の文字列

入力

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

N  
S

出力

答えを 1 行で出力せよ。

入力例 1

8
xxoxxxox

出力例 1

左から 1,5 番目の椅子のみが条件を満たします。

入力例 2

5
ooooo

出力例 2

入力例 3

1
x

出力例 3

Score : 200 points

Problem Statement

You are given a string S of length N consisting of o and x.
N chairs are arranged in a row from left to right. If the i-th character of S is o, a person is sitting in the i-th chair from the left; if it is x, no person is sitting there.
Find the number of chairs that satisfy all of the following conditions.

No person is sitting in it.
There is no chair to its left, or no person is sitting in the chair to its left.
There is no chair to its right, or no person is sitting in the chair to its right.

Constraints

1 \leq N \leq 100
N is an integer.
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

Output the answer in one line.

Sample Input 1

8
xxoxxxox

Sample Output 1

Only the first and fifth chairs from the left satisfy the conditions.

Sample Input 2

5
ooooo

Sample Output 2

Sample Input 3

1
x

Sample Output 3

E - Calendar Validator

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

10^{100} 行 7 列の行列 A があり、任意の整数対 (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7) についてその (i,j) 成分は (i-1) \times 7 + j です。

N 行 M 列の行列 B が与えられるので、B が A から一部の矩形領域を（向きを変えずに）切り出したものであるかを判定してください。

制約

1 \leq N \leq 10^4
1 \leq M \leq 7
1 \leq B_{i,j} \leq 10^9
入力はすべて整数

入力

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

N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}

出力

B が A から一部の矩形領域を切り出したものであれば Yes と、そうでないなら No と出力せよ。

入力例 1

2 3
1 2 3
8 9 10

出力例 1

Yes

与えられる B は、A の左上 2 行 3 列を切り出したものとなっています。

入力例 2

2 1
1
2

出力例 2

No

与えられる B を 90 度回転させると A の左上 1 行 2 列と一致しますが、問題文中に「向きを変えずに」とある通り回転による一致は認められていないため、答えは No となります。

入力例 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

出力例 3

Yes

Score : 300 points

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

1 \leq N \leq 10^4
1 \leq M \leq 7
1 \leq B_{i,j} \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}

Output

If B is some rectangular part of A, print Yes; otherwise, print No.

Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.

Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.

Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes