Water In Jars
All submissions for this problem are available.You are given $N$ jars numbered from $1$ to $N$. Initially, all jars are empty. Each jar is capable of holding infinite quantity of water. You are given $N$ integers (represented by $A$i, *1<=i<=N*) denoting the minimum quantity of water in litres which needs to be at least present in each of the respective jars (from $1$ to $N$). You are also given a drum containing $X$ litres of water. You need to find out the number of ways of distributing $X$ litres of water in given $N$ jars such that the given conditions are satisfied or find out if it is impossible. $Note$: *A jar can only contain integer litres of water. Fractions are not allowed.* You are given $Q$ queries. In each query, $X$ is given and you have to print the answer. Since the answer can be very large, print answer modulo $1000000007$ (modulo refers to %). Print "$-1$" (without quotes) if it is impossible to distribute $X$ litres of water satisfying the given conditions. ###Input: - First line contains two space separated integers $N$ denoting the number of jars and $Q$ denoting the number of queries. - Second line contains $N$ integers represented by $A$i (*1<=i<=N*) denoting the minimum quantity of water in litres which needs to be at least present in each of the respective jars. - Next $Q$ lines contain a single integer $X$ denoting the quantity of water in litres in the drum. ###Output: Print $Q$ integers denoting the answer to each query in a separate line. ###Constraints - $1 \leq N \leq 100000$ - $1 \leq Q \leq 100000$ - $1 \leq X \leq 100000$ - $0 \leq Ai \leq 100000$ ###Subtasks - 20 points : $1 \leq N \leq 2$ - 80 points : $Original Constraints$ ###Sample Input: 2 3 0 2 2 3 1 ###Sample Output: 1 2 -1 ###EXPLANATION: - For $1st$ query, there is only one possible configuration, i.e., $[0, 2]$. - For $2nd$ query, possible configurations include $[0, 3]$ and $[1, 2]$. - For $3rd$ query, no configuration is possible.
|Time Limit:||1 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.