// ////////////////////////////////////////////////////////
// # Title
// Roman Numerals II
//
// # URL
// https://projecteuler.net/problem=610
// http://euler.stephan-brumme.com/610/
//
// # Problem
// A random generator produces a sequence of symbols drawn from the set {I, V, X, L, C, D, M, #}.
// Each item in the sequence is determined by selecting one of these symbols at random, independently of the other items in the sequence.
// At each step, the seven letters are equally likely to be selected, with probability 14% each, but the # symbol only has a 2% chance of selection.
//
// We write down the sequence of letters from left to right as they are generated, and we stop at the first occurrence of the # symbol (without writing it).
// However, we stipulate that what we have written down must always (when non-empty) be a valid Roman numeral representation in minimal form.
// If appending the next letter would contravene this then we simply skip it and try again with the next symbol generated.
//
// Please take careful note of [About... Roman Numerals](https://projecteuler.net/about=roman_numerals) for the definitive rules for this problem on what constitutes a "valid Roman numeral representation" and "minimal form".
// For example, the (only) sequence that represents 49 is XLIX. The subtractive combination IL is invalid because of rule (ii), while XXXXIX is valid but not minimal.
// The rules do not place any restriction on the number of occurrences of M, so all integers have a valid representation. These are the same rules as were used in Problem 89,
// and members are invited to solve that problem first.
//
// Find the expected value of the number represented by what we have written down when we stop. (If nothing is written down then count that as zero.)
// Give your answer rounded to 8 places after the decimal point.
//
// # Solved by
// Stephan Brumme
// October 2017
//
// # Algorithm
// My solution for problem 89 contained two useful functions: ''number2roman'' and ''roman2number''.
// There is a unique optimal Roman string for each number. The ''monteCarlo()'' function generates random string and checks whether ''x == roman2number(number2roman(x))''
// But the Monte-Carlo simulation can't find 8 correct digit after the decimal point (it barely finds the correct digits in front of the decimal point).
//
// I split Roman numbers into two groups:
// - those below 1000 ==> "that don't start with an M"
// - those greater than or equal to 1000 => "start with an M"
//
// For each number below 1000 I can generate its Roman string (container ''n2r'', read "number-to-Roman") and the inverse mapping ''r2n'' ("Roman-to-number").
// In a second pass I append to each Roman number each possible Roman letter and check whether this produces a valid, optimal Roman number.
//
// The ''search()'' function needs this information to find the expected value of a number (between 0 and 999) and its continuations:
// - if there is no continuation, then return the number itself, e.g. you can't append anything to IX => ''search(9) = 9''
// - if there is at least one continuation, then find the sum of
// `2% * current + 14% * search(next_1) + 14% * search(next_2) + ...`
// - if those percentages don't add to 100% (because not every of the seven Roman letters yields a valid continuation) then divide by the sum
//
// The expected value of all numbers between 0 and 999 can be found by ''search''ing all initial letters except M.
//
// Any numbers above 999 consists of one or more M's plus a number between 0 and 999.
// I try to add as many M's as possible until the probability of such a number is below my threshold `10^-9`
#include
#include
#include
#include