// ////////////////////////////////////////////////////////
// # Title
// Scoring probabilities
//
// # URL
// https://projecteuler.net/problem=286
// http://euler.stephan-brumme.com/286/
//
// # Problem
// Barbara is a mathematician and a basketball player.
// She has found that the probability of scoring a point when shooting from a distance `x` is exactly `(1 - x/q)`,
// where `q` is a real constant greater than 50.
//
// During each practice run, she takes shots from distances `x = 1`, `x = 2`, ..., `x = 50` and, according to her records,
// she has precisely a 2% chance to score a total of exactly 20 points.
//
// Find `q` and give your answer rounded to 10 decimal places.
//
// # Solved by
// Stephan Brumme
// July 2017
//
// # Algorithm
// My solution is based on Dynamic Programming and bisection search.
//
// The function ''probability'' returns the chance that exactly 20 are made from distances 1,2,...,50 given a certain `q`.
// And the ''main'' function iteratively narrows a range of potential values for `q` until the range is so small that I can be sure
// to be extremely close to the true value of `q` (error is less than `10^-10`).
//
// The bisection part was obvious to me right from the start.
// However, I needed a few minutes to figure out that I can use a Dynamic Programming approach (again :-) ) for ''probability''.
// I was worried that the cache size might grow too fast and tried to solve the problem analytically.
// But as it turns out the cache contains only about 33000 values at the end (even without clearing it when a new `q` is processed).
//
// # Alternative
// My simple recursion could be probably replaced by an iterative algorithm because of the low number of different states (''made, distance'').
//
// # Note
// I play basketball and in my opinion the problem is phrased incorrectly:
// according to the "Project Euler Basketball rules" Barbara gets only 1 point per shot she made.
// In real life, a shot is usually worth 2 points. You get 1 point for a free throw and 3 points for a "long-range" shot.
//
// The correct result is found after 39 iterations.
// Due to the nature of bisection, narrowing the initial interval doesn't really speed up the process.
#include
#include
#include