coins
You are given M positive integer values and one of these values is 1. You are also given an unlimited number of coins of each of these values. Consider the following problem: A certain amount of money S should be paid by a minimal number of coins with the given values. <br><br>
It is known that this problem is solvable in some cases by the following greedy algorithm: Find the greatest value of a coin that is less than or equal to S, and then subtract it from S. Continue doing the same, until the value of S becomes zero. The number of coins, which is used by the algorithm to reduce S to zero seems to be the minimal number of coins needed at all. <br><br>
In many cases the above assertion is true, but on some sets of values and for some S the greedy algorithm described above does not compute the optimal solution. For example, on a set of values {1, 2, 5, 7, 10} and for S = 14, the greedy algorithm gives a solution with 3 coins (14=10+2+2), while the obvious minimal solution is with 2 coins (14 = 7 + 7). <br><br>
A question arises – for which sets of values the greedy algorithm does not produce an optimal solution. Write a program COINS, that for a given set of coins' values should examine if there exists an amount S, which is representable by a smaller number of coins than the greedy algorithm says. <br><br>
The program has to read the data from the standard input. On the first line of the input, the number M of different coins' values is given (1 < M < 100). On the second line of the input, the values a1, a2, … , aM are given (1=a1 < a2 < … < aM <=7000000), separated by a single space. On the third line of the input two integers x and y are given (0 < x < y <= 7000000), separated by a space. <br><br>
The program should print on the first line of the standard output a value S, x <= S <= y, for which the greedy algorithm fails to give the optimal solution. On the second line, the program should print the numbers b1, b2, … , bM of coins (separated by a space), corresponding to the different values (in the same order as given in the input) to represent the amount of S, i.e. S = a1b1 + a2b2 + … + aM bM. The total number of used coins should be less than the number of coins obtained by the greedy algorithm. If there exists more than one solution, your program should print any of them. <br><br>
The input data always guarantee the presence of at least one S for which the described greedy algorithm fails. <br><br>
EXAMPLE <br><br>
Input<br>
5<br>
1 2 5 7 10<br>
1 100<br><br>
Output<br>
14<br>
0 0 0 2 0
It is known that this problem is solvable in some cases by the following greedy algorithm: Find the greatest value of a coin that is less than or equal to S, and then subtract it from S. Continue doing the same, until the value of S becomes zero. The number of coins, which is used by the algorithm to reduce S to zero seems to be the minimal number of coins needed at all. <br><br>
In many cases the above assertion is true, but on some sets of values and for some S the greedy algorithm described above does not compute the optimal solution. For example, on a set of values {1, 2, 5, 7, 10} and for S = 14, the greedy algorithm gives a solution with 3 coins (14=10+2+2), while the obvious minimal solution is with 2 coins (14 = 7 + 7). <br><br>
A question arises – for which sets of values the greedy algorithm does not produce an optimal solution. Write a program COINS, that for a given set of coins' values should examine if there exists an amount S, which is representable by a smaller number of coins than the greedy algorithm says. <br><br>
The program has to read the data from the standard input. On the first line of the input, the number M of different coins' values is given (1 < M < 100). On the second line of the input, the values a1, a2, … , aM are given (1=a1 < a2 < … < aM <=7000000), separated by a single space. On the third line of the input two integers x and y are given (0 < x < y <= 7000000), separated by a space. <br><br>
The program should print on the first line of the standard output a value S, x <= S <= y, for which the greedy algorithm fails to give the optimal solution. On the second line, the program should print the numbers b1, b2, … , bM of coins (separated by a space), corresponding to the different values (in the same order as given in the input) to represent the amount of S, i.e. S = a1b1 + a2b2 + … + aM bM. The total number of used coins should be less than the number of coins obtained by the greedy algorithm. If there exists more than one solution, your program should print any of them. <br><br>
The input data always guarantee the presence of at least one S for which the described greedy algorithm fails. <br><br>
EXAMPLE <br><br>
Input<br>
5<br>
1 2 5 7 10<br>
1 100<br><br>
Output<br>
14<br>
0 0 0 2 0
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.