Re: [問題] Codeforces R11 Problem B

[tkcn (小安)]

※ 引述《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
→ bleed1979:這題我只寫19行。
推 LPH66:我剛剛才仔細看這一題  這不就是 ?1?2...?n=k problem ?
→ LPH66:(ie. ACM 10025)
推 LPH66:我拿這題的 code 改個輸入丟上去就過了....(連範圍都沒動)
→ tkcn:這題我還沒寫過，晚點試試
→ tkcn:http://tinyurl.com/386l7vk  這頁最下面的做法就是我說的了
→ tkcn:順利 AC，應該可以寫得比 19 行短。
→ tkcn:縮過之後，總共 14 行 (Java)