Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
N が与えられます。2^N を出力してください。
制約
- 0 \leq N \leq 30
- N は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
3
出力例 1
8
2^3=8 です。
入力例 2
30
出力例 2
1073741824
Score : 100 points
Problem Statement
Given N, print 2^N.
Constraints
- 0 \leq N \leq 30
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
8
We have 2^3=8.
Sample Input 2
30
Sample Output 2
1073741824
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
100 以上 999 以下の整数 S が与えられます。
S が 200 以上 299 以下のとき Success 、そうでないとき Failure と出力してください。
制約
- 100\leq S\leq999
- S は整数
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
200
出力例 1
Success
200 は 200 以上 299 以下なので、Success と出力してください。
入力例 2
401
出力例 2
Failure
401 は 200 以上 299 以下ではないので、Failure と出力してください。
入力例 3
999
出力例 3
Failure
Score : 100 points
Problem Statement
You are given an integer S between 100 and 999 (inclusive).
If S is between 200 and 299 (inclusive), print Success; otherwise, print Failure.
Constraints
- 100 \le S \le 999
- S is an integer.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
200
Sample Output 1
Success
200 is between 200 and 299, so print Success.
Sample Input 2
401
Sample Output 2
Failure
401 is not between 200 and 299, so print Failure.
Sample Input 3
999
Sample Output 3
Failure
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 人の AtCoder ユーザーが集まり、 AtCoderじゃんけん2 を行います。i 人目のユーザー名は S_i 、レートは C_i です。
AtCoderじゃんけん2 は以下の手順で行われます。
- それぞれのユーザーに、ユーザー名の辞書順に 0, 1, \dots ,N - 1 の番号を割り当てる。
- N 人のレートの総和を T とする。番号 T \bmod N を割り当てられたユーザーが勝者となる。
勝者のユーザー名を出力してください。
辞書順とは？
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 S, T の大小を判定するアルゴリズムを以下に説明します。
以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S, T のうち長さが大きくない方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、S_j が T_j よりアルファベット順で小さい場合は S \lt T 、そうでない場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
制約
- 1 \leq N \leq 100
- S_i は英小文字からなる長さ 3 以上 16 以下の文字列
- S_1, S_2, \dots ,S_N は全て異なる
- 1 \leq C_i \leq 4229
- C_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N S_1 C_1 S_2 C_2 \vdots S_N C_N
出力
答えを一行に出力せよ。
入力例 1
3 takahashi 2 aoki 6 snuke 5
出力例 1
snuke
3 人のレートの総和は 13 です。また、それぞれの名前を辞書順に並び替えると、 aoki snuke takahashi の順になるので aoki に番号 0 が、 snuke に 番号 1 が、 takahashi に番号 2 が割り当てられます。
13 \bmod 3 = 1 なので、番号 1 を割り当てられた snuke を出力します。
入力例 2
3 takahashi 2813 takahashixx 1086 takahashix 4229
出力例 2
takahashix
Score : 200 points
Problem Statement
N AtCoder users have gathered to play AtCoder RPS 2. The i-th user's name is S_i and their rating is C_i.
AtCoder RPS 2 is played as follows:
- Assign the numbers 0, 1, \dots, N - 1 to the users in lexicographical order of their usernames.
- Let T be the sum of the ratings of the N users. The user assigned the number T \bmod N is the winner.
Print the winner's username.
What is lexicographical order?
Lexicographical order, simply put, means "the order in which words appear in a dictionary." More precisely, the algorithm to determine the order of two distinct strings S and T consisting of lowercase English letters is as follows:
Here, "the i-th character of S" is denoted as S_i. If S is lexicographically smaller than T, we write S \lt T, and if S is larger, we write S \gt T.
- Let L be the length of the shorter string among S and T. Check if S_i and T_i match for i=1,2,\dots,L.
- If there exists an i such that S_i \neq T_i, let j be the smallest such i. Compare S_j and T_j. If S_j is alphabetically smaller than T_j, then S \lt T. Otherwise, S \gt T. The algorithm ends here.
- If there is no i such that S_i \neq T_i, compare the lengths of S and T. If S is shorter than T, then S \lt T. If S is longer, then S \gt T. The algorithm ends here.
Constraints
- 1 \leq N \leq 100
- S_i is a string consisting of lowercase English letters with length between 3 and 16, inclusive.
- S_1, S_2, \dots, S_N are all distinct.
- 1 \leq C_i \leq 4229
- C_i is an integer.
Input
The input is given from Standard Input in the following format:
N S_1 C_1 S_2 C_2 \vdots S_N C_N
Output
Print the answer on a single line.
Sample Input 1
3 takahashi 2 aoki 6 snuke 5
Sample Output 1
snuke
The sum of the ratings of the three users is 13. Sorting their names in lexicographical order yields aoki, snuke, takahashi, so aoki is assigned number 0, snuke is 1, and takahashi is 2.
Since 13 \bmod 3 = 1, print snuke, who is assigned number 1.
Sample Input 2
3 takahashi 2813 takahashixx 1086 takahashix 4229
Sample Output 2
takahashix
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
英小文字からなる長さ 3 以上の文字列 S が与えられます。
S はちょうど 2 種類の文字を含み、 1 文字だけ他の文字と異なります。その 1 文字を答えてください。
例えば、 S が odd なら o と答えてください。
制約
- S は英小文字からなる長さ 3 以上 10 以下の文字列
- S はちょうど 2 種類の文字を含み、 1 文字だけ他の文字と異なる
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
odd
出力例 1
o
odd のうち他の文字と異なるものは o です。
入力例 2
dad
出力例 2
a
dad のうち他の文字と異なるものは a です。
入力例 3
wwwwwwwwwv
出力例 3
v
wwwwwwwwwv のうち他の文字と異なるものは v です。
Score : 200 points
Problem Statement
You are given a string S of length at least 3 consisting of lowercase English letters.
S contains exactly two types of characters, and exactly one character is different from the others. Find that one character.
For example, if S is odd, report o.
Constraints
- S is a string of length at least 3 and at most 10 consisting of lowercase English letters.
- S contains exactly two types of characters, and exactly one character is different from the others.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
odd
Sample Output 1
o
In odd, the character different from the others is o.
Sample Input 2
dad
Sample Output 2
a
In dad, the character different from the others is a.
Sample Input 3
wwwwwwwwwv
Sample Output 3
v
In wwwwwwwwwv, the character different from the others is v.
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N 行 N 列のグリッドが与えられます。ここで、N は偶数です。グリッドの上から i 行目、左から j 列目のマスをマス (i, j) と表記します。
グリッドの各マスは黒か白のいずれかで塗られており、A_{i, j} = # のときマス (i, j) は黒、A_{i, j} = . のときマス (i, j) は白で塗られています。
i = 1, 2, \ldots, \frac{N}{2} の順に以下の操作を行った後のグリッドの各マスの色を求めてください。
- i 以上 N + 1 - i 以下の整数 x, y について、マス (y, N + 1 - x) の色をマス (x, y) の色で置き換える。この置き換えは条件を満たすすべての整数 x, y について同時に行う。
制約
- N は 2 以上 3000 以下の偶数
- A_{i, j} は
#または.
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1, 1}A_{1, 2}\ldotsA_{1, N}
A_{2, 1}A_{2, 2}\ldotsA_{2, N}
\vdots
A_{N, 1}A_{N, 2}\ldotsA_{N, N}
出力
すべての操作を終えた後、マス (i, j) の色が黒であるとき B_{i, j} = #、マス (i, j) の色が白であるとき B_{i, j} = . として以下の形式で出力せよ。
B_{1, 1}B_{1, 2}\ldotsB_{1, N}
B_{2, 1}B_{2, 2}\ldotsB_{2, N}
\vdots
B_{N, 1}B_{N, 2}\ldotsB_{N, N}
入力例 1
8 .......# .......# .####..# .####..# .##....# .##....# .####### .#######
出力例 1
........ #######. #.....#. #.###.#. #.#...#. #.#####. #....... ########
操作によってグリッドの各マスの色は以下のように変化します。
.......# ........ ........ ........ ........ .......# ######.. #######. #######. #######. .####..# ######.. #....##. #.....#. #.....#. .####..# → ##..##.. → #....##. → #.##..#. → #.###.#. .##....# ##..##.. #..####. #.##..#. #.#...#. .##....# ##...... #..####. #.#####. #.#####. .####### ##...... #....... #....... #....... .####### ######## ######## ######## ########
入力例 2
6 .#.#.# ##.#.. ...### ###... ..#.## #.#.#.
出力例 2
#.#.#. .#.#.# #.#.#. .#.#.# #.#.#. .#.#.#
入力例 3
12 .......#.### #...#...#..# ###.#..##### ..#.#.#.#... .#.....#.### .......#.#.. #...#..#.... #####....... ...#...#.#.# ..###..#..## #..#.#.#.#.# .####.......
出力例 3
.#..##...##. #.#.#.#.#... ###.##..#... #.#.#.#.#... #.#.##...##. ............ ............ .###.###.### ...#...#.#.. .###...#.### ...#...#...# .###...#.###
Score : 400 points
Problem Statement
You are given a grid with N rows and N columns, where N is an even number. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Each cell is painted black or white. If A_{i, j} = #, cell (i, j) is black; if A_{i, j} = ., it is white.
Find the color of each cell after performing the following operation for i = 1, 2, \ldots, \frac{N}{2} in this order.
- For all pairs of integers x, y between i and N + 1 - i, inclusive, replace the color of cell (y, N + 1 - x) with the color of cell (x, y). Perform these replacements simultaneously for all such pairs x, y.
Constraints
- N is an even number between 2 and 3000, inclusive.
- Each A_{i, j} is
#or..
Input
The input is given from Standard Input in the following format:
N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}
Output
After all operations, let B_{i, j} = # if cell (i, j) is black, and B_{i, j} = . if it is white. Print the grid in the following format:
B_{1,1}B_{1,2}\ldots B_{1,N}
B_{2,1}B_{2,2}\ldots B_{2,N}
\vdots
B_{N,1}B_{N,2}\ldots B_{N,N}
Sample Input 1
8 .......# .......# .####..# .####..# .##....# .##....# .####### .#######
Sample Output 1
........ #######. #.....#. #.###.#. #.#...#. #.#####. #....... ########
The operations change the colors of the grid cells as follows:
.......# ........ ........ ........ ........ .......# ######.. #######. #######. #######. .####..# ######.. #....##. #.....#. #.....#. .####..# → ##..##.. → #....##. → #.##..#. → #.###.#. .##....# ##..##.. #..####. #.##..#. #.#...#. .##....# ##...... #..####. #.#####. #.#####. .####### ##...... #....... #....... #....... .####### ######## ######## ######## ########
Sample Input 2
6 .#.#.# ##.#.. ...### ###... ..#.## #.#.#.
Sample Output 2
#.#.#. .#.#.# #.#.#. .#.#.# #.#.#. .#.#.#
Sample Input 3
12 .......#.### #...#...#..# ###.#..##### ..#.#.#.#... .#.....#.### .......#.#.. #...#..#.... #####....... ...#...#.#.# ..###..#..## #..#.#.#.#.# .####.......
Sample Output 3
.#..##...##. #.#.#.#.#... ###.##..#... #.#.#.#.#... #.#.##...##. ............ ............ .###.###.### ...#...#.#.. .###...#.### ...#...#...# .###...#.###
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
左右一列に N 個のマスが並んでいます。 最初、すべてのマスは白く塗られています。
Q 個のクエリを順に処理してください。i 個目のクエリでは 1 以上 N 以下の整数 A_i が与えられ、次の操作を行います。
左から A_i 番目のマスの色を反転させる。 具体的には、左から A_i 番目のマスが、白く塗られていたならば黒く塗り、黒く塗られていたならば白く塗る。
その後、黒く塗られたマスが連続している区間の個数を求める。ここで、黒く塗られたマスが連続している区間とは次をすべてみたす整数の組 (l,r) (1\leq l\leq r\leq N) を指す。
- 左から l, l+1, \ldots, r 番目のマスはすべて黒く塗られている。
- l=1 であるか、または左から (l-1) 番目のマスは白く塗られている。
- r=N であるか、または左から (r+1) 番目のマスは白く塗られている。
制約
- 1\leq N,Q\leq 5\times 10^5
- 1\leq A_i\leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \ldots A_Q
出力
Q 行出力せよ。i 行目 (1\leq i\leq Q) には i 個目のクエリの答えを出力せよ。
入力例 1
5 7 2 3 3 5 1 5 2
出力例 1
1 1 1 2 2 1 1
以下では、左から i 番目のマスを マス i と表します。
各クエリの後は次のような状態になっています。
- 1 個目のクエリの後、マス 2 のみが黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(2,2) の 1 つです。
- 2 個目のクエリの後、マス 2,3 が黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(2,3) の 1 つです。
- 3 個目のクエリの後、マス 2 のみが黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(2,2) の 1 つです。
- 4 個目のクエリの後、マス 2,5 が黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(2,2), (5,5) の 2 つです。
- 5 個目のクエリの後、マス 1,2,5 が黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(1,2), (5,5) の 2 つです。
- 6 個目のクエリの後、マス 1,2 のみが黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(1,2) の 1 つです。
- 7 個目のクエリの後、マス 1 のみが黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(1,1) の 1 つです。
よって、1,1,1,2,2,1,1 を改行区切りで出力します。
入力例 2
1 2 1 1
出力例 2
1 0
2 個目のクエリの後、すべてのマスは白く塗られているため、2 行目には 0 を出力します。
入力例 3
3 3 1 3 2
出力例 3
1 2 1
Score : 350 points
Problem Statement
There are N squares arranged in a row from left to right. Initially, all squares are painted white.
Process Q queries in order. The i-th query gives an integer A_i between 1 and N, inclusive, and performs the following operation:
Flip the color of the A_i-th square from the left. Specifically, if the A_i-th square from the left is painted white, paint it black; if it is painted black, paint it white.
Then, find the number of intervals of consecutively painted black squares.Here, an interval of consecutively painted black squares is a pair of integers (l,r) (1\leq l\leq r\leq N) that satisfy all of the following:
- The l-th, (l+1)-th, \ldots, r-th squares from the left are all painted black.
- Either l=1, or the (l-1)-th square from the left is painted white.
- Either r=N, or the (r+1)-th square from the left is painted white.
Constraints
- 1\leq N,Q\leq 5\times 10^5
- 1\leq A_i\leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q A_1 A_2 \ldots A_Q
Output
Output Q lines. On the i-th line (1\leq i\leq Q), output the answer to the i-th query.
Sample Input 1
5 7 2 3 3 5 1 5 2
Sample Output 1
1 1 1 2 2 1 1
Below, the i-th square from the left is referred to as square i.
After each query, the state is as follows:
- After the 1st query, only square 2 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,2).
- After the 2nd query, squares 2,3 are painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,3).
- After the 3rd query, only square 2 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,2).
- After the 4th query, squares 2,5 are painted black. There are 2 intervals of consecutively painted black squares: (l,r)=(2,2), (5,5).
- After the 5th query, squares 1,2,5 are painted black. There are 2 intervals of consecutively painted black squares: (l,r)=(1,2), (5,5).
- After the 6th query, only squares 1,2 are painted black. There is 1 interval of consecutively painted black squares: (l,r)=(1,2).
- After the 7th query, only square 1 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(1,1).
Thus, output 1,1,1,2,2,1,1 separated by newlines.
Sample Input 2
1 2 1 1
Sample Output 2
1 0
After the 2nd query, all squares are painted white, so output 0 on the 2nd line.
Sample Input 3
3 3 1 3 2
Sample Output 3
1 2 1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
H 行 W 列のマス目があります。マス目の上から i 番目、左から j 番目のマスをマス (i,j) と表記します。
マス (i,j) は S_{i,j} が . のとき空きマスであり、# のとき障害物があります。
ある空きマスを出発し、上下左右に隣接するマスへの移動を K 回行う方法であって、障害物のあるマスを通らず、同じマスを 2 回以上通らないようなものの個数を数えてください。
具体的には、長さ K+1 の列 ((i_0,j_0),(i_1,j_1),\dots,(i_K,j_K)) であって、以下を満たすものの個数を数えてください。
- 各 0 \leq k \leq K について、 1 \leq i_k \leq H, 1 \leq j_k \leq W かつ S_{i_k,j_k} は
.である - 各 0 \leq k \leq K-1 について、 |i_{k+1}-i_k| + |j_{k+1}-j_k| = 1
- 各 0 \leq k < l \leq K について、 (i_k,j_k)\neq (i_l,j_l) である
制約
- 1 \leq H,W \leq 10
- 1 \leq K \leq 11
- H,W,K は整数
- S_{i,j} は
.または# - 空きマスが少なくとも 1 つ存在する
入力
入力は以下の形式で標準入力から与えられる。
H W K
S_{1,1}S_{1,2}\dots S_{1,W}
S_{2,1}S_{2,2}\dots S_{2,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}
出力
答えを出力せよ。
入力例 1
2 2 2 .# ..
出力例 1
2
可能な経路は、以下の 2 通りです。
- (1,1) \to (2,1) \to (2,2)
- (2,2) \to (2,1) \to (1,1)
入力例 2
2 3 1 .#. #.#
出力例 2
0
入力例 3
10 10 11 ....#..#.. .#.....##. ..#...##.. ...#...... ......##.. ..#......# #........# ..##...... .###....#. ...#.....#
出力例 3
218070
Score : 425 points
Problem Statement
There is a grid of H \times W cells. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.
Cell (i, j) is empty if S_{i,j} is ., and blocked if it is #.
Count the number of ways to start from an empty cell and make K moves to adjacent cells (up, down, left, or right), without passing through blocked squares and not visiting the same cell more than once.
Specifically, count the number of sequences of length K+1, ((i_0, j_0), (i_1, j_1), \dots, (i_K, j_K)), satisfying the following.
- 1 \leq i_k \leq H, 1 \leq j_k \leq W, and S_{i_k, j_k} is
., for each 0 \leq k \leq K. - |i_{k+1} - i_k| + |j_{k+1} - j_k| = 1 for each 0 \leq k \leq K-1.
- (i_k, j_k) \neq (i_l, j_l) for each 0 \leq k < l \leq K.
Constraints
- 1 \leq H, W \leq 10
- 1 \leq K \leq 11
- H, W, and K are integers.
- Each S_{i,j} is
.or#. - There is at least one empty cell.
Input
The input is given from Standard Input in the following format:
H W K
S_{1,1}S_{1,2}\dots S_{1,W}
S_{2,1}S_{2,2}\dots S_{2,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}
Output
Print the answer.
Sample Input 1
2 2 2 .# ..
Sample Output 1
2
Here are the two possible paths:
- (1,1) \rightarrow (2,1) \rightarrow (2,2)
- (2,2) \rightarrow (2,1) \rightarrow (1,1)
Sample Input 2
2 3 1 .#. #.#
Sample Output 2
0
Sample Input 3
10 10 11 ....#..#.. .#.....##. ..#...##.. ...#...... ......##.. ..#......# #........# ..##...... .###....#. ...#.....#
Sample Output 3
218070
Time Limit: 6 sec / Memory Limit: 1024 MiB
配点 : 500 点
コンテスト開催当時はメモリ制限が2GBでしたが、ジャッジ環境が異なるため、現在はメモリ制限を1GBに設定しております。なお、このメモリ制限でもAC出来ることは確認しています。
問題文
ここに、 N \times N のチェス盤があります。このチェス盤の上から i 行目、左から j 列目にあるマスをマス (i,j) と呼びます。
チェス盤の情報は N 個の文字列 S_i として与えられます。
文字列 S_i の j 文字目である S_{i,j} には、以下の情報が含まれています。
- S_{i,j}=
.のとき マス (i,j) には何も置かれていない。 - S_{i,j}=
#のとき マス (i,j) には白のポーンが 1 つ置かれている。このポーンを動かしたり取り除いたりすることはできない。
この盤面のマス (A_x,A_y) に、白のビショップを 1 つ置きました。
この白のビショップをチェスのルール (注記参照) に従ってマス (A_x,A_y) からマス (B_x,B_y) に移動させるために必要な最小の手数を求めてください。
ただし、移動できない場合は代わりに -1 を出力してください。
注記
マス (i,j) に置かれている白の ビショップ は、 1 手で以下のルールに従って移動することができます。
-
各正整数 d について、以下の条件を全て満たせばマス (i+d,j+d) に移動できる。
- マス (i+d,j+d) が盤内に存在する
- 全ての正整数 l \le d について、 (i+l,j+l) に白のポーンがない
-
各正整数 d について、以下の条件を全て満たせばマス (i+d,j-d) に移動できる。
- マス (i+d,j-d) が盤内に存在する
- 全ての正整数 l \le d について、 (i+l,j-l) に白のポーンがない
-
各正整数 d について、以下の条件を全て満たせばマス (i-d,j+d) に移動できる。
- マス (i-d,j+d) が盤内に存在する
- 全ての正整数 l \le d について、 (i-l,j+l) に白のポーンがない
-
各正整数 d について、以下の条件を全て満たせばマス (i-d,j-d) に移動できる。
- マス (i-d,j-d) が盤内に存在する
- 全ての正整数 l \le d について、 (i-l,j-l) に白のポーンがない
制約
- 2 \le N \le 1500
- 1 \le A_x,A_y \le N
- 1 \le B_x,B_y \le N
- (A_x,A_y) \neq (B_x,B_y)
- S_i は
.および#からなる N 文字の文字列 - S_{A_x,A_y}=
. - S_{B_x,B_y}=
.
入力
入力は以下の形式で標準入力から与えられる。
N A_x A_y B_x B_y S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
5 1 3 3 5 ....# ...#. ..... .#... #....
出力例 1
3
以下のように移動させることで 3 手でビショップを (1,3) から (3,5) まで移動させることができます。 2 手以内でビショップを (1,3) から (3,5) まで移動させることはできません。
- (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)
入力例 2
4 3 2 4 2 .... .... .... ....
出力例 2
-1
どのようにビショップを動かしても (3,2) から (4,2) に移動させることはできません。
入力例 3
18 18 1 1 18 .................. .####............. .#..#..####....... .####..#..#..####. .#..#..###...#.... .#..#..#..#..#.... .......####..#.... .............####. .................. .................. .####............. ....#..#..#....... .####..#..#..####. .#.....####..#.... .####.....#..####. ..........#..#..#. .............####. ..................
出力例 3
9
Score : 500 points
During the time of the contest, the memory limit was set to 2GB. However, due to a change in the judging environment, the memory limit has now been set to 1GB. Please note that it has been confirmed that solutions can still achieve an Acceptable Completion (AC) within this memory limit.
Problem Statement
We have an N \times N chessboard. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of this board.
The board is described by N strings S_i.
The j-th character of the string S_i, S_{i,j}, means the following.
- If S_{i,j}=
., the square (i, j) is empty. - If S_{i,j}=
#, the square (i, j) is occupied by a white pawn, which cannot be moved or removed.
We have put a white bishop on the square (A_x, A_y).
Find the minimum number of moves needed to move this bishop from (A_x, A_y) to (B_x, B_y) according to the rules of chess (see Notes).
If it cannot be moved to (B_x, B_y), report -1 instead.
Notes
A white bishop on the square (i, j) can go to the following positions in one move.
-
For each positive integer d, it can go to (i+d,j+d) if all of the conditions are satisfied.
- The square (i+d,j+d) exists in the board.
- For every positive integer l \le d, (i+l,j+l) is not occupied by a white pawn.
-
For each positive integer d, it can go to (i+d,j-d) if all of the conditions are satisfied.
- The square (i+d,j-d) exists in the board.
- For every positive integer l \le d, (i+l,j-l) is not occupied by a white pawn.
-
For each positive integer d, it can go to (i-d,j+d) if all of the conditions are satisfied.
- The square (i-d,j+d) exists in the board.
- For every positive integer l \le d, (i-l,j+l) is not occupied by a white pawn.
-
For each positive integer d, it can go to (i-d,j-d) if all of the conditions are satisfied.
- The square (i-d,j-d) exists in the board.
- For every positive integer l \le d, (i-l,j-l) is not occupied by a white pawn.
Constraints
- 2 \le N \le 1500
- 1 \le A_x,A_y \le N
- 1 \le B_x,B_y \le N
- (A_x,A_y) \neq (B_x,B_y)
- S_i is a string of length N consisting of
.and#. - S_{A_x,A_y}=
. - S_{B_x,B_y}=
.
Input
Input is given from Standard Input in the following format:
N A_x A_y B_x B_y S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
5 1 3 3 5 ....# ...#. ..... .#... #....
Sample Output 1
3
We can move the bishop from (1,3) to (3,5) in three moves as follows, but not in two or fewer moves.
- (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)
Sample Input 2
4 3 2 4 2 .... .... .... ....
Sample Output 2
-1
There is no way to move the bishop from (3,2) to (4,2).
Sample Input 3
18 18 1 1 18 .................. .####............. .#..#..####....... .####..#..#..####. .#..#..###...#.... .#..#..#..#..#.... .......####..#.... .............####. .................. .................. .####............. ....#..#..#....... .####..#..#..####. .#.....####..#.... .####.....#..####. ..........#..#..#. .............####. ..................
Sample Output 3
9
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
半径で切って N 等分された円形のケーキがあります。
各ピースには時計回りに 1, 2, \ldots, N の番号が付けられています。また、1 \leq i \leq N なる整数 i についてピース i をピース N + i とも呼ぶこととします。
はじめ、すべてのピースの色は色 0 です。
あなたは、以下の操作を好きな回数行うことができます。
- 1 \leq a, b, c \leq N なる整数 a, b, c を選ぶ。0 \leq i < b なる各整数 i に対してピース a + i の色を色 c に変更する。この操作にはコストが b + X_c かかる。
1 \leq i \leq N なるすべての整数 i に対してピース i の色を色 C_i にするために必要なコストの合計の最小値を求めてください。
制約
- 1 \leq N \leq 400
- 1 \leq C_i \leq N
- 1 \leq X_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N C_1 C_2 \ldots C_N X_1 X_2 \ldots X_N
出力
答えを出力せよ。
入力例 1
6 1 4 2 1 2 5 1 2 3 4 5 6
出力例 1
20
ピース i の色が色 A_i であるとします。はじめ、(A_1, A_2, A_3, A_4, A_5, A_6) = (0, 0, 0, 0, 0, 0) です。
(a, b, c) = (2, 1, 4) として操作を行うと (A_1, A_2, A_3, A_4, A_5, A_6) = (0, 4, 0, 0, 0, 0) となります。
(a, b, c) = (3, 3, 2) として操作を行うと (A_1, A_2, A_3, A_4, A_5, A_6) = (0, 4, 2, 2, 2, 0) となります。
(a, b, c) = (1, 1, 1) として操作を行うと (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 4, 2, 2, 2, 0) となります。
(a, b, c) = (4, 1, 1) として操作を行うと (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 4, 2, 1, 2, 0) となります。
(a, b, c) = (6, 1, 5) として操作を行うと (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 4, 2, 1, 2, 5) となります。
このとき、コストの合計は 5 + 5 + 2 + 2 + 6 = 20 となります。
入力例 2
5 1 2 3 4 5 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 2
5000000005
入力例 3
8 2 3 3 1 2 1 3 1 3 4 1 2 5 3 1 2
出力例 3
23
Score : 550 points
Problem Statement
There is a circular cake that has been cut into N equal slices by its radii.
Each piece is labeled with an integer from 1 to N in clockwise order, and for each integer i with 1 \leq i \leq N, the piece i is also referred to as piece N + i.
Initially, every piece’s color is color 0.
You can perform the following operation any number of times:
- Choose integers a, b, and c such that 1 \leq a, b, c \leq N. For each integer i with 0 \leq i < b, change the color of piece a + i to color c. The cost of this operation is b + X_c.
You want each piece i (for 1 \leq i \leq N) to have color C_i. Find the minimum total cost of operations needed to achieve this.
Constraints
- 1 \leq N \leq 400
- 1 \leq C_i \leq N
- 1 \leq X_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N C_1 C_2 \ldots C_N X_1 X_2 \ldots X_N
Output
Print the answer.
Sample Input 1
6 1 4 2 1 2 5 1 2 3 4 5 6
Sample Output 1
20
Let A_i denote the color of piece i. Initially, (A_1, A_2, A_3, A_4, A_5, A_6) = (0, 0, 0, 0, 0, 0).
Performing an operation with (a, b, c) = (2, 1, 4) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (0, 4, 0, 0, 0, 0).
Performing an operation with (a, b, c) = (3, 3, 2) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (0, 4, 2, 2, 2, 0).
Performing an operation with (a, b, c) = (1, 1, 1) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 2, 2, 0).
Performing an operation with (a, b, c) = (4, 1, 1) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 1, 2, 0).
Performing an operation with (a, b, c) = (6, 1, 5) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 1, 2, 5).
In this case, the total cost is 5 + 5 + 2 + 2 + 6 = 20.
Sample Input 2
5 1 2 3 4 5 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 2
5000000005
Sample Input 3
8 2 3 3 1 2 1 3 1 3 4 1 2 5 3 1 2
Sample Output 3
23