UVa 10025 - The ? 一 ? 2 ? . ? n = k problem

UVa 10025 - The ? 1 ? 2 ? ... ? n = k problem

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 ± 2 ± 3 ±…± n = k ， 找出满足条件的最小 n 。

   令S(n)=1 + 2 + 3 + ... + n. 其中一项为x.

     那么S(n)=1 + 2 + 3 + ...+ x + ... + n. 这样结果可能大于等于 | k | ,等于最好，即一次算出。

     所以我们把+ x 改成- x，此时得到新的关系：S'(n)=1+2+...-x+...+n.

     => S(n)-S'(n)=2x;且k=S'(n).令y=2x.

      利用这个特性，找出一个满足条件的y(即y是偶数)即可。

#include <stdio.h>int main(){    int i,j,n;    long long int s,t,k,m;    scanf("%d",&n);    while(n--)    {        scanf("%lld",&m);        if(m<0)        {            m=-1*m;        }        s=0;        t=0;        while((s-m)<0)        {            t+=1;            s+=t;        }        if((s-m)%2==0)        {            ;        }else        {            t+=1;            s+=t;            if((s-m)%2==0)            {                ;            }else            {                t+=1;            }        }        if(m==0)        {            printf("3\n");        }else        {            printf("%lld\n",t);        }        if(n)        {            printf("\n");        }    }    return 0;}

查看更多 下一篇