Stochastic Digit Generator

A stochastic digit generator (SDG) generates a decimal digit with a certain probability. The probability of the generation of one digit may be different than the other. Suppose this generator is allowed to generate N digits of a number one after another from right to left (least significant to most significant). “What is the probability that this number has a specific remainder when divided by 11?” In this problem you will have to determine such probabilities with some additional constraints. Input The input file contains at most 51 blocks of input. The description of each block starts with an integer 10 in a single line, which indicates that this is a valid input set and the probability of the generation of 10 decimal digits follow. Each of the next 10 lines contains a decimal digit di and a floating-point number pi (1 ≤ I ≤ 10). These lines indicate that the generator generates the digit di with probability pi. Note that values of all di will be distinct ∑ Input is terminated by a block whose first line contains a zero. Output For each block of input produce Q + 1 lines of output. The description of output for each block is given below: The first line contains the serial of the block. Each of the next Q lines contains a floating-point number with eight digits after the decimal point. The i-th floating-point number indicates the proba- bility that the numbers generated according to the format string Si has reminder ri when divided by 11. Sample Input 10 0 0.1 1 0.1 2 0.1 3 0.1 4 0.1 5 0.1 6 0.1 7 0.1 8 0.1 9 0.1 5 and Di=1 pi = 1. Next line contains an integer Q (0 < Q < 21) which indicates the number of queries for this set. Each of the next Q lines contains a format string Si (1 ≤ i ≤ Q) which actually denotes the format of the generated number followed my an integer r (0 ≤ ri ≤ 10). Each character of the format string will either be an ‘∗’ (asterisk) or a decimal digit. An asterisk in a position means that the generator can generate any digit for that position, a decimal digit indicates that for those places the generator doesnt work and generates only that specific digit. The format strings will have maximum 50 characters The integer ri denotes that when the generated number is divided by 11 the remainder will be ri.

2/2 *** 0 12* 0 1** 0 121 0 121 1 0 Sample Output Case 1: 0.09100000 0.10000000 0.09000000 1.00000000 0.00000000