We provide counterexemples for both data sets (i.e. both incorrect programs) and we also provide correct algorithm for solving the problem of little John.

First, let us see how the algorithm implemented in the easy data set
works. Function **payClassic** takes the price **V**
and finds the coin with highest value not higher than **V**. It
decides to use this coins for paying, subtracts its value from **V**
and tries to pay the rest in the same way. Counterexample can be for
example following input:

0 3 1 0 0 0 0 0 0 0 6

John has to pay 6 TD and he has 3 coins of value 2 TD and 1 coin of value 5
TD. Clearly it is possible to pay the amount using 3 coins of value 2 TD.
Function **payClassic** first uses 5 TD coin. Now it is
necessary to pay 1 TD. But it is not possible to pay 1 TD using 2 TD coins.
Thus the function output -1.

The algorithms in the difficult data set tries to patch this problem
somehow. It computes several different solutions and finds best of these
solutions. First, it computes the solution given by **payClassic**.
All considered solutions are such that they contain several coins of the
same value and the rest of the price is payed by **payClassic**.
However the set of solutions considered in this algorithm does not always
contain the best solution.

For counterexample given above this algorithm works correctly. Solution consists of 3 coins of the same value and therefore it is among solutions computed in this algorithm. Let us consider following input:

0 3 1 0 3 1 0 0 0 0 66

The only solution for this input contains 3 coins of value 2 TD and 3
coins of value 20 TD. Function **payClassic** uses first 50 TD coin,
then 5 TD coin and then 3 coins of value 2 TD. There remains 5 TD to pay
but there are only three 20 TD coins. The algorithm in difficult data set
tries to use several coins of the same value first. The partial solution
produced by **payClassic** contains all coins except 20 TD coins.
Therefore all computes solutions in which 20 TD coins is not used are the
same. When the program tries to use 20 TD coins first, it pays 60 TD and it
has to pay 6 TD using 5 TD coin and 3 2 TD coins. This is done by
**payClassic** function which does not find a solution. Therefore this
input is counterexample for algorithm given in C2.

John's problem can be solved correctly by
dynamic programming. Suppose that John has **N** coins. We will
compute for each **i**=0,1,2,..,**N** and for each
**j**=0,1,2,...,**V** the smallest number of coins need for
paying price **j** if we can use only first **i** of John's
coins. More precisely we compute whether it is possible at all to pay
**j** using only the first **i** coins and only if it is possible
we compute the smallest number of coins needed.

If we know these values for some **i**, we can easily obtain values
for **i+1**. If we want to pay value **j** using first
**i+1** coins, we can either use the (**i+1**)-th coin or not. If
we do not use this coin, the best solution is the same as using only the
first **i** coins. Now let us suppose that we use the (**i+1**)-th
coin and that the value of this coin is **k**. Then the rest of the
price is payed by the best solution for the first **i** coins and
price **j-k**. If **a[i][j]** is the best solution for first
**i** coins and prize **j**, we have

The formula given above is simplified because it does not take
into account possibility that for some values of **i** and **j**
the problem does not have any solution. Moreover the formula is valid only
for **j>=k**. However when we handle these two exceptions, we get
the correct algorithms. Its time complexity is **O(NV)** that can be
further improved to **O(V** log **N)** if we process all the
coins of the same value at the same time (this improvement is not
implemented in the given program).