Hdu1847 problem solving ideas

HDU1847（ Bash Game ）

• Ideas ： Because it is the last time to win （ Definition of bash game ）, So for starters , Make sure you don't win immediately after you take it
• reflection , When n by 2^k when , Win first f;
• When n No 2 ^ k when , If you want to win first , It is necessary to ensure that the status after fetching is " Later stage " Winning state ,
• such as n6 when , You can take it first 1,2,4, And I know n2,4,5 When the state is " First of all " victory , Then the final backhand wins
• When again n7 when , If you take it first 4, And I know n3 When the state is " Later stage " victory , So finally win first
• Further generalize , Can be found when n from 1 Gradually increase , The winner in succession is “ First in order ” loop
• n==1,2,3( as well as 4,5,6) The situation is easy to prove , When n>3 when , Make k=3z-2(z>=3 And z It's a positive integer. ) And k<=n<=k+2, that k, k+1, k+2 Form a group
• here ,k+1 You can always subtract 2 Get the last value of the previous group （ The winning state of the backhand ）, So it won first ;
• k By subtracting 4 Get the last value of the upper group （ The winning state of the backhand ）, So it is also the first to win ;
• and k+2 Subtract one 2 The last value of any previous group must not be obtained after the power of （ Because these values are 3 Multiple ）, So it must be a victory for the backhand