Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 9795 Accepted: 6406
Description
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.
For a given S, find out the minimum value N in order to obtain S according to the conditions of the problem.
Input
The only line contains in the first line a positive integer S (0< S <= 100000) which represents the sum to be obtained.
Output
The output will contain the minimum number N for which the sum S can be obtained.
Sample Input
12Sample Output
7Hint
The sum 12 can be obtained from at least 7 terms in the following way: 12 = -1+2+3+4+5+6-7.
Source
Romania OI 2002
思路：
算是很簡單的數學題目了,但是昨天晚上就算幾乎是推出了規律，居然都沒有折騰出來太弱了。
然後完賽後在群裡和 TeilWall 吐槽了下，就差淚奔了。。。
正解思路：
先定義 sum(i) = 1+2+...+i = (i+1)*i/2 【小學數學。。。(首項+末項)*項數/2 了解Orz】
可想而知 sum(i) 是 i 能確定的最大的數。
1.對於每一個輸入的數 S ,我們找符合條件的 i 肯定是可以從 sum(i) >= S 開始枚舉 i 的。
分析：如果連 sum(i) < S 那麼 i 肯定是不符合條件的了。
PS：昨晚我在草稿紙上是逆推的,結果搞的很復雜,也沒有注意到從 sum(i) >= S 這裡開始枚舉。。。
2. 當我們由第一步確定了 i 後有兩種情況：
(1)Sum(i) == S ，那麼很明顯 i 就是答案,直接輸出即可。
(2)Sum(i) > S , 從 i 開始,依次往後面 +1 枚舉 ，只要遇到 (Sum(i) - S) % 2 == 0 輸出答案就可以了。
其實 0%2 == 0 所以第一類情況實際上是可以歸類於第二種情況的了。
分析：
情況一已經很明顯了,下面主要分析情況二。。。
對於每一個 i 能夠確定的數：
很明顯最大的是 Sum(i) ，
然後再把序列 1,2,3，...i 中的 + 依次改成 - 那麼能確定的下一個數一定比前一個數小二
比如說 i = 3， 那麼能夠確定的數是 6 ,4 ,2 ，（1）
i = 4, 能確定的數是 10, 8， （6）
i = 5， 能確定的數是 15,13,11,9,7,5， （3）
這裡有一個問題：如何確定能確定的最後一個數在哪裡截止, 如果減到後面遇的數已經被前面的數確定過,那麼就不用往後
面減了，由於前面已經提到了，我們是從前面往後面枚舉的 i 所以就不用考慮到哪裡截止的問題了。
那麼從這裡可以看出:
對於一個數 i 它能確定的最大的數是 Sum(i)，
如果對於當前的 i 它能夠確定當前的 S ，那麼 Sum(i)-S 一定是二的倍數。【(Sum(i)-S) % 2 == 0】
因為我們是從最小的可能滿足條件的 i 開始枚舉的,所以不會出現前面的 i 滿足條件而小於當前的 i 的情況。
也就是說一旦遇到了 (Sum(i)-S)%2 == 0 輸出 i 就可以了。
我比賽時的想法分析：
當時我已經在草稿紙上畫出了下面的東東了。。。
但是我居然是逆推的，同時沒想過枚舉。。。而且這麼明顯的結論也沒有看出來，然後我就推出了下面的復雜而傻逼的公式。。。
如果結尾的數 N 是偶數：
那麼 N 可以確定的數是從 (1+N)*N/2 開始 依次減二 直到大於 (1+ N-1)*(N-1)/2 為止
如果結尾的數 N 是奇數：
那麼 N 可以確定的數是從 (1+N)*N/2 開始 依次減二 知道大於 (1+ N-2)*(N-2)/2 為止
。。。。
然後實在是無法逆推出直接的公式了,也想到過枚舉,但是開始沒想到枚舉的區間從哪裡開始
然後看做這題無望，時間已經過去了大半,就果斷去寫了前面簡單的貪心。。。一直自認為關於找規律還是很在行的了,結果還是坑在了這題上。
code：
#include<stdio.h>
const int maxn = 100000;
int main()
{
int s;
while(scanf("%d", &s) != EOF)
{
int sum = 0;
int i;
for(i = 1; i < maxn; i++) //先找到和 <= 自己的最小的數
{
sum = (1+i)*i/2;
if(sum >= s) break;
}
int index = i; //記錄
for(;;)
{
sum = (1+index)*index/2;
if((sum-s)%2 == 0) //往後面找, 只要找到就輸出
{
printf("%d\n", index);
break;
}
index++;
}
}
return 0;
}
