| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 410493 | dolphingarlic | Chess Rush (CEOI20_chessrush) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
CEOI 2020 Chessrush
- Pawns
- There's only either 0 or 1 possible fixed-length paths
- O(1)
- Rooks
- If the start and end columns are equal, there's 1 path of length 1
- Otherwise, there are 2 paths of length 2
- O(1)
- Queens
- If the start and end columns or diagonals are equal, there's
1 path of length 1
- Otherwise, there are at least 4 paths of length 2
- If the start or end column is at an extremity and the board is
square, add a path
- If the start and end squares are the same colour and the queen
can travel on two diagonals to reach the end, add a path
- O(1)
- Bishops
- If the start and end squares are the same colour, then there's at
least 1 path
- dp[i][j][dir] = (Shortest path, No. of such paths)
= combine(dp[i - 1][j - 1][left] + 1,
dp[i - 1][j - 1][right],
dp[i - 1][j + 1][left],
dp[i - 1][j + 1][right] + 1)
- TODO: Optimize
- Kings
- There's always at least 1 fixed-length path
- dp[i][j] = Ways to reach cell (i, j)
= dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1]
- TOOD: Optimize
*/
#include <bits/stdc++.h>
#include "arithmetics.h"
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
int modpow(int base, int exp, int modulus = MOD) {
base %= modulus;
int result = 1;
while (exp > 0) {
if (exp & 1) result = (1ll * result * base) % modulus;
base = (1ll * base * base) % modulus;
exp >>= 1;
}
return result;
}
pair<int, int> solve_bishop(int x, int y, int r, int c) {
// Assume we always start moving left
// Get min moves and "buffer"
// Contribution = moves^buffer
int moves = 1 + (r - x) / (2 * c - 1) * 2;
if (r == c && x == c && y == 1) moves--;
int rem = (r - x) % (2 * c - 1) + 1;
int ways;
if (rem <= y) {
moves++;
ways = modpow(moves, y - rem);
} else {
moves += 2;
ways = modpow(moves, rem - y);
}
return {moves, ways};
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int r, c, q;
cin >> r >> c >> q;
while (q--) {
char p;
int x, y;
cin >> p >> x >> y;
switch (p) {
case 'P':
if (x == y)
cout << r - 1 << " 1\n";
else
cout << "0 0\n";
break;
case 'R':
if (x == y)
cout << "1 1\n";
else
cout << "2 2\n";
break;
case 'Q':
if (x == y || x + r - 1 == y || x - r + 1 == y)
cout << "1 1\n";
else {
int ways = 4;
// Extremities
if (r == c && (y == 1 || y == r || x == 1 || x == r))
ways++;
if (x + y + r & 1) {
// Double diagonal
if (r - x < y) ways++;
if (r - c + x - 1 < c - y + 1) ways++;
}
cout << "2 " << ways << '\n';
}
break;
case 'B':
if (x + y + r & 1) {
pair<int, int> move_left = solve_bishop(x, y, r, c);
pair<int, int> move_right =
solve_bishop(c - x + 1, c - y + 1, r, c);
if (move_left.first > move_right.first)
move_left = move_right;
else if (move_left.first == move_right.first) {
move_left.second += move_right.second;
if (move_left.second >= MOD) move_left.second -= MOD;
}
cout << move_left.first << ' ' << move_left.second << '\n';
} else
cout << "0 0\n";
break;
case 'K':
// Not yet implemented
cout << "NYI\n";
break;
}
}
return 0;
}