글 읽기 - 반례 부탁드립니다.

sunny0602 1년 전 0

질문 게시판과 문제에서 제공된 예시들을 모두 성공했는데 어떤 반례로 인해 틀렸는지 궁금합니다. 혹시 반례 알고 계신 분이 계시다면 답변 부탁드립니다;

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	int count[10001] = { 0, };
	cin >> n >> m;
	long sum = (n * (n - 1) * (n - 2))/(3*2*1); // nC3(전체 경우의 수)
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		sum -= (n - 2); // 섞으면 안되는 경우의 수 빼기
		if (count[a] >= 1)
		{
			sum+= count[a]; // 2번 빼진 겹치는 경우의 수 더하기
		}
		if (count[b] >= 1)
		{
			sum+=count[b]; // 2번 빼진 겹치는 경우의 수 더하기
		}
		count[a]++;
		count[b]++;
	}
	cout << sum << '\n';
	
}

qudfbf2 1년 전 1

조합을 입력할 때 큰 숫자가 먼저 나오는 경우

반례 입력
5 3
5 1
5 2
1 2

예상 출력
3

실제 출력
4

sunny0602 1년 전 0

감사합니다!!

sunny0602 1년 전 0

정말 죄송한데 저 반례에 대해서는 수정이 되었는데 또 어디서 오류가 났는지 모르겠어서요ㅠㅠ

혹시 반례 더 찾아주실 수 있나요?

#include <iostream>

bool check[10001][10001];
int count[10001];

int main()
{
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	int n, m;
	std::cin >> n >> m;
	long sum = (n * (n - 1) * (n - 2)) / (3 * 2 * 1); // nC3
	for (int i = 0; i < m; i++)
	{
		int a, b;
		std::cin >> a >> b;
		check[a][b] = 1;
		check[b][a] = 1;
		sum -= (n - 2);
		if (count[a] >= 1)
		{
			sum += count[a];
		}
		if (count[b] >= 1)
		{
			sum += count[b];
		}
		if (count[a] >= 1 && count[b] >= 1)
		{
			for (int j = 0; j < 10001; j++)
			{
				if (j == a || j == b)
				{
					continue;
				}
				if ((check[a][j] == check[b][j])  && (check[b][j] == true))
				{
					sum -= 1;
					break;
				}
			}
		}
		count[a]++;
		count[b]++;

	}
	
	std::cout << sum << '\n';

}

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

문제

문제

출처

ICPC

반례 부탁드립니다.

sunny0602 1년 전 0

qudfbf2 1년 전 1

sunny0602 1년 전 0

sunny0602 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말