実行時間制限: 2 sec / メモリ制限: 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
1 1 1 10 7 7 10 2
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
1 1 1 10 7 7 10 2
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.
実行時間制限: 2 sec / メモリ制限: 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).
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
非負整数 N が与えられるので、以下の条件を満たす非負整数 x を昇順に全て出力してください。
- x を 2 進数として表記した時に 1 となる位の集合が、 N を 2 進数として表記した時に 1 となる位の集合の部分集合となる。
- すなわち、全ての非負整数 k について、「 x の 2^k の位が 1 ならば、 N の 2^k の位は 1 」が成り立つ。
制約
- N は整数
- 0 \le N < 2^{60}
- N を 2 進数として表記した時、 1 となる位は 15 個以下である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを 1 行に 1 つずつ、10 進法の整数として昇順に出力せよ。
入力例 1
11
出力例 1
0 1 2 3 8 9 10 11
N = 11_{(10)} を 2 進数で表記すると、 1011_{(2)} となります。
条件を満たす非負整数 x は以下の通りです。
- 0000_{(2)}=0_{(10)}
- 0001_{(2)}=1_{(10)}
- 0010_{(2)}=2_{(10)}
- 0011_{(2)}=3_{(10)}
- 1000_{(2)}=8_{(10)}
- 1001_{(2)}=9_{(10)}
- 1010_{(2)}=10_{(10)}
- 1011_{(2)}=11_{(10)}
入力例 2
0
出力例 2
0
入力例 3
576461302059761664
出力例 3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
入力は 32bit 符号付き整数に収まらない可能性があります。
Score : 300 points
Problem Statement
You are given a non-negative integer N. Print all non-negative integers x that satisfy the following condition in ascending order.
- The set of the digit positions containing 1 in the binary representation of x is a subset of the set of the digit positions containing 1 in the binary representation of N.
- That is, the following holds for every non-negative integer k: if the digit in the "2^ks" place of x is 1, the digit in the 2^ks place of N is 1.
Constraints
- N is an integer.
- 0 \le N < 2^{60}
- In the binary representation of N, at most 15 digit positions contain 1.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer as decimal integers in ascending order, each in its own line.
Sample Input 1
11
Sample Output 1
0 1 2 3 8 9 10 11
The binary representation of N = 11_{(10)} is 1011_{(2)}.
The non-negative integers x that satisfy the condition are:
- 0000_{(2)}=0_{(10)}
- 0001_{(2)}=1_{(10)}
- 0010_{(2)}=2_{(10)}
- 0011_{(2)}=3_{(10)}
- 1000_{(2)}=8_{(10)}
- 1001_{(2)}=9_{(10)}
- 1010_{(2)}=10_{(10)}
- 1011_{(2)}=11_{(10)}
Sample Input 2
0
Sample Output 2
0
Sample Input 3
576461302059761664
Sample Output 3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
The input may not fit into a 32-bit signed integer.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
AtCoder 王国では、これから N 日間のお祭りが開催されます。そのうち、A_1 日目、A_2 日目、\dots、A_M 日目の M 日では花火が上がります。ここで、お祭りの最終日には花火が上がることが保証されます。(つまり、A_M=N が保証されます。)
i=1,2,\dots,N に対して、以下の問題を解いてください。
- i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後か？ただし、i 日目に花火が上がる場合 0 日後とする。
制約
- 1 \le M \le N \le 2 \times 10^5
- 1 \le A_1 < A_2 < \dots < A_M = N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_M
出力
N 行出力せよ。
i(1 \le i \le N) 行目には、i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後かを整数として出力せよ。
入力例 1
3 2 2 3
出力例 1
1 0 0
AtCoder 王国ではお祭りを 3 日間開催し、2,3 日目に花火が上がります。
- 1 日目以降で初めて花火が上がるのは 2 日目なので、1 日目から数えて 1 日後です。
- 2 日目以降で初めて花火が上がるのは 2 日目なので、2 日目から数えて 0 日後です。
- 3 日目以降で初めて花火が上がるのは 3 日目なので、3 日目から数えて 0 日後です。
入力例 2
8 5 1 3 4 7 8
出力例 2
0 1 0 0 2 1 0 0
Score : 250 points
Problem Statement
The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)
For each i=1,2,\dots,N, solve the following problem.
- How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.
Constraints
- 1 \le M \le N \le 2 \times 10^5
- 1 \le A_1 < A_2 < \dots < A_M = N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_M
Output
Print N lines.
The i-th line (1 \le i \le N) should contain an integer representing the number of days from the i-th day until fireworks are launched for the first time on or after the i-th day.
Sample Input 1
3 2 2 3
Sample Output 1
1 0 0
The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.
- From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
- From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
- From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.
Sample Input 2
8 5 1 3 4 7 8
Sample Output 2
0 1 0 0 2 1 0 0
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
湖の周りに N 個の休憩所があります。
休憩所には時計回りに 1,2,\dots,N の番号が付いています。
休憩所 i から休憩所 i+1 まで時計回りに歩くには A_i 歩かかります ( 但し、休憩所 N+1 は休憩所 1 を指します ) 。
休憩所 s から休憩所 t ( s \neq t ) まで時計回りに歩くのにかかる最小の歩数は M の倍数でした。
(s,t) の組として考えられるものの数を求めてください。
制約
- 入力は全て整数
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 \le M \le 10^6
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
4 3 2 1 4 3
出力例 1
4
- 休憩所 1 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 2 歩で、これは 3 の倍数ではありません。
- 休憩所 1 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
- 休憩所 1 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
- 休憩所 2 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 1 歩で、これは 3 の倍数ではありません。
- 休憩所 2 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
- 休憩所 2 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 8 歩で、これは 3 の倍数ではありません。
- 休憩所 3 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 4 歩で、これは 3 の倍数ではありません。
- 休憩所 3 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
- 休憩所 3 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 9 歩で、これは 3 の倍数です。
- 休憩所 4 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
- 休憩所 4 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
- 休憩所 4 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 6 歩で、これは 3 の倍数です。
以上より、求めるべき (s,t) の組の数は 4 個です。
入力例 2
2 1000000 1 1
出力例 2
0
入力例 3
9 5 9 9 8 2 4 4 3 5 3
出力例 3
11
Score : 400 points
Problem Statement
There are N rest areas around a lake.
The rest areas are numbered 1, 2, ..., N in clockwise order.
It takes A_i steps to walk clockwise from rest area i to rest area i+1 (where rest area N+1 refers to rest area 1).
The minimum number of steps required to walk clockwise from rest area s to rest area t (s \neq t) is a multiple of M.
Find the number of possible pairs (s,t).
Constraints
- All input values are integers
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 \le M \le 10^6
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
4 3 2 1 4 3
Sample Output 1
4
- The minimum number of steps to walk clockwise from rest area 1 to rest area 2 is 2, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 1 to rest area 3 is 3, which is a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 1 to rest area 4 is 7, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 2 to rest area 3 is 1, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 2 to rest area 4 is 5, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 2 to rest area 1 is 8, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 3 to rest area 4 is 4, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 3 to rest area 1 is 7, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 3 to rest area 2 is 9, which is a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 4 to rest area 1 is 3, which is a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 4 to rest area 2 is 5, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 4 to rest area 3 is 6, which is a multiple of 3.
Therefore, there are four possible pairs (s,t).
Sample Input 2
2 1000000 1 1
Sample Output 2
0
Sample Input 3
9 5 9 9 8 2 4 4 3 5 3
Sample Output 3
11