SRM 526 Div 1 500

Horray :) :) ... I am so happy this is my first 500 to solve on my own :) :)


Here is a link to the problem statement.


My solution is greedy and it depends on the following observations:

A. If the N < 3 the result is 0 because you can't make a move after that.

B. N=3 is your only winning state because any other prime you choose bigger than 3 the other player can remove one from it without hitting another prime.
C. Your losing state is when you hit an integer N that there is no primes in the K integers smaller than it.
D. Letting L to be your smallest losing state. If N is smaller than L you will always win. If N is equal of bigger than it you will always lose.(because you can,t reach from L or any integer bigger than it any prime smaller than it)
E. The strategy if you are winning

1. Go to 3 if you can.
2. else go to smallest prime you can // to speed the game up
3. the other player will always go the next integer // to try to make it take as much as possible

F. The strategy if you are losing

1. try to go to the nearest prime // to slow the game down
2. try to find any integer within range that is a losing state
3. if not go to the smallest integer you can

  And here is the code ... enjoy :)