Re: [問題] Codeforces R11 Problem B
以下這個方法只是能AC，但不代表恆正確，也可能是錯的。
解這題的基本認知︰
1.測資的正負是一樣的，所以一開始要轉正來解。
2.相鄰兩步數最少會差一步，2和3最小可能是+1或-1。
3.0，0 + 1 = 1， 0 + 1 + 2 = 3， 0 + 1 + 2 + 3 = 6，
0 + 1 + 2 + 3 + 4 = 10， 0 + 1 + 2 + 3 + 4 + 5 = 15，
0 + 1 + 2 + 3 + 4 + 5 + 6 = 21，
0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
為0，1，3，6，10，15，21，28....
0不要看，依序是奇奇偶偶奇奇偶偶奇奇偶偶....
解題，數據觀察。
1 2 3 最大為6
+ + + 6
+ + - 0
+ - + 4
+ - - 4 取絕對值，以下皆是。
- + + 4
- + - 2
推到這就可以發現，最大為6，但0，2，4，6通包了。
1 2 3 4 5 最大15
+ + + + + 15
+ + + - + 7
+ + + - - 3
+ + - + + 9
+ + - + - 1
+ + - - - 9
+ - + + + 11
+ - - + + 5
- + + + + 13
我跳著推，但推到這就發現，最大為15，但1，3，5，7，9，11，13，15通包了。
到此階段可以合理的假設。總和如果是奇數，從1開始的奇數會包含。
同理如偶數。
所以，我的作法就是用for迴圈一直加總，
跳出迴圈的條件為總和大於等於測資且測資%2和總和%2相等。
有人可能會說，如果找14呢？
14相當於15差兩步(5 + 2 = 7)(基礎知識1) 或是
加總到7(15, 21, 28)(基礎知識3)
都是7步。
如果是找20呢？
從21倒回來找的話，6 + 2 = 8步
但是在加總到7時，28 % 2 == 20 % 2，7步就會有解了。
特別講一下CodeForces這題和UVa 10025的差別，
UVa 10025規定找到的數字>= 1
所以input 0的話，這個假設的公式會找到0但在UVa那裡必須是3。
Bleed
※ 引述《chchwy (mat)》之銘言：
: http://codeforces.com/contest/11/problem/B
: 請問一下這題到底該怎麼解呢
: 感覺應該是有某種規律....不過我找不出來 orz
: 建表跟暴力搜尋都太慢了
: ==
: 順便偷問..這裡也有人在打code force嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97
※ 編輯: bleed1979 來自: 114.32.177.97 (04/28 14:36)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 4 篇)：