The Race

Source: Project Euler 232

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.
   • Note that this is an output-only task; there is only one test case, and no time limit enforced.
2. Player 2 can choose a value of T on each move. What values should they choose from?

There is a natural characterisation of each step of the game.

3. Define appropriate subproblems to represent the game state.
   • Make sure that the answer to the original problem can be determined from the answers to these subproblems.
4. Propose a recurrence between these subproblems.
   • What are the base cases, i.e. those too simple to require a recursive solution?
5. In what order should you solve the subproblems?
   • Be careful of cyclic dependencies! Both players have a possibility of not scoring any points.
   • You may need to adjust your subproblem and/or recurrence to eliminate these.

6. Design an algorithm to solve the problem.

7. Analyse the time complexity of your algorithm and estimate its running time.

8. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
9. Submit your output for judging!
   • Debug as required.