글 읽기 - 1033 반례 부탁드립니다 :)

kjh31021 1년 전 0

모든 case 만족하고 질문글에 있는 아래 case도 문제없이 출력이 잘 되는데 틀렸습니다. 라고 뜹니다. 무엇이 문제인지 잘 모르겠어서 도움 부탁드립니다:)

input
10
4 0 1 1
4 1 3 1
4 2 5 1
4 3 7 1
3 5 1 9
3 6 8 2
5 7 2 1
7 8 5 8
5 9 1 6

output
420 140 84 60 420 540 15 270 432 3240

#include <stdio.h>

int n, A[10], B[10], P[10], Q[10];
long long amount[11];	// 칵테일의 각 질량 

int min(int a, int b);				// 더 작은 값을 return 하는 함수 
long long gcd(int a, int b);		// 두 수의 최대공약수를 return 하는 함수 
long long lcm(int a, int b);		// 두 수의 최소공배수를 return 하는 함수
// amount배열에 각 칵테일의 질량을 넣어주는 함수 
void input(int a, int b, int p, int q, int num);

int main(void) {
	scanf("%d", &n);
	for(int i=0;i<n-1;i++)
		scanf("%d %d %d %d", &A[i], &B[i], &P[i], &Q[i]);
	
	for(int i=0;i<n-1;i++)
		input(A[i], B[i], P[i], Q[i], i);
		
	// 칵테일 종류가 1개인 경우 예외처리 
	if(n==1)
		amount[0] = 1;
		
    // 마지막으로 한번 더 최대공약수가 1이 아닌지 확인해본다. 
    // (모든 case에서 GCD가 1이 나왔습니다. 그래도 계속 틀렸길래 혹시나 해서...)
	long long GCD = amount[0];
	for(int i=1;i<n;i++)
		GCD = gcd(GCD, amount[i]);
		
	for(int i=0;i<n;i++)
		printf("%lld ", amount[i]/GCD);
		
	return 0;
}

int min(int a, int b) {
	if(a<b)	return a;
	else	return b;
}

long long gcd(int a, int b) {
	long long GCD = 1;
	for(long long i=2;i<=min(a, b);i++)
		if(a%i == 0 && b%i == 0)
			GCD = i;
	
	return GCD;
}

long long lcm(int a, int b) {
	return a*b/gcd(a,b);
}

void input(int a, int b, int p, int q, int num) {	
	long long multi, GCD;
	GCD = gcd(p, q);
	// p/q를 기약분수로 바꾸어준다 
	p = p/GCD;
	q = q/GCD;
		
	// a, b번째 칵테일에 대한 정보가 처음 나왔을 때, 그대로 대입한다. 
	if(!amount[a] && !amount[b]) {
		amount[a] = p;
		amount[b] = q;
	}
	 
	else if(!amount[b]) {
		multi = p/gcd(amount[a], p);
		for(int i=0;i<n;i++)
			amount[i] *= multi;
		amount[b] = amount[a]*q/p;
	}
	
	else if(!amount[a]) {
		multi = q/gcd(amount[b], q);
		for(int i=0;i<n;i++)
			amount[i] *= multi;
		amount[a] = amount[b]*p/q;
	}
	
	else {
		for(int i=0;i<n;i++)
			if(i != a && i!= b)
				amount[i] = 0;
				
		multi = lcm(p, amount[b])/gcd(amount[a], lcm(p, amount[b]));
		amount[a] *= multi;
		amount[b] = amount[a]/p*q;
		
		for(int i=0;i<num;i++)
			input(A[i], B[i], P[i], Q[i], i);
	}
	
	return;
}

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

문제

문제

출처

ICPC

1033 반례 부탁드립니다 :)

kjh31021 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말