PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Codeforces R11 Problem B

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間14年前 (2010/04/28 13:50)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串3/4 (看更多)

以下這個方法只是能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)