시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2.3 초 | 64 MB | 27 | 3 | 3 | 21.429% |
The mythic world of Chess Land is a rectangular grid of squares with R rows and C columns, R being greater than or equal to C. Its rows and columns are numbered from 1 to R and 1 to C, respectively.
The inhabitants of Chess Land are usually mentioned as pieces in everyday language, and there are 5 specific types of them roaming the land: pawns, rooks, bishops, queens and kings. Contrary to popular belief, chivalry is long dead in Chess Land, so there are no knights to be found.
Each piece is unique in the way it moves around from square to square: in one step,
In the following figure, we marked by X the squares each piece can move to in a single step (here, the rows are numbered from bottom to top, and the columns from left to right).
Recently, Chess Land has become a dangerous place: pieces that are passing through the land can get captured unexpectedly by unknown forces and simply disappear. As a consequence, they would like to reach their destinations as fast (i.e. in as few moves) as possible, and they are also interested in the number of different ways it is possible for them to reach it, using the minimal number of steps – because more paths being available could mean lower chances of getting captured. Two paths are considered different if they differ in at least one visited square.
For this problem, let us assume that pieces are entering Chess Land in a given column of row 1, and exit the land in a given column of row R. Your task is to answer Q questions: given the type of a piece, the column it enters row 1 and the column it must reach in row R in order to exit, compute the minimal number of moves it has to make in Chess Land, and the number of different ways it is able to do so.
The first line contains three space separated integers R, C and Q, the number of rows and columns of Chess Land, and the number of questions, respectively. Then Q lines follow.
Each line consists of
You have to print Q lines, the i-th one containing two space separated integers, the answer to the i-th question: the first one is the minimal number of steps needed, the second is the number of different paths available using this number of steps. Since the answer can be quite large, you have to compute it modulo 109 + 7, using the library functions provided by the grader.
If it is impossible to reach the target square, output the line “0 0”.
번호 | 배점 | 제한 |
---|---|---|
1 | 8 | T ∈ {‘P’, ‘R’, ‘Q’}, i.e. all pieces are pawns, rooks or queens |
2 | 15 | T = ‘B’ and C, R ≤ 100 |
3 | 22 | T = ‘B’ |
4 | 5 | T = ‘K’ and C, R ≤ 100 and Q ≤ 50 |
5 | 8 | T = ‘K’ and C, R ≤ 100 |
6 | 15 | T = ‘K’ and C ≤ 100 |
7 | 20 | T = ‘K’ |
8 | 7 | No additional constraints |
8 8 5 P 1 2 R 4 8 Q 2 3 B 3 6 K 5 5
0 0 2 2 2 5 2 2 7 393