Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

Zadanie: Banknoty


Bajtocki Bank Bitowy (w skrócie BBB) ma największą w Bajtocji sieć bankomatów. BBB postanowił usprawnić swoje bankomaty i zwrócił się do Ciebie o pomoc. Środkiem płatniczym w Bajtocji są banknoty o nominałach b1, b2,..., bn. BBB postanowił, że bankomaty powinny wypłacać żądaną kwotę w jak najmniejszej łącznej liczbie banknotów.

Zadanie

Napisz program, który:
  • wczyta ze standardowego wejścia opis zapasu banknotów, które posiada bankomat, oraz kwotę do wypłacenia,
  • obliczy minimalną łączną liczbę banknotów, za pomocą jakiej bankomat może wypłacić żądaną kwotę, oraz znajdzie pewien sposób jej wypłacenia,
  • wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się liczba nominałów n, 1 <= n <= 200. Drugi wiersz zawiera n liczb całkowitych b1, b2,..., bn, 1 <= b1 < b2 < ... < b n <= 20 000, pooddzielanych pojedynczymi odstępami. Trzeci wiersz zawiera n liczb całkowitych c1, c2,..., cn, 1 <= ci <= 20 000, pooddzielanych pojedynczymi odstępami; ci jest liczbą banknotów o nominale bi znajdujących się w bankomacie. W ostatnim, czwartym wierszu wejścia znajduje się jedna liczba całkowita k -- kwota, którą bankomat ma wypłacić, 1 <= k <= 20 000. Możesz założyć, dla danych testowych, że kwotę k można wypłacić za pomocą dostępnych banknotów.

Wyjście

Pierwszy wiersz wyjścia powinien zawierać jedną dodatnią liczbę całkowitą równą minimalnej łącznej liczbie banknotów, za pomocą których bankomat może wypłacić kwotę k. Drugi wiersz wyjścia powinien zawierać n liczb całkowitych, oddzielonych pojedynczymi odstępami i oznaczających liczby sztuk poszczególnych banknotów użytych do wypłacenia kwoty k. W przypadku, gdy istnieje więcej niż jedno rozwiązanie, program powinien wypisać którekolwiek.





Wersja do druku