Minimal Weighted Digit Sum

All submissions for this problem are available.
Let M be a fixed positive integer. Your task is for each R from 0 to M − 1, inclusive, find the minimal nonnegative integer having residue R modulo M and having the minimal weighted digit sum.
Namely, let W[0], W[1], ..., W[9] be the sequence of weights assigned to the decimal digits. For positive integer N having decimal representation D_{1}D_{2}...D_{K} the weighted digit sum of N is the number WS(N) = W[D_{1}] + W[D_{2}] + ... + W[D_{K}]. We set WS(0) = 0 by definition.
For each R from 0 to M − 1, inclusive, denote S_{min}(R) = min{WS(R + K * M) : K = 0, 1, 2, 3, ...}. Therefore, S_{min}(R) is the minimal weighted digit sum over all nonnegative integers having residue R modulo M. Next, denote by N_{min}(R) the minimum nonnegative integer having residue R modulo M and having weighted digit sum equal to S_{min}(R). So, formally, N_{min}(R) = min{N ≥ 0 : N mod M = R, WS(N) = S_{min}(R)}. Note, that S_{min}(0) = N_{min}(0) = 0 for any M and any sequence of weights.
As mentioned above, your task is for the given M and W[0], W[1], ..., W[9] find the sequence N_{min}(0), N_{min}(1), ..., N_{min}(M − 1). Since the output could be quite large output the following sum instead:
F(N_{min}(0)) + F(N_{min}(1)) + ... + F(N_{min}(M − 1)),
where F(0) = 0 and for positive integer N with decimal representation D_{1}D_{2}...D_{K}:
F(N) = (D_{1} * 3141^{K−1} + D_{2} * 3141^{K−2} + ... + D_{K−1} * 3141 + D_{K}) mod 2^{32}.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains an integer M. The second line contains ten space separated integers W[0], W[1], ..., W[9].
Output
For each test case, output a single line containing the required sum.
Constraints
 1 ≤ T ≤ 3141
 1 ≤ M ≤ 3141592
 0 ≤ W[0], W[1], ..., W[9] ≤ 314
 The sum of M in one test file does not exceed 3141592
Example
Input: 6 1 3 1 4 1 5 9 2 6 5 3 2 0 2 9 9 9 9 9 9 9 1 3 0 10 2 3 4 5 6 7 8 9 4 99 99 99 1 99 99 2 99 99 99 5 1 1 1 1 1 1 1 1 1 1 3141 31 41 59 26 53 58 97 93 23 0 Output: 0 9 6 9435 10 6500672892792
Explanation
Example case 1. Here M = 1. So we need to find F(N_{min}(0)). Since S_{min}(0) = N_{min}(0) = 0 and F(0) = 0, the answer is 0.
Example case 2. Here M = 2 and W[0] = 0, W[1] = 2, W[9] = 1, while all remaining W[D] = 9. As mentioned above S_{min}(0) = N_{min}(0) = 0. For R = 1 we have S_{min}(1) = 1 and N_{min}(1) = 9 since W[9] = 1. Therefore, the answer is F(0) + F(9) = 0 + 9 = 9.
Example case 3. Here values of S_{min}(R) are {0, 4, 2} and values of N_{min}(R) are {0, 4, 2}. Therefore, the answer is F(0) + F(4) + F(2) = 0 + 4 + 2 = 6.
Example case 4. Here values of S_{min}(R) are {0, 2, 2, 1} and values of N_{min}(R) are {0, 33, 6, 3}. Since F(33) = (3 * 3141 + 3) mod 2^{32} = 9426, the answer is F(0) + F(33) + F(6) + F(3) = 0 + 9426 + 6 + 3 = 9435.
Example case 5. Here S_{min}(R) = N_{min}(R) = R for all R from 0 to M − 1, inclusive.
Example case 6. Make sure that you calculates F(N) properly here. Also note that N_{min}(666) = 10^{106} − 1 and N_{min}(3140) = 10^{116} − 2 for M = 3141 and given sequence of weights. It means that brute force solution is not applicable even for such relatively small value of M.
Author:  anton_lunyov 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/MINWDSUM 
Tags  anton_lunyov, bfs, cook31, medium 
Date Added:  9022013 
Time Limit:  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions