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!