首页 > 代码库 > 【原创】UVAOJ水题10025解题报告

【原创】UVAOJ水题10025解题报告

首先是原题,转自UVAOJ

 The ? 1 ? 2 ? ... ? n = k problem 

The problem

Given the following formula, one can set operators ‘+‘ or ‘-‘ instead of each ‘?‘, in order to obtain a given k
? 1 ? 2 ? ... ? n = k

For example: to obtain k = 12 , the expression to be used will be:
- 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 
with n = 7

The Input

The first line is the number of test cases, followed by a blank line.

Each test case of the input contains integer k (0<=|k|<=1000000000).

Each test case will be separated by a single line.

The Output

For each test case, your program should print the minimal possible n (1<=n) to obtain k with the above formula.

Print a blank line between the outputs for two consecutive test cases.

Sample Input

212-3646397

Sample Output

72701


Alex Gevak
September 15, 2000 (Revised 4-10-00, Antonio Sanchez)

 

 

简单说,就是一组从1开始到n的自然数序列,每个数字以前可以填写-号和+号,要求最后的结果等于另外给定的数字k。这里要求为了满足k,所能达到的最小的n。

 

分析:

此题当然可以穷举每个可能,但n个数需要穷举2^n次,也就是从1到n,需要穷举几何级数规模次,爆定了,抛弃;

但容易知道,当1到n1全是+号且和小于k时,不可能有解。因此,需要连加至sum > k时开始判断。

当sum > k时,设Q = sum - k,则k = sum -Q -> k = (1+2+3..+n) - Q。这里,需要转换该等式为1 + 2 - 3 - 4...+ n的形式。对于1到n而言,若欲改变特定数位正号为符号,需要减去两倍该数,而减去的数需从Q中分解,故有以下推论:

1、Q必须为偶数

2、当Q/2大于n时,需判断是否分解Q为x个不同偶数之和。

换言之,在n足够大时,由于任意大于4的偶数一定能分解为x个不同偶数之和同时2对应1而4对应2,我们就可以保证,当Q为偶数时,此时n为最小值;当Q为奇数时,由于无法将Q拆进原自然数序列,故此时n不是解。

前述断言,我想证明,但证明失败了。于是只能退而求其次,寻找结果为Q的不同偶数连续相加中的最大偶数。

如16 = 2 + 4 + 10,最大不重复偶数为10

设为函数fun,代码如下:

int fun(int x)

{

    int left = 2;
    int result = 0;
    while(result == 0)
    {
     while(x - left < left)
    {
            if(left >= x)
            {
                    result = left;
                    break;
            }
            left += 2;
    }
    x -= left;
    left += 2;
    
    }
    return result;  

}

这个函数返回最大偶数,跟n比较,若小于n,则证明偶数Q对应的n是解。

 

下面是全部代码

#include <stdio.h>
int main()
{
    int n;
    long long k;
    int i;
    int sum = 0;
    int result = 0;
    int flag = 0;
    int temp;
    int left;
    int right;
    scanf("%d",&n);
    while(n--)
    {

            scanf("%lld",&k);
            sum = 0;
            flag = 0;
            if(k < 0)
                 k = -1 * k;
            for(i = 1;sum < k;i++)
                  sum += i;
            i --;
            if(sum == k)
            {
                   result = i;           
            }
                        if(k == 0)
                        result = 3;
            else
            {
                while(1)
                {
                        temp = sum - k;
                        if(temp % 2 != 0)
                        {
                                i++;
                                sum += i;
                                continue;
                        }        
                        else
                        {

                                int max = fun(k);

                                if(max <= n)
                                   break;
                        }
                }
                if(k)result = i;
            }        
    printf("%d\n",result);
    if(n)printf("\n");
    }
    return 0;
}

 

先前,我的while里的条件是 n!=0,循环体里有n--,但是WR过不了,换成while(n--)就过了,真是百思不得其解。。。

托这个的福,连续刷了3个wrong answer。。。

 

遗留问题:

直觉上,感觉Q是偶数就能解,但是始终拿不出严格的数学证明。于是,只能选择判断最大偶数与n孰大孰小的方案。首先,1加到n减去偶数Q大于0,因此,分解出不同偶数连续和中的所有偶数数目小于n,同时,用最大值来与n比较,若大于n,则无论怎么分解都无法在1~n的自然数序列中找到与之对应的值,当前n为解;若小于n则证明当前n为解。

【原创】UVAOJ水题10025解题报告