Problem Solving►UVa

UVa 10025 - The 1 2 n = k problem

Contents

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

Problem

題目網址
中文網址

注意 $0 = -1-2+3$，所以 $n = 3$。

Solution

直接做等差級數直到大於等於 n ，在判斷離目標相差多少，只要是偶數，一定可以利用前面的數字組成。
因為將前面的加號轉為負號，剛好都是差 2 的倍數。

+1 -> -1  => 差 2
+2 -> -2  => 差 4

且相差的數字一定會小於可組成的。

正負所使用的 n 相同，只是符號相反。

Code

UVa 10025UVa 10025 The 1 2 n = k problem
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
#include<cstdio>

int main()
{
    int Case;
    scanf("%d", &Case);
    while (Case--)
    {
        int n;
        scanf("%d", &n);
        int sum = 0, i;
        if (!n)
            puts("3");//-1-2+3
        else
        {
            if (n < 0)
                n *= -1;

            for (i = 0; sum < n; i++)
                sum += i;
            i--;
            while ((sum - n) & 1)//相差偶數就一定湊得出來
                sum += ++i;

            printf("%d\n", i);
        }

        if (Case)
            putchar('\n');
    }

    return 0;
}