Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Game Theory Problem [2018 ICPC Singapore Online Contest]

Revision en1, by john_hopes, 2018-09-19 09:59:13

Is there anyone can help me to solve this problem?

Problem Link: https://open.kattis.com/problems/foolingaround

Problem Description:

Alice and Bob take turns playing a game, with Alice going first. They begin with a pile of N stones, each turn removing one less than a prime number of stones. The person who removes the last stone wins. Given N, determine who wins the the game.

Constraints: N>0 and N<=10^9

I already read some solutions. They just pre calculated all the N for which Second Player wins and answer each query.

How can I pre calculate all the N(Second Player wins)?

Tags game theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English john_hopes 2018-09-19 09:59:13 664 Initial revision (published)