The ? 일?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 ? 일?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

먼저 첫 번째 s=1+2+3+...+n>=k의 첫 번째 n은 s-k가 짝수라고 가정하면 이때 n은 최소값이다. 그렇지 않으면 최소값은 n+1 또는 n+2(연속된 두 수에 반드시 하나의 홀수가 있기 때문에 s-k의 짝성을 바꿀 수 있다).... 때문에
우선 n개수의 짝수와 k의 짝수가 같아야 한다. 아무리 기호 n개수의 짝수가 바뀌어도 변하지 않기 때문에 짝성이 같으면 n-k는 짝수일 것이다. n-k는 짝수일 때 변호의 수는 (n-k)/2, s'=k, s-(s-k)=1+2+...
-(n-k)/2
+....n=k;그래서 이때 구한 n은 반드시 k를 구성할 수 있고 가장 작은 것이다. 코드는 다음과 같다.

#include<stdio.h>
#include<math.h>
int main()
{
    int i,k,n,m;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&k);
        if(m==0)printf("3
");
        else
        {
            k=k>0?k:-k;
            m=sqrt(2*k);
            for(i=m;i*(i+1)<2*k;i++);
            while(1)
                if((i*(i+1)/2-k)%2)i++;// 
                else break;
            printf("%d
",i);
        }
        if(n)printf("
");
    }
    return 0;
}