Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 H 行、横 W 列のマス目があり、各マスには 1 つの整数が書かれています。 上から i 行目、左から j 列目のマスに書かれている整数は A_{i, j} です。
マス目が下記の条件を満たすかどうかを判定してください。
1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たすすべての整数の組 (i_1, i_2, j_1, j_2) について、A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立つ。
制約
- 2 \leq H, W \leq 50
- 1 \leq A_{i, j} \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
出力
マス目が問題文中の条件を満たす場合は Yes と出力し、条件を満たさない場合は No と出力せよ。
入力例 1
3 3 2 1 4 3 1 3 6 4 1
出力例 1
Yes
1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たす整数の組 (i_1, i_2, j_1, j_2) は 9 個存在し、それらすべてについて A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立ちます。例えば、
- (i_1, i_2, j_1, j_2) = (1, 2, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 2, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 2, 2, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 3, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 3, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
が成り立ちます。残りの (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3) についても同様に確認できます。
よって、Yes を出力します。
入力例 2
2 4 4 3 2 1 5 6 7 8
出力例 2
No
問題文中の条件を満たさないので、No を出力します。
例えば、(i_1, i_2, j_1, j_2) = (1, 2, 1, 4) について、A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} です。
Score : 200 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns, where each square contains an integer. The integer written on the square at the i-th row from the top and j-th column from the left is A_{i, j}.
Determine whether the grid satisfies the condition below.
A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds for every quadruple of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W.
Constraints
- 2 \leq H, W \leq 50
- 1 \leq A_{i, j} \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
Output
If the grid satisfies the condition in the Problem Statement, print Yes; otherwise, print No.
Sample Input 1
3 3 2 1 4 3 1 3 6 4 1
Sample Output 1
Yes
There are nine quadruples of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W. For all of them, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds. Some examples follow.
- For (i_1, i_2, j_1, j_2) = (1, 2, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 2, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 2, 2, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 3, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 3, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
We can also see that the property holds for the other quadruples: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
Thus, we should print Yes.
Sample Input 2
2 4 4 3 2 1 5 6 7 8
Sample Output 2
No
We should print No because the condition is not satisfied.
This is because, for example, we have A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} for (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
数字のみからなる長さ 6 の文字列が N 個与えられます。i \, (i = 1, 2, \dots, N) 番目のものを S_i と表します。
さらに、数字のみからなる長さ 3 の文字列が M 個与えられます。j \, (j = 1, 2, \dots, M) 番目のものを T_j と表します。
S_1, S_2, \dots, S_N のうち、末尾 3 文字が T_1, T_2, \dots, T_M のいずれかに一致するものの個数を求めてください。
制約
- 1 \leq N, M \leq 1000
- N, M は整数
- 全ての i = 1, 2, \dots, N に対し、S_i は数字のみからなる長さ 6 の文字列
- 全ての j = 1, 2, \dots, M に対し、T_j は数字のみからなる長さ 3 の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N T_1 T_2 \vdots T_M
出力
答えを出力せよ。
入力例 1
3 3 142857 004159 071028 159 287 857
出力例 1
2
S_1 の末尾 3 文字は 857 であり、これは T_3 に一致します。
S_2 の末尾 3 文字は 159 であり、これは T_1 に一致します。
S_3 の末尾 3 文字は 028 であり、これは T_1, T_2, T_3 のいずれにも一致しません。
以上から、答えは 2 です。
入力例 2
5 4 235983 109467 823476 592801 000333 333 108 467 983
出力例 2
3
入力例 3
4 4 000000 123456 987111 000000 000 111 999 111
出力例 3
3
Score : 200 points
Problem Statement
You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.
You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.
Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.
Constraints
- 1 \leq N, M \leq 1000
- N and M are integers.
- S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
- T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N T_1 T_2 \vdots T_M
Output
Print the answer.
Sample Input 1
3 3 142857 004159 071028 159 287 857
Sample Output 1
2
The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.
Thus, the answer is 2.
Sample Input 2
5 4 235983 109467 823476 592801 000333 333 108 467 983
Sample Output 2
3
Sample Input 3
4 4 000000 123456 987111 000000 000 111 999 111
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
縦 H マス横 W マスのグリッドがあります。グリッドの上から i 行目、左から j 列目のマスを (i, j) と呼びます。
グリッドの各マスには # と . のいずれかの文字が書かれています。(i, j) に書かれている文字を C[i][j] とします。また、整数 i, j が 1 \leq i \leq H と 1 \leq j \leq W の少なくとも一方を満たさない場合、 C[i][j] を . と定義します。
正整数 a, b, n が以下の条件を全て満たす時、(a,b) および (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n) の 4n + 1 マスを (a,b) を中心とするサイズ n のバツ印 と呼びます。
- C[a][b] は
#である。 - 1 \leq d \leq n を満たす整数 d について、 C[a+d][b+d],C[a+d][b-d],C[a-d][b+d],C[a-d][b-d] はいずれも
#である。 - C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1],C[a-n-1][b-n-1] のうち少なくとも 1 つは
.である。
例えば次の図で示された例では、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印がグリッド上にあります。
グリッドにはいくつかのバツ印があります。バツ印を構成するマス以外に # は書かれていません。
また、異なるバツ印を構成するマス同士は頂点を共有しません。以下の 2 つのグリッドは異なるバツ印を構成するマス同士が頂点を共有している例で、このようなグリッドの状態は入力として与えられません。 例えば左のグリッドでは (3, 3) と (4, 4) が頂点を共有しているのが条件に反しています。
N = \min(H, W) とします。また、サイズ n のバツ印の個数を S_n とします。S_1, S_2, \dots, S_N を計算してください。
制約
- 3 \leq H, W \leq 100
- C[i][j] は
#または. - 異なるバツ印を構成するマス同士は頂点を共有しない
- H, W は整数
入力
入力は以下の形式で標準入力から与えられる。
H W C[1][1]C[1][2]\dots C[1][W] C[2][1]C[2][2]\dots C[2][W] \vdots C[H][1]C[H][2]\dots C[H][W]
出力
S_1, S_2, \dots, S_N を空白区切りで出力せよ。
入力例 1
5 9 #.#.#...# .#...#.#. #.#...#.. .....#.#. ....#...#
出力例 1
1 1 0 0 0
問題文に書かれた説明の通り、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印が書かれています。
入力例 2
3 3 ... ... ...
出力例 2
0 0 0
バツ印が 1 個も書かれていない場合もあります。
入力例 3
3 16 #.#.....#.#..#.# .#.......#....#. #.#.....#.#..#.#
出力例 3
3 0 0
入力例 4
15 20 #.#..#.............# .#....#....#.#....#. #.#....#....#....#.. ........#..#.#..#... #.....#..#.....#.... .#...#....#...#..#.# ..#.#......#.#....#. ...#........#....#.# ..#.#......#.#...... .#...#....#...#..... #.....#..#.....#.... ........#.......#... #.#....#....#.#..#.. .#....#......#....#. #.#..#......#.#....#
出力例 4
5 0 1 0 0 0 1 0 0 0 0 0 0 0 0
Score : 300 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..
(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:
- C[a][b] is
#. - C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all
#, for all integers d such that 1 \leq d \leq n, - At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is
..
For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).
The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.
Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.
Constraints
- 3 \leq H, W \leq 100
- C[i][j] is
#or.. - No two different squares that comprise two different crosses share a corner.
- H and W are integers.
Input
The input is given from Standard Input in the following format:
H W C[1][1]C[1][2]\dots C[1][W] C[2][1]C[2][2]\dots C[2][W] \vdots C[H][1]C[H][2]\dots C[H][W]
Output
Print S_1, S_2, \dots, and S_N, separated by spaces.
Sample Input 1
5 9 #.#.#...# .#...#.#. #.#...#.. .....#.#. ....#...#
Sample Output 1
1 1 0 0 0
As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).
Sample Input 2
3 3 ... ... ...
Sample Output 2
0 0 0
There may be no cross.
Sample Input 3
3 16 #.#.....#.#..#.# .#.......#....#. #.#.....#.#..#.#
Sample Output 3
3 0 0
Sample Input 4
15 20 #.#..#.............# .#....#....#.#....#. #.#....#....#....#.. ........#..#.#..#... #.....#..#.....#.... .#...#....#...#..#.# ..#.#......#.#....#. ...#........#....#.# ..#.#......#.#...... .#...#....#...#..... #.....#..#.....#.... ........#.......#... #.#....#....#.#..#.. .#....#......#....#. #.#..#......#.#....#
Sample Output 4
5 0 1 0 0 0 1 0 0 0 0 0 0 0 0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。
制約
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを 998244353 で割った余りを出力せよ。
入力例 1
2 3 4
出力例 1
6
条件を満たす数列は以下の 6 つです。
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
入力例 2
31 41 592
出力例 2
798416518
答えを 998244353 で割った余りを出力してください。
Score : 300 points
Problem Statement
How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
Since the count can get enormous, find it modulo 998244353.
Constraints
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
2 3 4
Sample Output 1
6
The following six sequences satisfy the conditions.
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
Sample Input 2
31 41 592
Sample Output 2
798416518
Be sure to print the count modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N \times N のマス目があります。上から i 行目、左から j 列目のマスを (i,j) と表します。
始め、(1,1) に駒が 1 個置かれています。あなたは以下の操作を何度でも行うことができます。
- 今駒が置かれているマスと距離がちょうど \sqrt{M} であるマスに駒を移動させる。
ここで、マス (i,j) とマス (k,l) の距離は \sqrt{(i-k)^2+(j-l)^2} とします。
全てのマス (i,j) に対して、以下の問題を解いてください。
- 駒を (1,1) から (i,j) に移動させることができるかを判定し、できる場合は操作回数の最小値を求めてください。
制約
- 1 \le N \le 400
- 1 \le M \le 10^6
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
N 行出力せよ。i 行目には N 個の整数を出力せよ。i 行目の j 個目の出力は、マス (i,j) に駒を移動させることができるのであれば操作回数の最小値を、そうでないのであれば -1 を出力せよ。
入力例 1
3 1
出力例 1
0 1 2 1 2 3 2 3 4
駒は上下左右の 4 個のマスに移動することができます。
例えば (2,2) に移動するには、以下のように 2 回の操作を行えばよいです。
- 今駒は (1,1) に置かれている。(1,1) と (1,2) の距離はちょうど \sqrt{1} であるため、駒を (1,2) に移動させる。
- 今駒は (1,2) に置かれている。(1,2) と (2,2) の距離はちょうど \sqrt{1} であるため、駒を (2,2) に移動させる。
入力例 2
10 5
出力例 2
0 3 2 3 2 3 4 5 4 5 3 4 1 2 3 4 3 4 5 6 2 1 4 3 2 3 4 5 4 5 3 2 3 2 3 4 3 4 5 6 2 3 2 3 4 3 4 5 4 5 3 4 3 4 3 4 5 4 5 6 4 3 4 3 4 5 4 5 6 5 5 4 5 4 5 4 5 6 5 6 4 5 4 5 4 5 6 5 6 7 5 6 5 6 5 6 5 6 7 6
Score : 400 points
Problem Statement
There is a grid with N \times N squares. We denote by (i, j) the square at the i-th row from the top and j-th column from the left.
Initially, a piece is placed on (1, 1). You may repeat the following operation any number of times:
- Let (i, j) be the square the piece is currently on. Move the piece to the square whose distance from (i, j) is exactly \sqrt{M}.
Here, we define the distance between square (i, j) and square (k, l) as \sqrt{(i-k)^2+(j-l)^2}.
For all squares (i, j), determine if the piece can reach (i, j). If it can, find the minimum number of operations required to do so.
Constraints
- 1 \le N \le 400
- 1 \le M \le 10^6
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print N lines. The i-th line should contain N integers. If the piece can reach (i, j), the j-th integer in the i-th line should be the minimum number of operations required to do so; otherwise, it should be -1.
Sample Input 1
3 1
Sample Output 1
0 1 2 1 2 3 2 3 4
You can move the piece to four adjacent squares.
For example, we can move the piece to (2,2) with two operations as follows.
- The piece is now on (1,1). The distance between (1,1) and (1,2) is exactly \sqrt{1}, so move the piece to (1,2).
- The piece is now on (1,2). The distance between (1,2) and (2,2) is exactly \sqrt{1}, so move the piece to (2,2).
Sample Input 2
10 5
Sample Output 2
0 3 2 3 2 3 4 5 4 5 3 4 1 2 3 4 3 4 5 6 2 1 4 3 2 3 4 5 4 5 3 2 3 2 3 4 3 4 5 6 2 3 2 3 4 3 4 5 4 5 3 4 3 4 3 4 5 4 5 6 4 3 4 3 4 5 4 5 6 5 5 4 5 4 5 4 5 6 5 6 4 5 4 5 4 5 6 5 6 7 5 6 5 6 5 6 5 6 7 6