Infinite Stable Integer

For any infinite-length decimal integer S = d1d2d3d4 ... (0 ≤ di ≤ 9, i ≥ 1), let prefix(S,p) be the integer formed by the first p digits of S (i.e. d1d2d3 . . . dp), and F (S, i, p) be the percentage of digit i in pref ix(S, p). For example, if S = 122312231223..., F (S, 2, 7) = 4 ∗ 100 7 We say S is stable if and only if every for digit i (0 ≤ i ≤ 9), there exists a real number L(i) such that lim F(S,i,p) = L(i) p→∞ Given three positive integers M, X and Y (0 ≤ X ≤ Y < M), and 10 pairs of integers (A(0),B(0)), (A(1), B(1)), ..., (A(9), B(9)), find an infinite stable integer S such that:

1. Every L(i) satisfies A(i) ≤ L(i) ≤ B(i)
2. Foreveryintegerp≥1,X≤(prefix(S,p)modM)≤Y. If there are more than one solution, maximize the average value of all the digits in S. Since S is stable, it can be proven that the average value converges. Forexample,ifM =9,X =1andY =8,B(3)=B(4)=100,allotherA(i)andB(i)arezero,then the optimal S is 44(4444443)*, where * means “repeated forever”. It’s not hard to see that prefix(S,p) will never be a multiple of 9, and L(3) = 1 ∗ 100, L(4) = 6 ∗ 100, all other L(i) = 0. 77 Input There will be multiple test cases. Each test case contains 23 integers: M, X, Y , A(0), A(1), ..., A(9), B(0), B(1), ..., B(9). 2 ≤ M ≤ 50, 0 ≤ X ≤ Y < M, 0 ≤ A(i) ≤ B(i) ≤ 100. Output For each test case, print case number and the maximal average value rounded to 8 decimal places. If no infinite stable integer can be found, print ‘NO SOLUTION’ instead. Look at the output for sample input for details. Sample Input 2 1 1 0 0 0 0 0 0 0 0 0 0 20 20 20 20 20 20 20 20 20 20 9 1 8 0 0 0 0 0 0 0 0 0 0 0 0 0 100 100 0 0 0 0 0 80711111111112222222222 192 3 0 0 0 0 0 0 0 0 0 0100100100100100100100100100100 Sample Output Case 1: 5.00000000 Case 2: 3.85714286 Case 3: NO SOLUTION Case 4: 1.00000000