最省納智捷1年新車83萬起金豪禮★拿現金最實在!正妹的東京自助旅行買太多也不行!7500...
2012-03-26 20:51:29 人氣(554) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 10025 - The ? 1 ? 2 ? ... ? n = k problem

0
收藏
0
推薦

 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

2

12

-3646397

Sample Output

7

2701

從一個正換到一個負, 之間的差距是偶數, 因此我們先得到 1+ ... + n = n*(n+1)/2 >= k
只要差是偶數, 便一定可以湊得到那個差距。
#include <stdio.h>
#include <stdlib.h>
int main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
n = abs(n);
int k;
for(k = 0; ; k++) {
if(k*(k+1)/2 >= n && (k*(k+1)/2-n)%2 == 0)
break;
}
printf("%d\n", n == 0 ? 3 : k);
if(t) puts("");
}
return 0;
}
 

10025The ? 1 ? 2 ? ... ? n = kproblem
台長:Morris
人氣(554) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][JAVA] 10183 - How Many Fibs?
此分類上一篇:[UVA] 10227 - Forests

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文