PS와 개발을 공부하자

Codeground) 윤목의 달인 본문

Algorithm/Problem Solving

Codeground) 윤목의 달인

sgc109 2017.05.26 16:23

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인 모든 실수에 대해 만들 수가 있다.(아마도)

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}
cs


'Algorithm > Problem Solving' 카테고리의 다른 글

CSacademy) Second Minimum  (0) 2017.06.01
알고스팟) COUNTPALIN  (0) 2017.05.31
Codeground) 윤목의 달인  (0) 2017.05.26
Topcoder SRM 522 Div1(Medium) CorrectMultiplication  (0) 2017.05.20
BOJ 14276번 도로 건설  (0) 2017.05.11
Hackerrank) Tree Pruning  (0) 2017.05.11
0 Comments
댓글쓰기 폼