글 읽기 - 반례좀 찾아주세요..

xodid0936 4년 전 0

테스트케이스들은 다 정확하게 돌아가는데

제출 누르면 바로 틀려버리네요.

혹시 반례나 문제점좀 알수있을까요?

#include <iostream>
#include <deque>
#include <vector>

#define endl '\n'

using namespace std;

deque<int> dq;
vector<deque<int>> v;

int N, M, T, tmp;
int all_sum = 0;
float all_ave = 0;
bool same_check = false; // DFS 돌때 같아서 들어온거면 0으로 바꿔주기 위함
bool samesame = false; // 전체 같은수 있는지 확인용

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

//반시계, 시계 도는 함수
void spin(int n, int dir, int k)
{
	if (!dir)
	{
		for (int i = 0; i < k; i++)
		{
			v[n].push_front(v[n].back());
			v[n].pop_back();
		}
	}
	else
	{
		for (int i = 0; i < k; i++)
		{
			v[n].push_back(v[n].front());
			v[n].pop_front();
		}
	}
}

// 근처에 같은 수 있는지 확인하는 함수
void check_near(int x, int y)
{
	if (v[x][y] == 0) return;

	for (int i = 0; i < 4; i++)
	{
		if (x + dx[i] == 0 || x + dx[i] > N)
			continue;
		int nx = x + dx[i];
		int ny;
		if (y + dy[i] == M) ny = 0;
		else if (y + dy[i] < 0) ny = M - 1;
		else
			ny = y + dy[i];

		if (v[x][y] == v[nx][ny])
		{
			samesame = true;
			same_check = true;
			v[x][y] = 0;
			check_near(nx, ny);
		}
	}

	if (same_check) v[x][y] = 0;
}

//같은수 없을경우 평균비교후 더하거나 빼는함수
void nosamesame()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (v[i][j] == 0) continue;

			if (v[i][j] < all_ave)
				v[i][j]++;
			else if (v[i][j] > all_ave)
				v[i][j]--;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	dq.push_back(0);
	v.push_back(dq);
	dq.clear();

	cin >> N >> M >> T;

	for (int i = 0; i < N; i++) // 입력
	{
		for (int j = 0; j < M; j++)
		{
			cin >> tmp;
			dq.push_back(tmp);
		}
		v.push_back(dq);
		dq.clear();
	}

	for (int i = 0; i < T; i++)
	{
		samesame = false;
		int x, d, k;
		cin >> x >> d >> k;
		for (int n = x; n <= N; n += x)
		{
			spin(n, d, k);
		}
		for (int k = 1; k <= N; k++)//1.0 부터 돌면서 같은수 있는지 체크
		{
			for (int j = 0; j < M; j++)
			{
				same_check = false;
				if (v[k][j] != 0)
					check_near(k, j);
			}
		}
		int count = 0;
		all_sum = 0;
		for (int k = 1; k <= N; k++)
		{
			for (int j = 0; j < M; j++)
			{
				if (v[k][j])
				{
					count++;
					all_sum += v[k][j];
				}
			}
		}
		if (count == 0) all_ave = 0; //제로디바이드 방지
		else
			all_ave = (float)all_sum / (float)count;

		if (!samesame) nosamesame();
	}

	cout << all_sum << endl;
	return 0;
}

pichulia 4년 전 1

62번째 줄은 없어야할거 같습니다. 4방향을 모두 봐야하는데 v[x][y]=0으로 만들어버리면 그 다음방향(?)이 같은 경우를 처리하지 못합니다.
평균이랑 비교할 때 float로 비교연산을 하고있는데... 평균이 정확히 4인 경우 점수가 4인 친구는 변화가 없어야할텐데 그런걸 잘 걸러내주는지 모르겠습니다. float형이기 때문에 생기는 실수오차는 믿음직스럽지 못하죠.

xodid0936 4년 전 0

@pichulia

1번은 처리했고

float 부분은 정상작동 했었습니다.!

제가 문제를 잘못읽고 마지막에 안움직이고 나서도 합해서 답을 내야하는걸 체크못했었습니다.!

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

문제

문제

출처

ICPC

반례좀 찾아주세요..

xodid0936 4년 전 0

pichulia 4년 전 1

xodid0936 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말