Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_02_01 - Wydawanie reszty |
Bajtek pracuje w firmie informatycznej. Ostatnio, gdy ktoś kupował u nich płytę główną, spotkał go poważny problem. W kasie było mnóstwo pieniędzy każdego nominału, wręcz nieograniczona ilość. Już miał wydać klientowi resztę, gdy nagle uświadomił sobie, że nie wie jak to zrobić. Możliwości było tak dużo.. No właśnie, na tą chwilę nie ma nic bardziej istotnego niż odpowiedź na pytanie - na ile sposobów można to uczynić?
Weście
Wejście rozpoczyna się liczbą 1<=n<=10 oznaczającą ilość dostępnych nominałów. W następnej linii znajduje się n liczb (nie większych niż tysiąc) posortowanych rosnąco - są to kolejne dostępne nominały. W kolejnym wierszu podana jest liczba 1<=q<=104 oznaczająca ilość zapytań. Każde zapytanie składa się z jednej liczby 1<=r<=104.
Wyjście
Dla każdego zapytania należy wypisać w osobnej linii na ile możliwych sposobów Bajtek może wydać resztę r za pomocą dostępnych nominałów. Wynik nie przekracza 263 - 1.
Przykład
Wejście: 4
5 10 20 50
4
30
80
90
100
Wyjście: 6
31
39
49
Dodane przez: | Adam Bąk |
Data dodania: | 2012-09-29 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: GOSU |
Pochodzenie: | ALGOLIGA |
ukryj komentarze
2012-11-03 16:18:48 Adam B±k
@Adam, Na pewno poprawny? Masz wypisać na ile sposobów, więc Twoja odpowiedź dla testu: 1 5 2 1 2 jest błędna. |
|
2012-11-03 16:15:05 Adam Kuszczak
ma ktoś jakieś fajne testy na to zadanie? na duże liczby np. bo mam poprawny alg, sprawdziłem typy danych a nadal WA |
|
2012-11-03 15:19:44 Adam B±k
Odpowiem tak: liczba r w zapytaniu jest dowolną liczbą naturalną z przedziału [1; 10000] :-) |
|
2012-11-03 15:12:54 Adam Kuszczak
zawsze da się wydać reszte, tak? |
|
2012-11-03 12:30:40 Adam B±k
Nie. Nominały mogą być dowolnymi liczbami naturalnymi (nie większymi niż tysiąc). |
|
2012-11-03 12:29:21 Marcin Grudzi±z
Dostępne są tylko nominały które faktycznie istnieją? |