Wprowadzenie do zachłanności i dynamiki

18.10.2010 - Łukasz Zatorski
Trudność

Banknoty Bajtazara


Z powodu problemów z kopalniami złota i zbliżających się wydatków, król Bajtocji - Bajtazar postanowił zreformować system pieniężny. Zamiast bitych monet chce wprowadzić banknoty ze swoją podobizną i o nominałach będących jego szczęśliwymi liczbami. Zamówił już nawet specjalne matryce i maszyny drukarskie (które dostarczy mu kartel krasnoludów) oraz otrzymał spis kwot do rozdysponowania. Ze względu na to, że koszt wydrukowania każdego banknotu jest taki sam, król chciałby zaoszczędzić i użyć ich możliwie jak najmniej.

Wraz ze swoim stutysięcznym wojskiem przygotowywuje ważną wizytę dyplomatyczną dlatego poprosił Ciebie swojego osobistego doradcę o pomoc w tej sprawie. Zanim rozpocznie się wielkie drukowanie pieniędzy, król chciałby się dowiedzieć, czy każdą kwotę jest w stanie za pomocą ustalonych przez siebie nominałów dokładnie wydać (oraz w jaki sposób to zrobić).

Wejście:

W pierwszej linii wejście znajduje się dwie liczby całkowite: $ n $ - ilość nominałów $ (0<n<1000) $ i $ m $ - ilość kwot $ (0<m<1000) $. W drugiej linii wejścia jest $ n $ nominałów - liczb całkowitych z przedziału $ [1..20000] $. W trzeciej linii wejścia jest $ m $ kwot - liczb całkowitych z przedziału $ [1..20000] $.

Wyjście:

$ M $ linii wyjścia odpowiadających kolejnym kwotom:

  • jeśli danej kwoty nie da się wydać w systemie Bajtazara - napis $ NIE $
  • w przeciwnym wypadku rozkład tej kwoty wykorzystujący najmniejszą liczbę banknotów w postaci:
    $ [kwota]=[bankot_1]+[banknot_2]+[banknot_3]+...+[banknot_{ostatni}] $; banknoty wypisane są w porządku nierosnącym (patrz przykład).
W przypadku, gdy występuje więcej niż jedno rozwiązanie, należy umieścić te wykorzystujące możliwie najwyższe nominały.

Przykład:

Dla danych wejściowych:

4 6
10 5 7 2
10 11 12 13 3 14

Poprawnym wynikiem jest:

10=10
11=7+2+2
12=10+2
13=7+2+2+2
NIE
14=7+7

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.846155
Twoja ocena: Brak Ocena: 4.8 (13 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com