글 읽기 - 주어진 예제는 다 맞는데 제출하면 틀리네요... 반례가 있을까요..?

dvlpr 5년 전 0

주어진 예제 8개는 답이 잘 나오는데 왜 틀릴까요 ㅠㅠ 반례를 못찾겠습니다

입력시 y, x순서나 x, y순서는 시도해봤습니다. 역시나 답은 나오지만 제출시 틀렸다고 나옵니다...

map 3차원 배열은 1살부터 1010살까지 나이와 위치별로 나무의 수를 저장했습니다. map[0][y][x]는 x,y위치의 나무의 총 개수입니다

#include <iostream>
#include <queue>
#include <memory.h>

#define MAP 10
#define MAX 1011

using namespace std;

typedef struct qnode
{
	int old, x, y, n;
	qnode(int _old, int _x, int _y, int _n)
	{
		old = _old, x = _x, y = _y, n = _n;
	}
}qnode;

long map[MAX][MAP][MAP] = {0, };
int energy[MAP][MAP] = {0, };
int supply[MAP][MAP] = {0, };
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};

void init(void)
{
	memset(map, 0, sizeof(map));
}


bool isWall(int x, int y, int n)
{
	return (x<0 || y<0 || x>=n || y>=n);
}

void eat(int n)
{
	queue<qnode> q;
	for(int i=1; i<MAX; i++){					// i가 나이
		for(int y=0; y<n; y++){					// y위치
			for(int x=0; x<n; x++){				// x위치
				if(map[i][y][x]){				// 한 그루라도 있어야 진행
					if(energy[y][x] >= i*map[i][y][x]){			// 모든 나무가 양분을 먹을수 있을때
						energy[y][x] -= i*map[i][y][x];
						q.push(qnode(i+1, x, y, map[i][y][x]));
						map[i][y][x] = 0;
					}
					else{							// 양분을 먹지 못하는 나무가 한그루라도 있을때
						int alive = energy[y][x]/i;
						int die = map[i][y][x] - alive;
						energy[y][x] -= alive*i;
						q.push(qnode(i+1, x, y, alive));
						energy[y][x] += (i/2)*die;
						map[i][y][x] = 0;
						map[0][y][x] -= die;
					}
				}
			}
		}
	}
	while(!q.empty()){
		int old = q.front().old, x = q.front().x, y = q.front().y, add = q.front().n;	q.pop();
		map[old][y][x] += add;
	}
}

void spread(int n)
{
	for(int i=5; i<MAX; i+=5){
		for(int y=0; y<n; y++){
			for(int x=0; x<n; x++){
				if(int t = map[i][y][x]){
					for(int i=0; i<8; i++){
						int nx = x + dx[i];
						int ny = y + dy[i];
						if(!isWall(nx, ny, n)){			// 영역 내에서만 번식
							map[0][ny][nx] += t;
							map[1][ny][nx] += t;
						}
					}
				}
			}
		}
	}
}

void refill(int n)
{
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			energy[i][j] += supply[i][j];
		}
	}
}

int counting(int n)
{
	int res = 0;

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			res += map[0][i][j];
		}
	}

	return res;
}


void simulation(int n, int m, int k)
{
	for(int year=1; year<=k; year++){
		eat(n);				// 봄, 여름
		spread(n);			// 가을
		refill(n);			// 겨울
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("input.txt", "r", stdin);
	init();
	int n, m, k;
	cin >> n >> m >> k;
	for(int i=0; i<n; i++){			// 양분공급량, 초기양분
		for(int j=0; j<n; j++){
			cin >> supply[i][j];
			energy[i][j] = 5;
		}
	}
	for(int i=0; i<m; i++){
		int x, y, old;
		cin >> y >> x >> old;
		map[old][y-1][x-1]++;
		map[0][y-1][x-1]++;		// 0번째에 각 위치에 나무의 갯수 저장
	}
	simulation(n, m, k);
	int ans = counting(n);
	cout << ans << endl;

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

주어진 예제는 다 맞는데 제출하면 틀리네요... 반례가 있을까요..?

dvlpr 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말