AtCoder Daily Training EASY 2025/01/02 16:30start

A - Similar String

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

二つの文字 x と y は以下の 3 つの条件のうちどれか 1 つを満たすとき、似た文字と呼ばれます。

x と y は同じ文字
x と y の片方が 1 で、もう片方が l
x と y の片方が 0 で、もう片方が o

また、長さ N の文字列 S と T は以下の条件を満たすとき、似た文字列と呼ばれます。

任意の i\ (1\leq i\leq N) について、 S の i 番目の文字と T の i 番目の文字は似た文字

英小文字及び数字からなる長さ N の文字列 S,T が与えられます。 S と T が似た文字列か判定してください。

制約

N は 1 以上 100 以下の整数
S,T は英小文字及び数字からなる長さ N の文字列

入力

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

N
S
T

出力

S と T が似た文字列の場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

3
l0w
1ow

出力例 1

Yes

S の 1 文字目は lで、T の 1 文字目は 1です。これらは似た文字です。

S の 2 文字目は 0で、T の 2 文字目は oです。これらは似た文字です。

S の 3 文字目は wで、T の 3 文字目は wです。これらは似た文字です。

よって S と T は似た文字列です。

入力例 2

3
abc
arc

出力例 2

No

S の 2 文字目は bで、T の 2 文字目は rです。これらは似た文字ではありません。

よって S と T は似た文字列ではありません。

入力例 3

4
nok0
n0ko

出力例 3

Yes

Score : 100 points

Problem Statement

Two characters x and y are called similar characters if and only if one of the following conditions is satisfied:

x and y are the same character.
One of x and y is 1 and the other is l.
One of x and y is 0 and the other is o.

Two strings S and T, each of length N, are called similar strings if and only if:

for all i\ (1\leq i\leq N), the i-th character of S and the i-th character of T are similar characters.

Given two length-N strings S and T consisting of lowercase English letters and digits, determine if S and T are similar strings.

Constraints

N is an integer between 1 and 100.
Each of S and T is a string of length N consisting of lowercase English letters and digits.

Input

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

N
S
T

Output

Print Yes if S and T are similar strings, and No otherwise.

Sample Input 1

3
l0w
1ow

Sample Output 1

Yes

The 1-st character of S is l, and the 1-st character of T is 1. These are similar characters.

The 2-nd character of S is 0, and the 2-nd character of T is o. These are similar characters.

The 3-rd character of S is w, and the 3-rd character of T is w. These are similar characters.

Thus, S and T are similar strings.

Sample Input 2

3
abc
arc

Sample Output 2

No

The 2-nd character of S is b, and the 2-nd character of T is r. These are not similar characters.

Thus, S and T are not similar strings.

Sample Input 3

4
nok0
n0ko

Sample Output 3

Yes

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

C - Strawberries

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は歯が左右一列に N 本生えています。現在の高橋君の歯の状態はある文字列 S によって表されます。

S の i 文字目が O のとき、左から i 番目の歯が丈夫であることを表します。S の i 文字目が X のとき、左から i 番目の歯が虫歯にかかっていることを表します。丈夫である歯は虫歯にかかっていません。

高橋君はある連続する K 本の歯が丈夫であるとき、その K 本の歯を使ってイチゴを 1 個食べることができます。イチゴを食べると、その K 本の歯が虫歯にかかり丈夫でなくなります。

このとき、高橋君は最大で何個のイチゴを食べることができるか求めてください。

制約

1 \leq K \leq N \leq 100
N,K は整数
S は O と X からなる長さ N の文字列

入力

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

N K
S

出力

答えを出力せよ。

入力例 1

7 3
OOXOOOO

出力例 1

左から 4 本目の歯から左から 6 本目の歯までの連続する 3 本の丈夫な歯を使ってイチゴを 1 個食べることができます。これ以降、イチゴを食べることができません。また、他にどのような方法でイチゴを食べても 1 個以下しか食べることができません。よって、1 を出力します。

入力例 2

12 2
OXXOOOXOOOOX

出力例 2

入力例 3

22 5
XXOOOOOOOOXXOOOOOXXXXX

出力例 3

Score : 200 points

Problem Statement

Takahashi has N teeth arranged in a single row from left to right. The current condition of his teeth is represented by a string S.

If the i-th character of S is O, it means that the i-th tooth from the left is healthy. If it is X, it means that the i-th tooth has a cavity. Healthy teeth do not have cavities.

When he has K consecutive healthy teeth, he can eat one strawberry using those K teeth. After eating a strawberry, those K teeth develop cavities and become unhealthy.

Find the maximum number of strawberries he can eat.

Constraints

1 \leq K \leq N \leq 100
N and K are integers.
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 K
S

Output

Print the answer.

Sample Input 1

7 3
OOXOOOO

Sample Output 1

He can eat one strawberry by using the three consecutive healthy teeth from the 4th to 6th tooth from the left. After this, he cannot eat any more strawberries. Besides, there is no way for him to eat more than one strawberry. Therefore, print 1.

Sample Input 2

12 2
OXXOOOXOOOOX

Sample Output 2

Sample Input 3

22 5
XXOOOOOOOOXXOOOOOXXXXX

Sample Output 3

D - TaK Code

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は 2 次元コード TaK Code を考案しました。以下の条件を全て満たすものが TaK Code です。

縦 9 マス横 9 マスの領域である
左上及び右下の縦 3 マス横 3 マスの領域に含まれる計 18 マスは全て黒である
左上及び右下の縦 3 マス横 3 マスの領域に八方位で隣接する計 14 マスは全て白である

TaK Code を回転させることはできません。

縦 N マス、横 M マスのグリッドがあります。グリッドの状態は N 個の長さ M の文字列 S_1,\ldots,S_N で与えられ、上から i 行目左から j 列目のマスは S_i の j 文字目が # のとき黒、. のとき白です。

グリッドに完全に含まれる縦 9 マス横 9 マスの領域で、TaK Code の条件を満たす箇所を全て求めてください。

制約

9 \leq N,M \leq 100
N,M は整数である
S_i は . および # のみからなる長さ M の文字列である

入力

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

N M
S_1
\vdots
S_N

出力

上から i 行目左から j 列目のマスを左上とする縦 9 マス横 9 マスの領域が TaK Code の条件を満たす (i,j) の組全てを辞書順の昇順で 1 行に 1 組ずつ、i,j をこの順に空白区切りで出力せよ。
(i,j) の組の辞書順の昇順とは、i の昇順、i が等しい組は j の昇順にすることである。

入力例 1

19 18
###......###......
###......###......
###..#...###..#...
..............#...
..................
..................
......###......###
......###......###
......###......###
.###..............
.###......##......
.###..............
............###...
...##.......###...
...##.......###...
.......###........
.......###........
.......###........
........#.........

出力例 1

TaK Code は以下のものです。# が黒マス、. が白マス、? が白黒どちらでもよいマスを表します。

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

入力で与えられたグリッドの上から 10 マス目左から 2 列目のマスを左上とする縦 9 マス横 9 マスの領域は以下のようになっており、TaK Code の条件を満たします。

###......
###......
###......
.........
..##.....
..##.....
......###
......###
......###

入力例 2

9 21
###.#...........#.###
###.#...........#.###
###.#...........#.###
....#...........#....
#########...#########
....#...........#....
....#.###...###.#....
....#.###...###.#....
....#.###...###.#....

出力例 2

1 1

入力例 3

18 18
######............
######............
######............
######............
######............
######............
..................
..................
..................
..................
..................
..................
............######
............######
............######
............######
............######
............######

出力例 3

TaK Code の条件を満たす箇所が 1 つもないこともあります。

Score : 200 points

Problem Statement

Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:

It is a region consisting of nine horizontal rows and nine vertical columns.
All the 18 cells in the top-left and bottom-right three-by-three regions are black.
All the 14 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.

It is not allowed to rotate a TaK Code.

You are given a grid with N horizontal rows and M vertical columns. The state of the grid is described by N strings, S_1,\ldots, and S_N, each of length M. The cell 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 #, and white if it is ..

Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.

Constraints

9 \leq N,M \leq 100
N and M are integers.
S_i is a string of length M consisting of . and #.

Input

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

N M
S_1
\vdots
S_N

Output

For all pairs (i,j) such that the nine-by-nine region, whose top-left cell is at the i-th row from the top and j-th columns from the left, satisfies the conditions of a TaK Code, print a line containing i, a space, and j in this order.
The pairs must be sorted in lexicographical ascending order; that is, i must be in ascending order, and within the same i, j must be in ascending order.

Sample Input 1

19 18
###......###......
###......###......
###..#...###..#...
..............#...
..................
..................
......###......###
......###......###
......###......###
.###..............
.###......##......
.###..............
............###...
...##.......###...
...##.......###...
.......###........
.......###........
.......###........
........#.........

Sample Output 1

A TaK Code looks like the following, where # is a black cell, . is a white cell, and ? can be either black or white.

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

In the grid given by the input, the nine-by-nine region, whose top-left cell is at the 10-th row from the top and 2-nd column from the left, satisfies the conditions of a TaK Code, as shown below.

###......
###......
###......
.........
..##.....
..##.....
......###
......###
......###

Sample Input 2

9 21
###.#...........#.###
###.#...........#.###
###.#...........#.###
....#...........#....
#########...#########
....#...........#....
....#.###...###.#....
....#.###...###.#....
....#.###...###.#....

Sample Output 2

1 1

Sample Input 3

18 18
######............
######............
######............
######............
######............
######............
..................
..................
..................
..................
..................
..................
............######
............######
............######
............######
............######
............######

Sample Output 3

There may be no region that satisfies the conditions of TaK Code.

E - Minimize Abs 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正整数 D が与えられます。

非負整数 x,y に対する |x^2+y^2-D| の最小値を求めてください。

制約

1\leq D \leq 2\times 10^{12}
入力は全て整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

x=4,y=2 のとき |x^2+y^2-D| = |16+4-21|=1 となります。

|x^2+y^2-D|=0 を満たすような非負整数 x,y は存在しないので、答えは 1 です。

入力例 2

998244353

出力例 2

入力例 3

264428617

出力例 3

Score : 300 points

Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

1\leq D \leq 2\times 10^{12}
All input values are integers.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

Sample Input 3

264428617