Little Elephant and Colored Coins
All submissions for this problem are available.
The Little Elephant from the Zoo of Lviv very likes coins. But most of all he likes colored coins.
He has N types of coins, numbered from 1 to N, inclusive. The coin of the i-th type has the value Vi dollars and the color Ci. Note that he has infinite supply of each type of coins.
The Little Elephant wants to make exactly S dollars using the coins. What is the maximal number of different colors he can use to make exactly S dollars using some of the coins he has? If it's impossible, output -1. Also note that the Little Elephant wants to know this for many values of S.
The first line of the input contains a single integer N, denoting the number of types of coins. Each of the following N lines contains two space-separated integers Vi and Ci, denoting the value and the color of the coin of the i-th type. The next line contains a single integer Q, denoting the number of values of S to process. Each of the following Q lines contains a single integer S, denoting the coinage you should represent via given coins using maximum number of colors.
For each value of S in the input, output the maximum number of different colors in the representation of S or -1 if it is impossible to represent S via given coins.
- 1 ≤ N ≤ 30
- 1 ≤ Vi ≤ 200000 (2 * 105)
- 1 ≤ Ci ≤ 109
- 1 ≤ Q ≤ 200000 (2 * 105)
- 1 ≤ S ≤ 1018
Input: 3 2 1 3 4 4 4 4 1 3 5 7 Output: -1 1 2 2
- It is not possible to represent S = 1 since every coin has value more than 1.
- S = 3 can only be represented using one coin of the second type, hence only one color is used in the representation.
- S = 5 can only be represented as 2 + 3, which leads to two colors used.
- For S = 7 we have two representations as 2 + 2 + 3 (with two colors used) and 3 + 4 (with one color used). Hence, the answer is 2.
|Tags||dynamic-programming, hard, march13, shortest-path, simple-math, witua|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.