글 읽기 - 헨리문제 반례를 모르겠습니다...

gkfkagkfka12 6년 전 0

예제 다 맞고 제가 다른 것들도 테스트 해보면서 계산해 봤는데 반례를 모르겠습니다.

1%도 못 가고 틀리는데 어디가 문제일까요...ㅠㅠ 질문도 별로 없어서 못찾았습니다...

#include <iostream>

long long inputFraction[2];
long long unitFraction[2];

long long LCM(long long a, long long b)
{
	if (a < b) std::swap(a, b);
	long long temp_a = a;
	long long temp_b = b;
	while (b) {
		long long temp = a;
		a = b;
		b = temp % b;
	}

	return (temp_a*temp_b) / a;
}

long long henryRepresentation()
{
	long long unitN = unitFraction[0], unitD = unitFraction[1]; // 단위분수의 분자,분모
	long long inputN = inputFraction[0], inputD = inputFraction[1]; // 입력분수의 분자,분모
	long long ans;

	while (inputFraction[0]) {
		unitFraction[1]=inputFraction[1]=LCM(unitD, inputD); // 분모를 최소공배수로 통분

		// 통분한 것에 대해 분자도 맞춰준다.0
		unitFraction[0] = unitN * unitFraction[1] / unitD;
		inputFraction[0] = inputN * inputFraction[1] / inputD;

		// 단위분수의 분자가 입력분수의 분자보다 작거나 같으면 빼주고 다시 처음부터 시작
		if (unitFraction[0] <= inputFraction[0]) {
			inputFraction[0] -= unitFraction[0];
			inputN = inputFraction[0]; inputD = inputFraction[1];
			ans = inputFraction[1];
			if (inputN) unitD = inputD / inputN;
			else unitD++;
		}
		// 아니면 분모만 계속 증가시킨다.
		else unitD++;
		// 단위분수의 분자는 항상 1이기 때문에 초기화
		unitN = 1;
	}
	return ans;
}

int main(void)
{
	long long tc; std::cin >> tc;

	while (tc--) {
		unitFraction[0] = 1; // 단위분수의 분자는 1
		unitFraction[1] = 2; // 단위분수의 분모시작은 2
		std::cin >> inputFraction[0] >> inputFraction[1];
		std::cout << henryRepresentation() << '\n';
	}
	return 0;
}

cbs0615 6년 전 0

일단은 제가 무작정 넣어서 찾은 반례로

9999 10000 =>

30371235615000

(9999와 10000은 서로소)

gkfkagkfka12 6년 전 1

답이 3037~라는 건가요?

cbs0615 6년 전 0

일단은 오버플로우 문제인듯 싶습니다.

LCM 함수에서

return temp_a*(temp_b / a);

로 고치니 답이 바뀌네요..

gkfkagkfka12 6년 전 0

저도 방금 오버플로우를 찾아서 고쳤는데도 틀리네요....하...뭐가 문제일까여

cbs0615 6년 전 2

이렇게 고치니까 맞네요.

반복문 종료 조건을 둬서

마지막에 분자분모를 약분하는 부분만 추가했습니다

long long GCD(long long a, long long b){
    if(a < b) std::swap(a, b);

    if(b == 0) return a;
    else{
        return GCD(b, a%b);
    }
}

while (true) {
    unitFraction[1]=inputFraction[1]=LCM(unitD, inputD); // 분모를 최소공배수로 통분

    // 통분한 것에 대해 분자도 맞춰준다.0
    unitFraction[0] = unitN * (unitFraction[1] / unitD);
    inputFraction[0] = inputN * (inputFraction[1] / inputD);

    if (unitFraction[0] == inputFraction[0]){
        ans = inputFraction[1] / GCD(inputFraction[1], inputFraction[0]);
        break;
    }
    // 단위분수의 분자가 입력분수의 분자보다 작거나 같으면 빼주고 다시 처음부터 시작
    else if (unitFraction[0] < inputFraction[0]) {
        inputFraction[0] -= unitFraction[0];
        inputN = inputFraction[0]; inputD = inputFraction[1];

        if (inputN) unitD = inputD / inputN;
        else unitD++;
    }
    // 아니면 분모만 계속 증가시킨다.
    else unitD++;
    // 단위분수의 분자는 항상 1이기 때문에 초기화
    unitN = 1;
}

gkfkagkfka12 6년 전 0

와 약분일줄은 생각도 못했습니다 ㄷ...

감사합니다!!

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

문제

문제

출처

ICPC

헨리문제 반례를 모르겠습니다...

gkfkagkfka12 6년 전 0

cbs0615 6년 전 0

gkfkagkfka12 6년 전 1

cbs0615 6년 전 0

gkfkagkfka12 6년 전 0

cbs0615 6년 전 2

gkfkagkfka12 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말