hjh040506   1년 전

어디서 틀렷을까요 반례가 알고 싶어요

dlwocks31   1년 전

양쪽의 단위비용이 같을 때 잘못된 답을 출력하는 듯 합니다 . https://testcase.ac/problems/3343 에서도 반례 더 확인해볼 수 있습니다.


입력:

51 9 54 5 30

오답 출력:

324

정답 출력:

306

hjh040506   1년 전

#include

#include

using namespace std;

long long gcd(long long a, long long b){

if(b == 0) return a;

return gcd(b,a%b);

}

int main() {

long long n,a,b,c,d;

cin >> n >> a >> b >> c >> d;

bool first = false;

if((long double)b/a >= (long double)d/c) first = true;

long long sum=0;

long long lcm = a/gcd(a,c)*c;

long long k = n/lcm * lcm;

long long minn,p,m,t;

if(first)//c가 더 저렴함

{

sum += (k-lcm)/c * d;

n -= (k-lcm);

}

else//a가 더 저렴함

{

sum += (k-lcm)/a * b;

n -= (k-lcm);

}

if(n%a == 0)

{

p = n/a*b;

m = n/a * a;

t = n/a;

}

else

{

p = n/a * b + b;

m = n/a*a + a;

t = n/a + 1;

}

minn = p;

for(long long i=0; i= n) break;

p += d;

m += c;

}

minn = min(minn, p);

}

cout << sum + minn;

}

수정해서 모든 테스트 케이스 통과했는데  또 틀렸어요 너무 답답해요

dlwocks31   1년 전

제대로 포맷된 코드로 올려주셔야 좀 쉽게 찾아드릴 수 있습니다..

아마 https://testcase.ac/submission/169423 에서 제출한 코드 같은데 그 코드가 맞다면 아래와 같은 반례가 더 있습니다.

입력:

1 2 3 3 4

오답 출력:

2

정답 출력:

3

---

입력:

5 3 5 4 6

오답 출력:

9

정답 출력:

10

---

입력:

5 7 7 2 2

오답 출력:

5

정답 출력:

6

hjh040506   1년 전

해결됐습니다 감사합니다

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