Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
N 個の整数 A_1,A_2,\dots,A_N が与えられます。 また、B_i=A_i\times A_{i+1}\ (1\leq i\leq N-1) と定めます。
B_1,B_2,\dots,B_{N-1} をこの順に空白区切りで出力してください。
制約
- 2\leq N \leq 100
- 1\leq A_i \leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
B_1,B_2,\dots,B_{N-1} をこの順に空白区切りで出力せよ。
入力例 1
3 3 4 6
出力例 1
12 24
B_1=A_1\times A_2 = 12, B_2=A_2\times A_3 = 24 です。
入力例 2
5 22 75 26 45 72
出力例 2
1650 1950 1170 3240
Score: 100 points
Problem Statement
You are given N integers A_1, A_2, \dots, A_N. Also, define B_i = A_i \times A_{i+1}\ (1 \leq i \leq N-1).
Print B_1, B_2, \dots, B_{N-1} in this order, separated by spaces.
Constraints
- 2 \leq N \leq 100
- 1 \leq A_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print B_1, B_2, \dots, B_{N-1} in this order, separated by spaces.
Sample Input 1
3 3 4 6
Sample Output 1
12 24
We have B_1 = A_1 \times A_2 = 12, B_2 = A_2 \times A_3 = 24.
Sample Input 2
5 22 75 26 45 72
Sample Output 2
1650 1950 1170 3240
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
1 文字目が数字、2 文字目が文字 x、3 文字目が数字であるような 3 文字の文字列 S が与えられます。
S の 2 つの数の積を求めてください。
制約
- S は 1 文字目が 1 以上 9 以下の整数、2 文字目が文字
x、3 文字目が 1 以上 9 以下の整数であるような 3 文字の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを整数として出力せよ。
入力例 1
3x8
出力例 1
24
3 \times 8 = 24 より、24 を出力します。
入力例 2
9x9
出力例 2
81
9 \times 9 = 81 より、81 を出力します。
Score : 100 points
Problem Statement
You are given a 3-character string S, where the first character is a digit, the second character is the character x, and the third character is a digit.
Find the product of the two numbers in S.
Constraints
- S is a 3-character string where the first character is an integer between 1 and 9, inclusive, the second character is the character
x, and the third character is an integer between 1 and 9, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer as an integer.
Sample Input 1
3x8
Sample Output 1
24
From 3 \times 8 = 24, print 24.
Sample Input 2
9x9
Sample Output 2
81
From 9 \times 9 = 81, print 81.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
AtCoder社のオフィスは H 行 W 列のマス目で表されます。上から i 行目、左から j 列目のマスを (i, j) と表します。
各マスの状態は文字 S_{i,j} で表され、 S_{i,j} が # のときそのマスは机、. のときそのマスは床です。床のマスは 2 つ以上存在することが保証されます。
あなたは床のマスから異なる 2 マスを選び、加湿器を設置します。
加湿器が設置されたとき、あるマス (i,j) は加湿器があるマス (i',j') からのマンハッタン距離が D 以下であるとき、またその時に限り加湿されます。 なお、マス (i,j) からマス (i',j') までのマンハッタン距離は |i-i'|+|j-j'| で表されます。 ここで、加湿器が置かれた床のマスは必ず加湿されていることに注意してください。
加湿される 床のマス の個数として考えられる最大値を求めてください。
制約
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- 2 \leq H \times W
- 0 \leq D \leq H+W-2
- H,W,D は整数
- S_{i,j} は
#または.である (1 \leq i \leq H, 1 \leq j \leq W) - 床のマスは 2 つ以上存在する
入力
入力は以下の形式で標準入力から与えられる。
H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}
出力
答えを出力せよ。
入力例 1
2 5 1 .###. .#.##
出力例 1
3
マス (1,1) とマス (1,5) に加湿器を置いた時:
- マス (1,1) の加湿器によってマス (1,1),(2,1) の 2 マスが加湿されます。
- マス (1,5) の加湿器によってマス (1,5) の 1 マスが加湿されます。
よって、合計 3 マス加湿されています。また、4 マス以上加湿するような加湿器の置き方は存在しないため、答えは 3 です。
入力例 2
5 5 2 .#.#. ..... .#.#. #.#.# .....
出力例 2
15
マス (2,4) とマス (5,3) に加湿器を置いた時、15 個の床のマスが加湿されます。
入力例 3
4 4 2 .... .##. .##. ....
出力例 3
10
Score : 250 points
Problem Statement
The AtCoder company office can be represented as a grid of H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
The state of each cell is represented by a character S_{i,j}. If S_{i,j} is #, that cell contains a desk; if S_{i,j} is ., that cell is a floor. It is guaranteed that there are at least two floor cells.
You will choose two distinct floor cells and place a humidifier on each.
After placing the humidifiers, a cell (i,j) is humidified if and only if it is within a Manhattan distance D from at least one of the humidifier cells (i',j'). The Manhattan distance between (i,j) and (i',j') is defined as |i - i'| + |j - j'|. Note that any floor cell on which a humidifier is placed is always humidified.
Find the maximum possible number of humidified floor cells.
Constraints
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- 2 \leq H \times W
- 0 \leq D \leq H+W-2
- H,W,D are integers.
- S_{i,j} is
#or.. (1 \leq i \leq H, 1 \leq j \leq W) - There are at least two floor cells.
Input
The input is given from Standard Input in the following format:
H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}
Output
Print the answer.
Sample Input 1
2 5 1 .###. .#.##
Sample Output 1
3
When placing humidifiers on (1,1) and (1,5):
- From the humidifier on (1,1), two cells (1,1) and (2,1) are humidified.
- From the humidifier on (1,5), one cell (1,5) is humidified.
In total, three cells are humidified. No configuration can humidify four or more floor cells, so the answer is 3.
Sample Input 2
5 5 2 .#.#. ..... .#.#. #.#.# .....
Sample Output 2
15
When placing humidifiers on (2,4) and (5,3), 15 floor cells are humidified.
Sample Input 3
4 4 2 .... .##. .##. ....
Sample Output 3
10
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
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.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 個のボールが左右一列に並んでいます。初め、左から i \, (1 \leq i \leq N) 番目のボールには整数 i が書かれています。
高橋君は Q 回の操作を行いました。 i \, (1 \leq i \leq Q) 回目に行われた操作は次のようなものです。
- 整数 x_i が書かれているボールをその右隣のボールと入れ替える。ただし、整数 x_i が書かれているボールが元々右端にあった場合、代わりに左隣のボールと入れ替える。
操作後において左から i \, (1 \leq i \leq N) 番目のボールに書かれている整数を a_i とします。 a_1,\ldots,a_N を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq x_i \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q x_1 \vdots x_Q
出力
a_1,\ldots,a_N を空白区切りで出力せよ。
入力例 1
5 5 1 2 3 4 5
出力例 1
1 2 3 5 4
操作は以下のように行われます。
- 1 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 2,1,3,4,5 となる。
- 2 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,4,5 となる。
- 3 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,4,3,5 となる。
- 4 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,4,5 となる。
- 5 と書かれたボールは右端にあるので左隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,5,4 となる。
入力例 2
7 7 7 7 7 7 7 7 7
出力例 2
1 2 3 4 5 7 6
入力例 3
10 6 1 5 2 9 6 6
出力例 3
1 2 3 4 5 7 6 8 10 9
Score : 300 points
Problem Statement
N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.
Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.
- Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.
Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq x_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q x_1 \vdots x_Q
Output
Print a_1,\ldots,a_N, with spaces in between.
Sample Input 1
5 5 1 2 3 4 5
Sample Output 1
1 2 3 5 4
The operations are performed as follows.
- Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
- Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
- Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
- Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
- Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.
Sample Input 2
7 7 7 7 7 7 7 7 7
Sample Output 2
1 2 3 4 5 7 6
Sample Input 3
10 6 1 5 2 9 6 6
Sample Output 3
1 2 3 4 5 7 6 8 10 9