Project Euler 286 - Scoring probabilities

Official link:

Thought Process

Fairly simple problem compared to a lot of other like this one.

We just set in the game with a recursive function

game(q, score, shots, needed_score)

  1. q is the current q we are using

  2. score is the current score we are at

  3. shots is the number of shots we've taken so far

  4. needed_score is how many we need, it would be 20 for the problem

  5. we just return (1 - shots/q)*game(q, score + 1, shots + 1, needed_score) + (shots/q)*game(q, score, shots + 1, needed_score)

  6. We make sure to check if our score goes above 20, we quickly break (return 0), if we reach 50 shots, if we have achieved score = 20, return 1, else return 0

Then we use a bisection method to find the necessary q. I used this exact algorithm, although dumbly, in Problem 285 which was much harder than this one, so It was fresh in my memory!

Interactive Code

Input an integer (yourinput)

Code outputs the q such that she has a 2% chance to score precisely yourinput number of points