? 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
2 12 -3646397
Sample Output
7 2701 数学思维：
看似复杂，情况很多种，乍一看摸不着头脑的一道题，让人心生畏惧，Don't panic
数学思维，找规律求解
对于0=1+2-3 3
1=-1+2 2
2=1-2+3 3
依次查看，每个数的结果好像没什么规律
再看，会发现，若1变为-1，实际上将原数-2
2变为-2，实际上将原数-4 均为偶数，我们进步了一大步，我感觉离成功不远了，代码铁定不复杂，只需要我们想清楚
我们持续+，直到数s>k,此时若(s-k)%2==0,说明，s可将组成s的数中的一部分变为负数来的到k
问题转化为求满足s>k&&(s-k)%2==0的数s时，所经历的最大数 注意输出格式！减少不必要的麻烦。 PS：像这种基本的找规律题,数学思维，看得出就看，看不出就试
Version2.0
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "iostream"
#include "vector"
#include "queue"
using namespace std;
int main()
{
int t,k,s,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&k);
if(k==)
printf("3\n");
else
{
if(k<)k=-k;
s=n=;
while(s<k)s+=++n;
while((s-k)&)s+=++n;
printf("%d\n",n);
}
if(t)
printf("\n");
}
}
Version 1.0
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "iostream"
#include "vector"
#include "queue"
using namespace std;
#define LL long long
int main()
{
LL k;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&k);
int sum=;
int flag=;
if(k==)
{
printf("3\n");
}
else
{
if(k<)k=-k;
int t=;
while()
{
if(sum==k)///全为+ 15
break;
else if(sum>k)
{
if((sum-k)%==)///-在前面 13
break;
if(sum-t==k)///-在最后
{
flag=;
break;
}
else if(sum-t>k)
{
if((sum-t-k)%==)///-前后均有 12
{
flag=;
break;
}
}
}
sum+=t;
t++;
}
if(flag)t++;
printf("%d\n",--t);
}
if(T)printf("\n");
}
return ;
}