El de las monedas P87919


Statement
 

pdf   zip

html

Tal vez hayáis leído alguna vez que algunos problemas son tan clásicos que apenas merecen enunciado. En éste, os pedimos que, dadas una colección de n monedas con valores distintos y una determinada cantidad C, indiquéis la manera de sumar C usando monedas del mayor valor posible. En concreto, una manera es preferible a otra si usa más monedas del valor mayor; en caso de empate, si usa más monedas del segundo mayor valor, etc. Asumid que disponéis de un número ilimitado de monedas de cada tipo.

Entrada

La entrada consiste en diversos casos. Cada caso comienza con el número de monedas n entre 1 y 100, seguido de n enteros distintos v1, …, vn, donde 1≤ vi≤ 10000. Finalmente, tenemos un entero 1≤ C≤ 100000.

Salida

Para cada caso, escribid de mayor a menor las monedas necesarias para obtener C. Escoged la combinación que use monedas de mayor valor en caso de empate. De no haber ninguna, escribid −1.

Public test cases

  • Input

    8
1 2 5 10 25 50 100 200
481

3
1 4 5
5

6
428 19 521 67 84 101
75

6
428 19 521 67 84 101
749

    Output

    200,200,50,25,5,1
5
-1
521,19,19,19,19,19,19,19,19,19,19,19,19
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++