Fişierul intrare/ieşire:monezi2.in, monezi2.outSursăConcursul National Urmasii lui Moisil 2012, Clasa a 10-a
AutorTudose Vlad AndreiAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test0.05 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Monezi2

Aurel are N tipuri de monezi de valori v1,v2,...,vN. De fiecare dată când vrea să plăteasca o anumită sumă de bani, Aurel respectă următoarea condiţie: pentru oricare două tipuri de monezi i şi j, cu 1 ≤ i < j ≤ n, el va folosi cel puţin la fel de multe monezi de tipul i ca şi monezi de tipul j.

Cerinţă

Scrieţi un program care să-l ajute pe Aurel să verifice dacă poate plăti anumite sume de bani, respectând condiţia de mai sus.

Date de intrare

Pe prima linie a fişierului de intrare monezi2.in se află numărul natural N reprezentând numărul de tipuri de monezi. Pe următoarea linie se află numerele v1,v2,...,vN, separate prin câte un spaţiu. Pe a treia linie se află numărul Q de sume de bani pe care Aurel doreşte să le verifice dacă pot fi plătite respectând condiţia din enunţ. Pe următoarele Q linii se află numerele s1,s2,...,sQ reprezentând cele Q sume de bani, câte unul pe fiecare linie.

Date de ieşire

Fişierul de ieşire monezi2.out va conţine Q linii. Pe linia i se va afişa cuvântul DA în cazul în care suma si poate fi plătită. În caz contrar se va afişa cuvântul NU.

Restricţii

  • 1 ≤ n ≤ 50
  • 1 ≤ Q ≤ 10 000
  • 1 ≤ vi ≤ 1000
  • 1 ≤ si ≤ 100 000
  • Aurel dispune de un număr nelimitat de monezi pentru fiecare tip

Exemplu

monezi2.inmonezi2.out
2
3 5
2
14
10
DA
NU

Explicaţie

Suma 14 poate fi plătită folosind 3 monezi de tipul 1 şi o monedă de tipul 2.
Suma 10 nu poate fi plătită cu tipurile de monezi date, respectând condiţia din enunţ.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content