2332 Robot
unknown
plain_text
a year ago
14 kB
4
Indexable
Order Function Return
1 init(6,
{{1, 2, 1, 5, 5, 5},
{3, 1, 3, 1, 1, 5},
{1, 4, 5, 5, 5, 5},
{2, 1, 1, 1, 4, 5},
{1, 4, 5, 5, 5, 5},
{3, 2, 3, 4, 1, 2}})
2 numberOfCandidate(3, {4, 3, 4}) 2
3 maxBlockedRobots(5, {1, 5, 1, 3, 5}, 0) 17
4 numberOfCandidate(3, {1, 1, 1}) 9
5 maxBlockedRobots (3, {5, 2, 3}, 1) 19
6 maxBlockedRobots (2, {1, 4}, 2) 25
7 numberOfCandidate(2, {5, 2}) 8
8 numberOfCandidate(5, {2, 5, 5, 5, 4}) 1
9 numberOfCandidate(5, {1, 2, 1, 2, 1}) 0
10 maxBlockedRobots(2, {1, 4}, 3) 14
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#define MAX_N 20
extern void init(int N, int mMap[MAX_N][MAX_N]);
extern int numberOfCandidate(int M, int mStructure[]);
extern int maxBlockedRobots(int M, int mStructure[], int mDir);
#define CMD_INIT 100
#define CMD_CANDI 200
#define CMD_BLOCKED 300
static bool run()
{
int query_num;
scanf("%d", &query_num);
int ans;
bool ok = false;
for (int q = 0; q < query_num; q++)
{
int query;
scanf("%d", &query);
if (query == CMD_INIT)
{
int N;
int mMap[MAX_N][MAX_N];
scanf("%d", &N);
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
scanf("%d", &mMap[i][j]);
}
}
init(N, mMap);
ok = true;
}
else if (query == CMD_CANDI)
{
int M;
int mStructure[5];
scanf("%d", &M);
for (int i = 0; i < M; i++){
scanf("%d", &mStructure[i]);
}
int ret = numberOfCandidate(M, mStructure);
scanf("%d", &ans);
if (ans != ret)
{
ok = false;
}
}
else if (query == CMD_BLOCKED)
{
int M;
int mStructure[5];
int mDir;
scanf("%d", &M);
for (int i = 0; i < M; i++){
scanf("%d", &mStructure[i]);
}
scanf("%d", &mDir);
int ret = maxBlockedRobots(M, mStructure, mDir);
scanf("%d", &ans);
if (ans != ret)
{
ok = false;
}
}
}
return ok;
}
int main()
{
setbuf(stdout, NULL);
// freopen("sample_input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; tc++)
{
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
#define MAX_N 20
void init(int N, int mMap[MAX_N][MAX_N])
{
}
int numberOfCandidate(int M, int mStructure[])
{
Return the number of outcomes for building one structure, mStructure.
As for the areas where the structure is built, if all of the areas are same, this means the same outcome.
If at least one area is different, this means different outcomes.
mStructure has the size of 1 x M and consists of square-shaped parts with the size of 1 x 1.
The height of each part is as below.
Return 0, if there are no areas to build the structure.
Parameters
M : the size of the structure (2 ≤ M ≤ 5)
mStructure : the height of each part of the structure (1 ≤ mStructure[] ≤ 5)
Returns
the number of outcomes for building a structure
}
int maxBlockedRobots(int M, int mStructure[], int mDir)
{
Find the location to build one structure, mStructure, to maximize the number of locations of robots unable to reach the promised direction, mDir, and return the maximum number.
The promised direction, mDir, is given as one of the followings.
0: the north, 1: the east, 2: the south, 3: the west
It is guaranteed that there is at least one place to build the given structure.
After the structure is built, robots are dropped. Robots are also dropped to the locations where the structure is built. When finding the return value, the case where robots are dropped in absence of a structure is never considered.
The structure mStructure has the size of 1 x M, and consists of square-shaped parts with the size of 1 x 1. The height of each part is as below.
Parameters
M : the size of the structure (2 ≤ M ≤ 5)
mStructure : the height of each part of the structure (1 ≤ mStructure[] ≤ 5)
mDir : the promised direction (0: the north, 1: the east, 2: the south, 3: the west)
Returns
the maximum number of locations making it impossible for robots to reach the promised direction
}
25 100
10
100 6
1 2 1 5 5 5
3 1 3 1 1 5
1 4 5 5 5 5
2 1 1 1 4 5
1 4 5 5 5 5
3 2 3 4 1 2
200 3 4 3 4 2
300 5 1 5 1 3 5 0 17
200 3 1 1 1 9
300 3 5 2 3 1 19
300 2 1 4 2 25
200 2 5 2 8
200 5 2 5 5 5 4 1
200 5 1 2 1 2 1 0
300 2 1 4 3 14
16
100 6
4 1 2 2 3 1
2 2 3 2 2 5
2 3 2 2 1 3
2 2 1 2 2 2
1 1 5 1 3 1
3 5 2 1 2 3
200 3 2 2 1 5
200 3 3 3 2 5
200 3 3 2 3 5
200 3 3 4 3 3
300 3 3 3 3 3 25
300 4 3 4 5 1 2 13
300 2 1 4 0 18
200 3 3 3 4 6
300 3 1 5 4 2 13
200 3 5 1 3 1
300 2 2 2 0 22
200 4 4 3 1 5 1
200 3 4 3 4 5
200 2 5 4 28
200 3 1 2 3 7
16
100 6
2 3 2 1 1 3
1 5 1 3 1 1
3 2 3 1 2 1
1 1 3 1 1 1
1 2 3 1 3 5
4 2 3 1 3 3
200 2 4 3 16
200 3 5 3 1 1
300 4 1 3 2 3 2 17
200 4 3 4 2 3 1
200 5 2 1 3 1 1 1
200 2 3 1 21
200 2 1 3 21
300 5 5 3 5 5 5 0 19
300 3 4 5 4 3 25
300 3 1 1 3 0 19
200 2 2 4 21
200 2 3 2 16
200 2 1 5 3
300 4 2 2 2 2 1 11
200 2 3 5 21
41
100 6
3 2 3 3 1 3
1 1 2 3 4 3
1 3 2 2 2 3
2 5 3 2 1 1
3 1 4 2 3 3
1 3 4 1 1 3
200 3 5 4 5 1
300 3 4 2 2 3 6
200 4 2 3 4 3 0
300 4 4 1 3 4 2 21
200 5 1 2 3 3 2 1
200 3 1 2 3 5
200 2 5 1 1
200 3 1 3 2 3
300 4 1 1 3 1 0 29
200 3 2 2 3 5
300 3 5 5 5 0 26
200 3 1 5 3 1
300 3 3 5 4 2 25
200 2 4 1 4
300 4 5 4 2 5 2 21
200 3 2 2 4 3
200 3 2 4 2 2
300 3 4 4 2 0 26
300 4 4 4 3 2 3 26
200 3 2 4 4 2
200 4 2 2 1 1 1
300 2 2 2 3 25
200 2 1 2 21
300 3 4 2 5 1 13
300 2 4 2 3 25
300 3 3 1 2 0 26
300 2 1 4 1 13
300 4 2 3 4 4 2 20
300 3 2 2 4 0 27
300 3 1 2 2 2 21
300 3 4 2 5 2 24
200 3 2 3 2 1
300 3 1 3 2 1 26
300 3 2 1 3 1 13
200 3 4 1 2 1
200 3 1 5 3 1
200 2 5 1 1
300 3 5 5 3 1 11
200 2 1 3 18
200 4 3 2 5 5 1
41
100 6
2 1 1 5 2 4
1 1 3 3 3 1
1 1 3 2 1 3
1 3 2 3 3 1
3 5 2 3 2 2
2 1 3 3 2 1
200 4 2 1 3 1 2
200 3 2 5 4 1
200 4 4 5 5 4 1
200 2 5 2 3
300 4 4 3 3 5 2 23
200 3 3 5 2 2
200 3 3 3 5 5
200 2 2 4 18
300 3 4 3 2 3 19
200 2 4 2 18
200 3 5 3 4 5
200 3 2 2 4 5
300 3 2 5 3 0 18
300 4 3 5 5 5 2 20
200 4 1 3 4 3 1
300 3 4 2 3 1 19
200 5 5 3 3 4 4 1
200 3 2 1 1 4
300 3 2 2 3 2 23
300 2 5 5 2 23
200 3 3 3 2 6
300 3 1 3 2 2 24
300 3 2 3 1 1 18
300 4 4 2 2 2 0 26
300 4 1 1 1 3 3 21
200 2 3 5 18
300 3 3 5 4 2 25
200 2 1 5 2
200 2 1 4 3
300 2 3 2 0 26
200 2 1 5 2
300 3 3 3 1 1 18
300 2 1 2 2 25
200 2 4 3 20
300 2 3 5 3 24
300 2 1 5 3 19
300 4 3 2 4 4 1 18
300 3 2 4 1 0 18
200 4 1 3 5 5 1
300 2 4 3 2 25
41
100 6
2 3 2 3 3 3
3 3 4 2 3 3
5 1 1 2 3 1
2 3 1 3 3 3
3 5 1 1 2 1
1 3 1 1 1 1
200 3 1 5 5 2
200 3 5 3 3 3
300 3 5 3 4 1 13
300 2 4 3 3 27
300 3 2 1 2 3 24
200 4 4 2 4 2 1
200 4 4 4 2 4 2
200 4 1 5 5 4 2
200 3 4 4 2 3
300 2 5 1 3 23
300 3 3 5 5 1 24
300 2 1 1 3 24
300 3 1 2 3 0 21
200 5 1 1 3 1 3 1
300 2 3 5 0 22
300 3 3 1 4 1 11
200 2 4 2 18
200 3 4 3 2 2
300 4 1 1 3 1 1 14
200 2 5 1 2
300 3 1 2 2 2 15
200 3 4 4 1 1
300 2 5 1 3 23
300 3 2 1 2 2 4
300 4 1 1 1 2 2 4
200 2 5 5 22
200 4 3 3 1 3 2
200 3 1 3 1 3
300 2 5 1 3 23
300 3 5 5 1 0 18
200 2 4 1 2
200 2 3 5 18
200 2 4 2 18
300 3 4 2 4 1 5
200 4 3 2 2 2 2
200 3 4 2 4 3
200 2 1 4 2
300 2 1 5 1 16
300 3 2 4 2 1 14
300 4 1 1 3 1 3 24
41
100 6
2 2 1 2 1 3
2 2 1 1 3 1
1 1 2 3 1 3
3 5 3 3 3 2
2 1 2 2 5 2
4 4 5 1 3 3
300 3 5 3 5 1 26
200 4 1 4 4 5 1
300 3 2 2 3 2 26
300 4 3 4 3 3 1 22
200 3 4 4 5 7
200 4 2 3 3 2 1
200 2 3 3 14
300 3 5 4 5 2 22
200 5 3 4 1 4 1 0
200 2 2 3 21
200 3 1 5 4 1
200 4 2 4 2 4 1
200 4 3 5 1 2 1
300 3 2 1 1 3 27
200 4 2 4 3 3 1
200 3 2 2 3 7
300 3 2 1 3 1 28
300 2 5 1 0 18
300 2 1 5 3 24
200 3 5 2 5 1
300 2 1 5 3 24
200 3 3 5 1 1
300 4 1 2 3 3 1 19
300 3 4 2 4 1 26
300 3 1 2 3 3 22
200 3 2 1 5 1
300 2 4 4 3 24
200 4 2 4 3 3 1
300 4 2 4 2 3 3 20
200 3 5 1 5 1
300 2 3 5 3 26
200 2 2 4 18
300 3 3 1 2 0 22
300 2 3 5 2 30
300 3 3 4 3 3 16
300 3 3 1 2 3 25
300 4 5 5 4 3 0 24
200 2 5 1 3
200 2 3 5 18
200 4 3 5 5 5 1
41
100 6
4 2 5 1 2 3
2 3 2 3 1 1
2 2 1 1 2 2
1 4 1 3 2 2
3 2 1 1 2 3
3 2 2 1 2 4
200 5 4 2 3 2 3 1
200 4 1 5 4 3 1
200 4 2 2 1 1 2
200 4 5 4 4 3 2
200 3 3 1 1 1
300 3 1 1 2 1 30
200 3 2 1 1 6
300 3 3 2 2 1 30
300 4 1 2 2 2 0 28
200 3 1 5 4 1
200 4 3 5 4 5 1
200 3 4 5 4 3
200 3 3 3 2 9
300 3 2 2 1 0 28
300 3 1 4 2 1 22
300 4 4 4 3 3 0 24
300 3 3 5 4 1 25
200 2 5 1 1
300 3 2 4 1 3 25
300 3 5 3 4 3 24
200 3 1 4 2 2
200 3 2 3 4 4
300 5 3 4 5 5 4 2 25
300 4 2 3 3 3 1 17
200 3 1 1 3 1
200 3 3 1 2 2
300 3 5 5 3 3 29
300 4 5 5 4 4 2 15
200 3 4 4 2 4
300 4 3 4 4 3 1 20
300 3 5 3 4 3 24
300 4 4 5 5 4 1 20
300 3 2 3 4 1 22
300 3 2 4 4 2 19
200 3 1 5 4 1
200 3 3 2 1 4
300 5 3 4 4 3 2 2 25
200 2 1 2 25
200 3 4 3 3 6
300 4 1 2 1 1 2 29
#include <queue>
#include <vector>
#include <climits>
using namespace std;
#define MAX_N 20
#define MAX_D 10
#define pii pair<int, int>
const int off = 5;
const int dr[4] = { 0, 1, -1, 0 };
const int dc[4] = { 1, 0, 0, -1 };
int n, visited;
int grid[MAX_N][MAX_N];
int visit[MAX_N][MAX_N];
vector<pair<pii, int>> diff[MAX_D][MAX_D][MAX_D][MAX_D];
void init(int N, int mMap[MAX_N][MAX_N])
{
n = N;
visited = 1;
for (int i = 0; i < MAX_D; ++i)
for (int j = 0; j < MAX_D; ++j)
for (int k = 0; k < MAX_D; ++k)
for (int l = 0; l < MAX_D; ++l)
diff[i][j][k][l].clear();
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
grid[r][c] = mMap[r][c];
visit[r][c] = 0;
}
}
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
for (int k = 0; k < 4; ++k) {
int currDiff[4] = { -5, -5, -5, -5 };
int prev = grid[r][c];
for (int l = 1; l < 5; ++l) {
int newR = r + dr[k] * l, newC = c + dc[k] * l;
if (newR < 0 || newR >= N) break;
if (newC < 0 || newC >= N) break;
currDiff[l - 1] = grid[newR][newC] - prev;
prev = grid[newR][newC];
int idx0 = currDiff[0] + off;
int idx1 = currDiff[1] + off;
int idx2 = currDiff[2] + off;
int idx3 = currDiff[3] + off;
diff[idx0][idx1][idx2][idx3].push_back({ { r, c }, k });
}
}
}
}
}
int numberOfCandidate(int M, int mStructure[])
{
bool isPalindrome = true;
for (int i = 0; i < M / 2; ++i) {
if (mStructure[i] != mStructure[M - 1 - i]) {
isPalindrome = false;
break;
}
}
int currDiff[4] = { -5, -5, -5, -5 };
for (int i = 1; i < M; ++i)
currDiff[i - 1] = mStructure[i - 1] - mStructure[i];
int idx0 = currDiff[0] + off;
int idx1 = currDiff[1] + off;
int idx2 = currDiff[2] + off;
int idx3 = currDiff[3] + off;
int total = diff[idx0][idx1][idx2][idx3].size();
return !isPalindrome ? total : total / 2;
}
int getRobotPass(int mDir) {
queue<pii> q;
if (mDir == 0)
for (int j = 0; j < n; ++j) {
q.push({ 0, j });
visit[0][j] = visited;
}
else if (mDir == 1)
for (int i = 0; i < n; ++i) {
q.push({ i, n - 1 });
visit[i][n - 1] = visited;
}
else if (mDir == 2)
for (int j = 0; j < n; ++j) {
q.push({ n - 1, j });
visit[n - 1][j] = visited;
}
else
for (int i = 0; i < n; ++i) {
q.push({ i, 0 });
visit[i][0] = visited;
}
int cnt = 0;
while (!q.empty()) {
pii el = q.front();
q.pop();
int currR = el.first, currC = el.second;
for (int i = 0; i < 4; ++i) {
int newR = currR + dr[i], newC = currC + dc[i];
if (newR < 0 || newR >= n) continue;
if (newC < 0 || newC >= n) continue;
if (visit[newR][newC] == visited) continue;
if (grid[newR][newC] < grid[currR][currC]) continue;
q.push({ newR, newC });
visit[newR][newC] = visited;
cnt++;
}
}
visited++;
return cnt;
}
int maxBlockedRobots(int M, int mStructure[], int mDir)
{
int currDiff[4] = { -5, -5, -5, -5 };
for (int l = 1; l < M; ++l)
currDiff[l - 1] = mStructure[l - 1] - mStructure[l];
int idx0 = currDiff[0] + off;
int idx1 = currDiff[1] + off;
int idx2 = currDiff[2] + off;
int idx3 = currDiff[3] + off;
vector<pair<pii, int>> v = diff[idx0][idx1][idx2][idx3];
int minRobotPass = INT_MAX;
for (pair<pii, int> const& el : v) {
int r = el.first.first, c = el.first.second, k = el.second;
for (int l = 0; l < M; ++l) {
int newR = r + dr[k] * l, newC = c + dc[k] * l;
grid[newR][newC] += mStructure[l];
}
minRobotPass = min(minRobotPass, getRobotPass(mDir));
for (int l = 0; l < M; ++l) {
int newR = r + dr[k] * l, newC = c + dc[k] * l;
grid[newR][newC] -= mStructure[l];
}
}
return (n * n) - (n + minRobotPass);
}Editor is loading...
Leave a Comment