作者tkcn (小安)
看板Prob_Solve
標題Re: [問題] Codeforces R11 Problem B
時間Wed Apr 28 11:56:35 2010
※ 引述《chchwy (mat)》之銘言：
: http://codeforces.com/contest/11/problem/B
: 請問一下這題到底該怎麼解呢
: 感覺應該是有某種規律....不過我找不出來 orz
: 建表跟暴力搜尋都太慢了
: ==
: 順便偷問..這裡也有人在打code force嗎
只考慮 x 為正數的情況(反正負數也一樣)。
令 y = 1+2+...+j (假設全部都往右跳)
先找到 j 使得 y >= x，
如果 y > x，表示其中有一些 "向右跳" 要改成 "向左跳"，
所以只要能夠找到一組 1~j 之間的 subset A，使得 y - 2*sum{A} = x 即可。
很顯然 x-y 必須是偶數，否則一定找不到 subset A。
(所以如果不是偶數，可以把 j 的值加 1 然後從頭開始)
寫到這裡應該夠了?
--
◤ ◥ ◢ ◣
T$，修好它吧。 ⊙▁⊙─ ─⊙▂⊙ 碰到問題，用SoftICE就對了！
╰ ∕皿﹨ ◥皿◤ ╯
◥█◤◢ ◥ ︶◤
Lee ◤ ︶ ◥◤ ﹨▼∕◥ T$ Chen
ＭＹＴＨＢＵＧＴＥＲＳ ◥ ◤＼◥ by dajidali
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.122.183.199
1F：→ bleed1979:這題我只寫19行。 04/28 13:08
2F：推 LPH66:我剛剛才仔細看這一題 這不就是 ?1?2...?n=k problem ? 04/28 13:27
3F：→ LPH66:(ie. ACM 10025) 04/28 13:27
4F：推 LPH66:我拿這題的 code 改個輸入丟上去就過了....(連範圍都沒動) 04/28 13:30
5F：→ tkcn:這題我還沒寫過，晚點試試 04/28 14:13
7F：→ tkcn:順利 AC，應該可以寫得比 19 行短。 04/28 14:49
8F：→ tkcn:縮過之後，總共 14 行 (Java) 04/28 15:08