Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:好题啊, 赞一个

Posted by dengd at 2010-02-21 16:19:51 on Problem 1844
In Reply To:好题啊, 赞一个 Posted by:Be_the_top at 2009-08-01 16:35:34
> 我也是看了各位大牛的讨论才明白的, 我把它写的更加具体点了而已
> 一:sum一定要大于或等于输入的S.(等于时就已经找到了答案)
>    小于的话就算全做加法运算也不能达到S。
>              
> 二:在满足第一条的情况下,注意一定要满足第一条后
>    第一次碰到(sum - S ) % 2 == 0 
>  这里( sum = 1 + 2  + .... + i )这时的i就是答案。
>   证明如下:
>              1:若res是奇数,就说明res = ( 1 + 2 + ... + i )- S 是奇数
>              也就是说无论你怎么改变sum( sum = 1 + 2  + .... + i )的表达式
>              (当然是通过改变其中的加号为减号)也无法让res为0
>              举个例子吧:S = 5, sum = 1+2+3 = 6, res = 6 - 5 = 1;
>            无论改变(1+2+3)中的加号也没用,这是因为你在sum中改变一个加号为减号
>              时它的值就一定减少了一个偶数值(这是显然的)sum-S仍然为奇数
>              2:令res = sum - S,则res一定是0,2, 4, 6....中的一个
>              下面说明总可以通过改变sum表达式中的某几个加号为减号使得res为0
>              当k = 0的情况就不用说明了吧, 假设2k表示res 显然k = 1 2 3 4...
>             当k = 1 时可以通过把sum( sum = 1 + 2 + ... + i )
>             改成( sum = -1 + 2 + ... + i )
>             当k = 2 时可以通过把sum ( sum = 1 + 2 + ... + i )
>             改成( sum = 1 - 2 + ... + i ) 
>             一次类推res总可以变为0
>                                    
多谢                           

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator