Re: [問題] Codeforces R11 Problem B
※ 引述《bleed1979 (十三)》之銘言：
: 以下這個方法只是能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開始的奇數會包含。
: 同理如偶數。
其實這是可以證明的
若 1+2+...+n = K 是奇數
則 -1+2+3+...+n = K-2
1-2+3+...+n = K-4
1+2-3+...+n = K-6
...
1+2+3+...-n = K-2n
-1+2+3+...-n = K-2n-2
1-2+3+...-n = K-2n-4
...
依此類推即知 [-K,K] 當中的所有奇數都包了
K 是偶數時同理
: 所以，我的作法就是用for迴圈一直加總，
: 跳出迴圈的條件為總和大於測資且測資%2和總和%2相等。
: 有人可能會說，如果找14呢？
: 14相當於15差兩步(5 + 2 = 7)(基礎知識1) 或是
: 加總到7(15, 21, 28)(基礎知識3)
: 都是7步。
: Bleed
我這題送 ACM 10025 的做法是建表
______
建出一個 1~n 的總和表 n 建到 45000 (比 √2*10^9 稍大)
然後找和時就二分搜尋 再往後找奇偶相等的就是了
因為二分搜尋的關係 往後找頂多找個三四步 所以還滿快的
但意外的在這個地方也可以過...
(這裡和 ACM 不一樣是一次執行一組測資 這種的寫法會比 Bleed 的稍慢)
--
"LPH" is for "Let Program Heal us"....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
→
04/28 14:37, , 1F
04/28 14:37, 1F
→
04/28 14:38, , 2F
04/28 14:38, 2F
討論串 (同標題文章)
完整討論串 (本文為第 4 之 4 篇)：