AtCoder Daily Training EASY 2026/08/03 18:00start

A - First Grid

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

配点 : 100 点

問題文

縦 2 行、横 2 列のグリッド(各マスが正方形のマス目)があります。
このグリッドは、各マスが黒か白であり、少なくとも 2 つの黒マスを含みます。
各マスの色の情報は文字列 S_1,S_2 として、以下の形式で与えられます。

文字列 S_i の j 文字目が # であれば上から i マス目、左から j マス目は黒
文字列 S_i の j 文字目が . であれば上から i マス目、左から j マス目は白

2 つの異なる黒マス同士が辺で接している時、またその時に限りそれら 2 つの黒マスは直接行き来できます。
黒マスのみをいくつか通ることによって、どの 2 つの黒マス同士も(直接または間接的に)行き来できるかどうか判定してください。

制約

S_1,S_2 は # または . からなる 2 文字の文字列
S_1,S_2 に # が合計で 2 つ以上含まれる

入力

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

S_1
S_2

出力

どの 2 つの黒マス同士も行き来できるなら Yes 、そうでないなら No と出力せよ。

入力例 1

##
.#

出力例 1

Yes

左上の黒マスと右上の黒マス、右上の黒マスと右下の黒マスを直接行き来することができます。
これらの移動を用いてどの黒マスからどの黒マスへも行き来できるので、答えは Yes となります。

入力例 2

.#
#.

出力例 2

No

右上の黒マスと左下の黒マスを行き来することはできません。答えは No となります。

Score : 100 points

Problem Statement

We have a grid with 2 horizontal rows and 2 vertical columns.
Each of the squares is black or white, and there are at least 2 black squares.
The colors of the squares are given to you as strings S_1 and S_2, as follows.

If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left is black.
If the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is white.

You can travel between two different black squares if and only if they share a side.
Determine whether it is possible to travel from every black square to every black square (directly or indirectly) by only passing black squares.

Constraints

Each of S_1 and S_2 is a string with two characters consisting of # and ..
S_1 and S_2 have two or more #s in total.

Input

Input is given from Standard Input in the following format:

S_1
S_2

Output

If it is possible to travel from every black square to every black square, print Yes; otherwise, print No.

Sample Input 1

##
.#

Sample Output 1

Yes

It is possible to directly travel between the top-left and top-right black squares and between top-right and bottom-right squares.
These two moves enable us to travel from every black square to every black square, so the answer is Yes.

Sample Input 2

.#
#.

Sample Output 2

No

It is impossible to travel between the top-right and bottom-left black squares, so the answer is No.

B - Grandma's Footsteps

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

配点 : 150 点

問題文

高橋君は学校でゲームを楽しんでいます。チャイムが鳴ると同時にゲームが開始します。

高橋君はチャイムが鳴った直後から、以下の動作を繰り返し行います。

毎秒 S メートルの速さで A 秒間走る。その後の B 秒間は静止する。

チャイムが鳴ってから X 秒が経過するまでに、高橋君は合計何メートル走りますか？

制約

1 \leq S \leq 15
1 \leq A \leq 1000
1 \leq B \leq 1000
1 \leq X \leq 1000
入力される値はすべて整数

入力

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

S A B X

出力

答えを 1 行に出力せよ。単位 (メートル) は省いて出力すること。

入力例 1

7 3 2 11

出力例 1

チャイムが鳴ってからの 11 秒間、高橋君は以下のように動きます。

0 秒後から 3 秒後までのあいだ、高橋君は毎秒 7 メートルの速さで走る。このあいだの移動距離は 21 メートル。
3 秒後から 5 秒後までのあいだ、高橋君は静止する。
5 秒後から 8 秒後までのあいだ、高橋君は毎秒 7 メートルの速さで走る。このあいだの移動距離は 21 メートル。
8 秒後から 10 秒後までのあいだ、高橋君は静止する。
10 秒後から 11 秒後までのあいだ、高橋君は毎秒 7 メートルの速さで走る。このあいだの移動距離は 7 メートル。

総移動距離は 49 メートルなので、49 を出力します。

入力例 2

6 3 2 9

出力例 2

チャイムが鳴ってからの 9 秒間、高橋君は以下のように動きます。

0 秒後から 3 秒後までのあいだ、高橋君は毎秒 6 メートルの速さで走る。このあいだの移動距離は 18 メートル。
3 秒後から 5 秒後までのあいだ、高橋君は静止する。
5 秒後から 8 秒後までのあいだ、高橋君は毎秒 6 メートルの速さで走る。このあいだの移動距離は 18 メートル。
8 秒後から 9 秒後までのあいだ、高橋君は静止する。

総移動距離は 36 メートルなので、36 を出力します。

入力例 3

1 1 666 428

出力例 3

チャイムが鳴ってからの 428 秒間、高橋君は以下のように動きます。

0 秒後から 1 秒後までのあいだ、高橋君は毎秒 1 メートルの速さで走る。このあいだの移動距離は 1 メートル。
1 秒後から 428 秒後までのあいだ、高橋君は静止する。

総移動距離は 1 メートルなので、1 を出力します。

Score : 150 points

Problem Statement

Takahashi is enjoying a game at school. The game starts at the moment the bell rings.

Immediately after the bell rings, he repeats the following actions:

Run at a speed of S meters per second for A seconds. Then, remain stationary for B seconds.

How many meters in total does he run by the time X seconds have elapsed since the bell rang?

Constraints

1 \leq S \leq 15
1 \leq A \leq 1000
1 \leq B \leq 1000
1 \leq X \leq 1000
All input values are integers.

Input

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

S A B X

Output

Output the answer in one line. Omit the unit (meters) in the output.

Sample Input 1

7 3 2 11

Sample Output 1

During the 11 seconds after the bell rings, Takahashi moves as follows:

From 0 seconds to 3 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 21 meters.
From 3 seconds to 5 seconds, he remains stationary.
From 5 seconds to 8 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 21 meters.
From 8 seconds to 10 seconds, he remains stationary.
From 10 seconds to 11 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 7 meters.

The total distance traveled is 49 meters, so output 49.

Sample Input 2

6 3 2 9

Sample Output 2

During the 9 seconds after the bell rings, Takahashi moves as follows:

From 0 seconds to 3 seconds, he runs at a speed of 6 meters per second. The distance traveled during this time is 18 meters.
From 3 seconds to 5 seconds, he remains stationary.
From 5 seconds to 8 seconds, he runs at a speed of 6 meters per second. The distance traveled during this time is 18 meters.
From 8 seconds to 9 seconds, he remains stationary.

The total distance traveled is 36 meters, so output 36.

Sample Input 3

1 1 666 428

Sample Output 3

During the 428 seconds after the bell rings, Takahashi moves as follows:

From 0 seconds to 1 second, he runs at a speed of 1 meter per second. The distance traveled during this time is 1 meter.
From 1 second to 428 seconds, he remains stationary.

The total distance traveled is 1 meter, so output 1.

C - String Too Long

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

配点 : 200 点

問題文

連長圧縮（ランレングス圧縮）を復元してください。ただし、長すぎる場合には Too Long と出力してください。

N 個の文字と整数の組 (c_1,l_1),(c_2,l_2),\ldots,(c_N,l_N) が与えられます。

l_1 個の文字 c_1、l_2 個の文字 c_2、\ldots、l_N 個の文字 c_N をこの順に連結させた文字列を S とします。

S を出力してください。ただし、S の長さが 100 を超える場合には代わりに Too Long と出力してください。

制約

1\leq N\leq 100
1\leq l_i\leq 10^{18}
N,l_i は整数
c_i は英小文字
c_i\neq c_{i+1}

入力

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

N
c_1 l_1
c_2 l_2
\vdots
c_N l_N

出力

S の長さが 100 以下なら S を、そうでないなら Too Long と出力せよ。

入力例 1

8
m 1
i 1
s 2
i 1
s 2
i 1
p 2
i 1

出力例 1

mississippi

S は mississippi です。S の長さは 100 以下であるため S を出力します。

入力例 2

7
a 1000000000000000000
t 1000000000000000000
c 1000000000000000000
o 1000000000000000000
d 1000000000000000000
e 1000000000000000000
r 1000000000000000000

出力例 2

Too Long

S の長さは 7\times 10^{18} であるため、Too Long を出力します。

入力例 3

1
a 100

出力例 3

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

入力例 4

6
g 4
j 1
m 4
e 4
d 3
i 4

出力例 4

ggggjmmmmeeeedddiiii

Score : 200 points

Problem Statement

Restore run-length encoding. If the result is too long, output Too Long.

You are given N pairs of characters and integers (c_1,l_1),(c_2,l_2),\ldots,(c_N,l_N).

Let S be the string formed by concatenating l_1 characters c_1, l_2 characters c_2, \ldots, and l_N characters c_N in this order.

Output S. However, if the length of S exceeds 100, output Too Long instead.

Constraints

1\leq N\leq 100
1\leq l_i\leq 10^{18}
N and l_i are integers.
Each c_i is a lowercase English letter.
c_i\neq c_{i+1}

Input

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

N
c_1 l_1
c_2 l_2
\vdots
c_N l_N

Output

If the length of S is at most 100, output S; otherwise, output Too Long.

Sample Input 1

8
m 1
i 1
s 2
i 1
s 2
i 1
p 2
i 1

Sample Output 1

mississippi

S is mississippi. Since the length of S is not greater than 100, output S.

Sample Input 2

7
a 1000000000000000000
t 1000000000000000000
c 1000000000000000000
o 1000000000000000000
d 1000000000000000000
e 1000000000000000000
r 1000000000000000000

Sample Output 2

Too Long

The length of S is 7\times 10^{18}, so output Too Long.

Sample Input 3

1
a 100

Sample Output 3

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Input 4

6
g 4
j 1
m 4
e 4
d 3
i 4

Sample Output 4

ggggjmmmmeeeedddiiii

D - Sum of Digits Sequence

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

配点 : 200 点

問題文

正整数 x に対して、f(x) を x の十進表記における各桁の和として定義します。例えば、f(123) = 1 + 2 + 3 = 6 です。

無限数列 A = (A_0, A_1, A_2, \ldots) を以下の式により定義します。

A_0 = 1
i \geq 1 のとき A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)

正整数 N が与えられます。A_N の値を求めてください。

制約

N は 1 以上 100 以下の整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

A_0 = 1
A_1 = f(A_0) = 1
A_2 = f(A_0) + f(A_1) = 2
A_3 = f(A_0) + f(A_1) + f(A_2) = 4
A_4 = f(A_0) + f(A_1) + f(A_2) + f(A_3) = 8
A_5 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) = 16
A_6 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) + f(A_5) = 23

であるため、A_6 = 23 です。

入力例 2

出力例 2

Score : 200 points

Problem Statement

For a positive integer x, define f(x) as the sum of the digits in the decimal representation of x. For example, f(123) = 1 + 2 + 3 = 6.

Define an infinite sequence A = (A_0, A_1, A_2, \ldots) by the following formula:

A_0 = 1
For i \geq 1, A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)

You are given a positive integer N. Find the value of A_N.

Constraints

N is an integer between 1 and 100, inclusive.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

A_0 = 1
A_1 = f(A_0) = 1
A_2 = f(A_0) + f(A_1) = 2
A_3 = f(A_0) + f(A_1) + f(A_2) = 4
A_4 = f(A_0) + f(A_1) + f(A_2) + f(A_3) = 8
A_5 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) = 16
A_6 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) + f(A_5) = 23

Thus, A_6 = 23.

Sample Input 2

Sample Output 2

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