Avem la dispoziție bare metalice cu aceeași grosime, dar lungimi diferite. Putem alege oricare bară și să o tăiem, obținând alte două bare de lungimi mai mici. Ne dorim ca, folosind doar această operație (deci fără să le putem suda), să obținem un număr de bare de anumite lungimi date. Mai exact, dându-se un set de patru numere , , , , trebuie să decidem dacă putem obține bare de lungime , bare de lungime , bare de lungime și bare de lungime . Odată aplicată o tăiere de lungime asupra unei bare, restul poate fi în continuare folosit pentru a tăia alte bare de oricare dintre lungimile dorite.
Cerință
Cunoscând - numărul de bare metalice și lungimile celor bare metalice avute la dispoziție, pentru fiecare din seturile de patru numere date, determinați dacă, pornind de la cele lungimi date se pot obține barele de lungimile dorite.
Date de intrare
Fișierul de intrare taieri.in
conține pe prima linie numărul natural . Pe linia a doua se află cele numere naturale ce reprezintă lungimile barelor inițiale. Pe linia a treia se află un număr natural ce reprezintă numărul de seturi de patru numere. Pe fiecare din următoarele linii se află câte patru numere naturale cu semnificația de mai sus. Numerele de pe aceeași linie sunt separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire taieri.out
va conține valori și , separate prin câte un spațiu. Pentru fiecare set de patru numere, în ordinea apariției lor în fișierul de intrare, se scrie în fișierul de ieșire valoarea , dacă se poate obține numărul dorit de bare pentru toate cele patru lungimi din setul corespunzător, respectiv în caz contrar.
Restricții și precizări
- Lungimile barelor sunt numere naturale nenule cel mult egale cu .
- ;
# | Punctaj | Restricții |
---|---|---|
1 | 16 | și |
2 | 28 | |
3 | 56 |
Exemplu
taieri.in
5
10 12 8 3 1
3
2 3 2 2
31 0 0 0
1 13 0 1
taieri.out
1 1 0
Explicație
La primul set – trebuie obținute două bare de lungime , trei bare de lungime , două de lungime și două de lungime . Putem tăia bara de lungime în una de și una de . Avem deja a doua bară de lungime . Ne mai rămân astfel bare cu lungimile: , , și . Cele două bare de lungime le putem tăia din cea de lungime , rămânându-ne bare de lungimile , , și . Pentru cele de lungime putem folosi prima bară și pe a doua o tăiem în două bucăți, iar pe cele de lungime le putem obține folosind barele cu lungimile și rămase.
La al doilea set – putem obține din prima bară dată bare de lungime , din a doua bare de lungime , din a treia încă bare de lungime și mai avem ultima bară deja de lungime , așadar se pot obține cele de bare necesare. Remarcați că nu a fost nevoie să folosim bara de lungime . Se observă că nu este nevoie să obținem bare de lungimile , , .
La al treilea set – , oricum am tăia barele avute la dispoziție, nu putem obține întreg setul format din: o bară de lungime , bare de lungime și o bară de lungime .