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
配点 : 200 点
問題文
N 人の人がいます。N 人の人には人 1, 人 2,\dots, 人 N と番号がついています。
人 i(2 \le i \le N) の親は人 P_i です。ここで、P_i < i が保証されます。
人 1 が人 N の何代前か求めてください。
制約
- 2 \le N \le 50
- 1 \le P_i < i(2 \le i \le N)
- 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
N P_2 P_3 \dots P_N
出力
答えを整数として出力せよ。
入力例 1
3 1 2
出力例 1
2
人 2 は人 3 の親であるため、人 3 の 1 代前です。
人 1 は人 2 の親であるため、人 3 の 2 代前です。
よって解は 2 です。
入力例 2
10 1 2 3 4 5 6 7 8 9
出力例 2
9
Score : 200 points
Problem Statement
There are N people, called Person 1, Person 2, \ldots, Person N.
The parent of Person i (2 \le i \le N) is Person P_i. Here, it is guaranteed that P_i < i.
How many generations away from Person N is Person 1?
Constraints
- 2 \le N \le 50
- 1 \le P_i < i(2 \le i \le N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_2 P_3 \dots P_N
Output
Print the answer as a positive integer.
Sample Input 1
3 1 2
Sample Output 1
2
Person 2 is a parent of Person 3, and thus is one generation away from Person 3.
Person 1 is a parent of Person 2, and thus is two generations away from Person 3.
Therefore, the answer is 2.
Sample Input 2
10 1 2 3 4 5 6 7 8 9
Sample Output 2
9
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
正整数 N が与えられます。
N 以下の正整数であって回文立方数であるものの最大値を求めてください。
ただし、正整数 K は以下の 2 つの条件を満たすとき、またそのときに限り回文立方数であると定義します。
- ある正整数 x が存在し、x^3 = K を満たす。
- K を先頭に 0 をつけずに 10 進表記した文字列が回文となる。より厳密には、0 以上 9 以下の整数 A_0, A_1, \ldots, A_{L-2} および 1 以上 9 以下の整数 A_{L-1} を用いて K = \sum_{i = 0}^{L-1} A_i10^i と表記したときに i = 0, 1, \ldots, L-1 に対して A_i = A_{L-1-i} を満たす。
制約
- N は 10^{18} 以下の正整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
345
出力例 1
343
343 は回文立方数であり、344, 345 は回文立方数ではありません。したがって、343 が答えとなります。
入力例 2
6
出力例 2
1
入力例 3
123456789012345
出力例 3
1334996994331
Score: 250 points
Problem Statement
You are given a positive integer N.
Find the maximum value of a palindromic cube number not greater than N.
Here, a positive integer K is defined to be a palindromic cube number if and only if it satisfies the following two conditions:
- There is a positive integer x such that x^3 = K.
- The decimal representation of K without leading zeros is a palindrome. More precisely, if K is represented as K = \sum_{i = 0}^{L-1} A_i10^i using integers A_0, A_1, \ldots, A_{L-2} between 0 and 9, inclusive, and an integer A_{L-1} between 1 and 9, inclusive, then A_i = A_{L-1-i} for all i = 0, 1, \ldots, L-1.
Constraints
- N is a positive integer not greater than 10^{18}.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
345
Sample Output 1
343
343 is a palindromic cube number, while 344 and 345 are not. Thus, the answer is 343.
Sample Input 2
6
Sample Output 2
1
Sample Input 3
123456789012345
Sample Output 3
1334996994331
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正整数 N,Q と、長さ N の英小文字からなる文字列 S が与えられます。
以下で説明されるクエリを Q 個処理してください。クエリは次の 2 種類のいずれかです。
1 x: 「S の末尾の文字を削除し、先頭に挿入する」という操作を x 回連続で行う。2 x: S の x 番目の文字を出力する。
制約
- 2 \le N \le 5 \times 10^5
- 1 \le Q \le 5 \times 10^5
- 1 \le x \le N
- |S|=N
- S は英小文字からなる。
2 xの形式のクエリが 1 個以上与えられる。- N,Q,x はすべて整数。
入力
入力は以下の形式で標準入力から与えられる。
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
それぞれのクエリは以下の形式で与えられる。ここで、t は 1 または 2 である。
t x
出力
2 x の形式の各クエリについて、答えを一行に出力せよ。
入力例 1
3 3 abc 2 2 1 1 2 2
出力例 1
b a
1 個目のクエリのとき、S は abc なので 2 文字目の b を出力します。
2 個目のクエリのとき、S は abc から cab に変わります。
3 個目のクエリのとき、S は cab なので 2 文字目の a を出力します。
入力例 2
10 8 dsuccxulnl 2 4 2 7 1 2 2 7 1 1 1 2 1 3 2 5
出力例 2
c u c u
Score : 300 points
Problem Statement
You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.
Process Q queries. Each query is of one of the following two types.
1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.2 x: Print the x-th character of S.
Constraints
- 2 \le N \le 5 \times 10^5
- 1 \le Q \le 5 \times 10^5
- 1 \le x \le N
- |S|=N
- S consists of lowercase English letters.
- At least one query in the format
2 x. - N, Q, x are all integers.
Input
Input is given from Standard Input in the following format:
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is in the following format, where t is 1 or 2:
t x
Output
For each query in the format 2 x, print the answer in a single line.
Sample Input 1
3 3 abc 2 2 1 1 2 2
Sample Output 1
b a
In the 1-st query, S is abc, so the 2-nd character b should be printed.
In the 2-nd query, S is changed from abc to cab.
In the 3-rd query, S is cab, so the 2-nd character a should be printed.
Sample Input 2
10 8 dsuccxulnl 2 4 2 7 1 2 2 7 1 1 1 2 1 3 2 5
Sample Output 2
c u c u
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
縦 H 行、横 W 行の H \times W マスからなるグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と表します。
各マスの状態は文字 C_{i, j} で表され、C_{i, j} = . ならばマス (i, j) は空きマスであり、C_{i, j} = # ならばマス (i, j) は壁です。
高橋君がグリッド上を歩こうとしています。彼がマス (i, j) にいるとき、マス (i, j + 1) またはマス (i + 1, j) に移動することができます。ただし、グリッドの外に出るような移動や、壁のマスへの移動を行うことはできません。高橋君は、移動することのできるマスが無くなった時点で立ち止まります。
高橋君がマス (1, 1) から歩き始めるとき、彼が立ち止まるまでに通ることのできるマスは最大で何マスですか？
制約
- 1 \leq H, W \leq 100
- H, W は整数
- C_{i, j} =
.または C_{i, j} =#(1 \leq i \leq H, 1 \leq j \leq W) - C_{1, 1} =
.
入力
入力は以下の形式で標準入力から与えられる。
H W
C_{1, 1} \ldots C_{1, W}
\vdots
C_{H, 1} \ldots C_{H, W}
出力
答えを出力せよ。
入力例 1
3 4 .#.. ..#. ..##
出力例 1
4
例えば (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) と進むことで、4 マス通ることができます。
5 マス以上通ることはできないので、4 と出力します。
入力例 2
1 1 .
出力例 2
1
入力例 3
5 5 ..... ..... ..... ..... .....
出力例 3
9
Score : 400 points
Problem Statement
There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Each square is described by a character C_{i, j}, where C_{i, j} = . means (i, j) is an empty square, and C_{i, j} = # means (i, j) is a wall.
Takahashi is about to start walking in this grid. When he is on (i, j), he can go to (i, j + 1) or (i + 1, j). However, he cannot exit the grid or enter a wall square. He will stop when there is no more square to go to.
When starting on (1, 1), at most how many squares can Takahashi visit before he stops?
Constraints
- 1 \leq H, W \leq 100
- H and W are integers.
- C_{i, j} =
.or C_{i, j} =#. (1 \leq i \leq H, 1 \leq j \leq W) - C_{1, 1} =
.
Input
Input is given from Standard Input in the following format:
H W
C_{1, 1} \ldots C_{1, W}
\vdots
C_{H, 1} \ldots C_{H, W}
Output
Print the answer.
Sample Input 1
3 4 .#.. ..#. ..##
Sample Output 1
4
For example, by going (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2), he can visit 4 squares.
He cannot visit 5 or more squares, so we should print 4.
Sample Input 2
1 1 .
Sample Output 2
1
Sample Input 3
5 5 ..... ..... ..... ..... .....
Sample Output 3
9