Problem Solving►UVa

UVa 668 - Parliament

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

簡而言之就是要用 不重複 的數字，和為 n ，且乘積最大。

Solution

先直接放 2,3,4,… ，不要超過 n。(比起單一個數字加 1，多一項比較好)
接著看相差多少，因為數字不能重複，所以從最後一項開始，一個一個加一，直到第一個，如此循環。

ex.

n = 8
2 + 3 = 5
diff = 8 - 5 = 3

diff = 2:    2 + 4 = 6
diff = 1:    3 + 4 = 7
diff = 0:    3 + 5 = 8

Ans: 3 5

Code

UVa 668
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
36
37
38
39
40
#include<cstdio>

int main()
{
    int Case, ans[100] = {};
    scanf("%d", &Case);
    while (Case--)
    {
        int n, i;
        scanf("%d", &n);
        int sum = 0, count = 0;
        //先直接放2,3,4,... ，不要超過 n
        while (true)
        {
            ans[count] = count + 2;
            if (sum + ans[count] <= n)
                sum += ans[count++];
            else break;
        }

        int diff = n - sum;
        for (i = count - 1; diff; diff--)
        {
            //相差的從後面依序加一(循環)，直到總合為 n
            ans[i]++;
            sum++;
            i--;
            if (i < 0)
                i = count - 1;
        }

        for (i = 0; i < count - 1; i++)
            printf("%d ", ans[i]);
        printf("%d\n", ans[i]);
        if (Case)
            putchar('\n');
    }

    return 0;
}