Chef and Array (Challenge)

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef has an integer $K$ and a randomly generated sequence $A_1, A_2, \dots, A_N$. He asks you to choose $N$ nonnegative integers $D_1, D_2, \dots, D_N$ such that $D_i \le K$ for each valid $i$ and add $D_i$ to $A_i$ for each valid $i$. Also, Chef has $M$ primes $P_1, P_2, \dots, P_M$. It is guaranteed that for each valid $i$, $P_i$ is the smallest prime greater than $P_{i1}$. After all addition operations are performed on the sequence $A$, he finds the product of all elements of $A$ and computes its remainders modulo each prime. Let's denote these remainders by $B_1, B_2, \dots, B_M$. Please help Chef maximise $\frac{1}{M}\sum_{i=1}^M B_i$. ### Input  The first line of the input contains three spaceseparated integers $N$, $M$ and $K$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \dots, A_N$.  The third line contains $M$ spaceseparated integers $P_1, P_2, \dots, P_M$. ### Output Print a single line containing $N$ spaceseparated integers — the sequence $A_1, A_2, \dots, A_N$ obtained after performing all additions. ### Constraints  $1 \le N, M \le 10^4$  $1 \le K \le 2\cdot10^9$  $1 \le A_i, P_i \le 2\cdot10^9$ for each valid $i$  $P_i$ is the smallest prime greater than $P_{i1}$ for each valid $i$ ### Example Input4 4 5 1 2 3 4 5 7 11 13### Example Output
2 6 6 9### Explanation We can choose $D = (1, 4, 3, 5)$ — that is, we're adding $1$ to $A_1$, $4$ to $A_2$, $3$ to $A_3$ and $5$ to $A_4$. After these addition operations, $A = (2, 6, 6, 9)$. Let's calculate the sequence $B$.  $B_1 = (A_1 \cdot A_2 \cdot A_3 \cdot A_4)\;\%\; P_1 = 3$  $B_2 = (A_1 \cdot A_2 \cdot A_3 \cdot A_4)\;\%\; P_2 = 4$  $B_3 = (A_1 \cdot A_2 \cdot A_3 \cdot A_4)\;\%\; P_3 = 10$  $B_4 = (A_1 \cdot A_2 \cdot A_3 \cdot A_4)\;\%\; P_4 = 11$ The score for this output would be $(B_1 + B_2 + B_3 + B_4) / M = 28 / 4 = 7$. ### Score Your score for each test file will be the sum of all $B_i$ divided by $M$. For the above example, the score you would obtain is $7$. ### Test Generation Process There are four types of tests and five test files (test cases) of each type. During the contest, the displayed score will account for exactly one test file of each type, i.e. your score reflects your submission's performance on 20% (1/5) of the test files. However, if your program gets a nonAC verdict on any test file, your submission's verdict will be nonAC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to the sum of your program's scores over all test files. The pseudocodes used for generating tests of each type are given below. Assume the function rnd.next(l, r) generates a random number uniformly in the range $l$ through $r$ (both inclusive) and nextPrime(x) finds the smallest prime greater than $x$. **Type 1:**
INF = 1000000000 N = 100 M = 10000 K = rnd.next(1, 1000000) for i = 1 to N: A[i] = rnd.next(1, INF) X = rnd.next(INF / 10, INF / 2) + INF for i = 1 to M: P[i] = nextPrime(X) X = P[i]**Type 2:**
INF = 1000000000 N = 1000 M = 1000 K = rnd.next(1, 1000) for i = 1 to N: A[i] = rnd.next(1, INF) X = rnd.next(INF / 10, INF / 2) + INF for i = 1 to M: P[i] = nextPrime(X) X = P[i]**Type 3:**
INF = 1000000000 N = 1000 M = 1000 K = rnd.next(1, 1000000) for i = 1 to N: A[i] = rnd.next(1, INF) X = rnd.next(INF / 10, INF / 2) + INF for i = 1 to M: P[i] = nextPrime(X) X = P[i]**Type 4:**
INF = 1000000000 N = 10000 M = 100 K = rnd.next(1, 1000000) for i = 1 to N: A[i] = rnd.next(1, INF) X = rnd.next(INF / 10, INF / 2) + INF for i = 1 to M: P[i] = nextPrime(X) X = P[i]
Author:  mgch 
Editorial  https://discuss.codechef.com/problems/CHEFPAR 
Tags  april18, challenge, factorization, mgch, mgch, random, simulation 
Date Added:  2012017 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions