Codeground) 윤목의 달인

1<= P <= 5

인 실수 P 가 입력으로 들어오는데 최대 소수점은 9번째자리까지이다.

윤목은 한번 시행했을 때 1~5점을 얻게되는데 여러번 시행했을 때 최소 시행 횟수로

평균 점수가 정확히 p가 되기 위하여 각 점수를 몇번씩 획득해야하는지 구하는 문제이다.

어떤 주어진 소수를 정수로 만들기 위해 곱해야 하는 최소 정수를 구하면 그게 바로 총 시행 횟수의 최소값이 될 것이다.

이 때 구하는 방법은 여기를 참고

이 시행 횟수를 C라고 해보자. 그러면 P*C 는 그 때의 점수의 총 합이 될 것인데, 이것을 S라고해보자.

그럼 1~5점을 C번 골라서 S가 되는 경우를 하나만 찾으면 된다.

조금만 생각해보면 답은 여러개가 될 수 있다는 것을 알 수가 있다. 두 점수의 합이 4가 되는경우가

2점+2점 과 1점+3점 이 있다는 것만 봐도 알 수가 있다. 우린 그럼 이 경우의 수중에 딱 한개만 고르면

될 것이다. 우리는 그래서 그리디하게 구할 것이다. 우선 식을 두개 써보자

a + 2*b + 3*c + 4*d + 5*e = S    .... 1번식

a + b + c + d + e = C               .... 2번식

1번식에서 2번식을 빼보자. 그럼

b + 2*c + 3*d + 4*e = S - C

가 된다. 그럼 이 식을 만족하는 b, c, d, e 조합을 하나만 구하면 되는데 만약 b 를 S - C로 주고

c, d, e 를 0으로 줘보면 어떻게 될까? b가 매우 커져서 C보다 커질 수가 있고 그러면

2번식을 만족할 수 없게 된다. 왜냐하면 시행횟수는 무조건 음이아닌 정수이기 때문이다.

그러면 고득점을 최대한 많은 횟수를 할당하고 나머지 남는 점수를 저득점에 할당하는 식으로 해보자.

고득점에 최대한 많은 수를 할당했다면 저득점의 시행 횟수는 클 수가 없기 때문에 b + c + d + e 는

최소가 될 수밖에 없고 그러면 2번식에서 b~e 를 우변으로 넘겨서 나오는 식인

a = C - b - c - d - e

를 풀면 a의 개수를 구할 수가있다. 만약 (b + c + d + e) 가 C 보다 커서 a가 음수가 되어야 하는 경우가

나올 수 있을까 걱정할 수가 있는데, 우리는 그리디 하게 b + c + d + e 를 최대한 작게 해줬는데도

C보다 크다면 애초에 이것은 1번식과 2번식을 모두 만족하는 a,b,c,d,e 조합이 존재하지 않는다는 말이(될 것같)다.

근데 왠지 조합은 무조건 존재한다. 왜냐하면 1~5점 C 개로 만들 수 있는 총점은 C~5*C 점 이기 때문에

이것을 C로 나눠 나오는 평균 점수인 P를 1~5인 모든 실수에 대해 만들 수가 있다.(아마도)

그래서 모순이므로 그리디하게 하면 된다..

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int T;
double P;
ll ans[5];
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}
int main() {
    cin >> T;
    for(int t = 1; t <= T; t++){
        memset(ans,0,sizeof(ans));
        cin >> P;
        ll S = 1e12;
        ll GCD = gcd(P*S, S);
        ll C = S/GCD;
        S = P * C;
        S -= C;
 
        ans[4] = S/4;
        if(S%4) ans[S%4]++;
 
        ans[0] = C - ans[1] - ans[2] - ans[3] - ans[4];
 
        cout << "#testcase" << t << "\n";
        for(int i = 0 ; i < 5; i++) cout << ans[i] << " ";
        cout << endl;
    }
    return 0;
}