作者在 2012-03-20 13:24:21 发布以下内容
Sum
描述Consider the natural numbers from 1 to N. By associating to each number a sign (+ or -) and calculating the value of this expression we obtain a sum S. The problem is to determine for a given sum S the minimum number N for which we can obtain S by associating signs for all numbers between 1 to N. 时间限制：1000 ms | 内存限制：65535 KB
难度：2
For a given S, find out the minimum value N in order to obtain S according to the conditions of the problem. 输入The input consists N test cases.
The only line of every test cases contains a positive integer S (0< S <= 100000) which represents the sum to be obtained.
A zero terminate the input.
The number of test cases is less than 100000.输出The output will contain the minimum number N for which the sum S can be obtained.样例输入3 12 0样例输出2 7思路：找到连加使得和大于等于s，当和等于s时，不用说此时的n就是要求的值；当和大于s时，举个例子假设和是前n个数的和那么sum=n*(n-1)/2，sum-s必须为偶数假设是m，那么sum与s必定同奇同偶。
#include <stdio.h>
int main()
{
int i,s,a[700]={0,1};
for(i=2;i<=700;i++)
a[i]+=a[i-1]+i;
while(scanf("%d",&s),s!=0)
{
for(i=1;i<=700;i++)
{
if(a[i]==s)
{
printf("%d\n",i);
break;
}
if(a[i]>s)
{
if(s%2==0&&a[i]%2==0)
{
printf("%d\n",i);
break;
}
if(s%2&&a[i]%2)
{
printf("%d\n",i);
break;
}
}
}
}
return 0;
}