Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

MohamedHamada_'s blog

By MohamedHamada_, history, 3 months ago, In English,

I was solving the problem UVa 10368 and after thinking for a while i came up with this solution:

The first player have a number n%m == 0 or n/m > 1 is the winner and got AC ! :D

I just observed this solution when i tried some numbers on a paper but i actually don't have a rigorous proof for that ! could you demonstrate why this solution works ?

Thanks in advance :)

 
 
 
 

»
3 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

The following is a possible proof:

  1. The initial pair (m, n), where 0 < m ≤ n can be rewritten as (m, qm + r) where q ≥ 0 and 0 ≤ r ≤ m - 1 are quotient and remainder of the integral division div(n,m), respectively.

  2. Case 1: If r = 0, then the game is over, as the player can immediately subtract qm from n to make the next number zero and win.

  3. Case 2: If r > 0 and q > 1, then the next pair is (m, (q - k)m + r), where 1 ≤ k ≤ q. If k < q is chosen, then (q - k)m + r > m and the smaller number in the next pair is m. It is then guaranteed that the next remainder of dividing (q - k)m + r by m is non-zero as r > 0. Consequently, it is guaranteed that the other player does not win in the next play.

The following is a slight update to your program using the standard library function div(n,m).