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
ACM ICPC 2018 World Finals

Re:我的分析过程,包您满意~

Posted by ljinyu1998 at 2017-11-14 18:40:15 on Problem 3210
In Reply To:我的分析过程,包您满意~ Posted by:synapse at 2014-02-28 00:13:33
> 关键信息:所求的x是对于“任意一种”初始情况,使所有硬币正面或反面朝上的“最少”翻转此数,并且注意“only one coin could be flipped each time”,即每次只能翻转一枚硬币。
> 所以:
> 1. 答案要具有普适性,除了n为1时x=0,当n>1时x必为正,但是对于硬币全部朝上的情况也要翻转x次,由此可以得出:必须翻转偶数次;
> 2. 若n为偶数,考虑正面和反面都为奇数个硬币的情况,此时翻转次数必为奇数,矛盾,故此时No Solution;
> 3. 若n为奇数,则正面和反面的硬币数必为一奇一偶,那就不会出现“必须”翻转奇数次的情况(翻转偶数的硬币即可),所以x可能存在。
> 那我们来看看x的上界是多少:x不会大于n,反之,那对于任何情况至少会有一个硬币翻转了2次,不符合“最少”的要求,所以x<=n,但是n是奇数,x又必须为偶数,所以x<=n-1
> 那x的下界呢?来看看只有一个硬币朝上其余硬币都朝下的情况:若翻转那个朝上的硬币,则翻转次数必为2k+1,矛盾,所以我们应翻转其余n-1个朝下的硬币,这样x>=n-1
> 由这两个不等式可以得出当n为奇数时x必然存在,并且x=n-1

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