MohamedHamada_'s blog

UVa 10368 — Euclid's Game ... proof ?
By MohamedHamada_, history, 6 years 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 :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years 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).

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In codechef may long challenge divB, Qn2 "matches" is same as above. I implemented your logic and got WA. It seems that there may be weak testcases at uva platform. And i still dont know at which testcase , this logic is getting WA.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

whoever has n/m > 1 first approach works too.

→ Reply