B |
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 prefix(S,p).
For example, if S = 122312231223..., F(S,2,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
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. For every integer p ≥ 1,
X ≤ (prefix(S, p) mod M )≤ 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.
For example, if M=9, X=1
and Y=8, B(3)=B(4)=100, all other A(i) and B(i) are
zero, 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)=, L(4)=,
all other L(i)=0.
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.
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 8 0
7 1 1 1 1
1 1 1 1 1
1 2 2 2 2
2 2 2 2 2
2 19 2 3 0 0 0 0 0 0 0 0 0 0 100 100 100 100 100 100 100 100 100 100 |
Output for Sample Input |
Case 1:
5.00000000 Case 2:
3.85714286 Case 3: NO SOLUTION Case 4:
1.00000000 |
Problemsetter: Bin Jin, Rujia Liu