UVa 10025 The ？ 1 ？ 2 ？ ... ？ n = k problem：数学&想法题&常数算法

UVa 10025 The ？ 1 ？ 2 ？ ... ？ n = k problem：数学&想法题&常数算法2014-07-14 csdn博客 synapse710025 - The ？ 1 ？ 2 ？ ... ？ n = k problem

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=966

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

首先，1~n的和sum一定要>=k。当sum >n时要减掉一个数，比如在数字a前面加个-号，相当于sum - 2 * a，也就是说每次减掉只能是偶数，那么就要求sum % 2 == k % 2.（负数同理）

O（√k）代码：

/*0.006s*/#include<cstdio>#include<algorithm>using namespace std;int main（void）{int T, k, sum, i;bool flag = false;scanf（"%d", &T）;while （T--）{if （flag）putchar（"
"）;elseflag = true;scanf（"%d", &k）;k = abs（k）, sum = 0;for （i = 1;; i++）{sum += i;if （sum >= k && （（sum - k） & 1） == 0）{printf（"%d
", i）;break;}}}return 0;}