== include(page="template/taskheader" task_id="taieri") ==
Poveste și cerință...
Avem la dispoziție *n* 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 4 numere *a*, *b*, *c*, *d*, trebuie să decidem dacă putem obține *a* bare de lungime 1, *b* bare de lungime 2, *c* bare de lungime 4 și *d* bare de lungime 8. Odată aplicată o tăiere de lungime *L* asupra unei bare, restul poate fi în continuare folosit pentru a tăia alte bare de oricare dintre lungimile dorite.
h2. Cerință
Cunoscând *n* - numărul de bare metalice și lungimile celor *n* bare metalice avute la dispoziție, pentru fiecare din seturile de 4 numere *a b c d* date,
determinați dacă, pornind de la cele *n* lungimi date, se pot obține barele de lungimile dorite.
h2. Date de intrare
Fișierul de intrare $taieri.in$ ...
Pe prima linie a fișierului de intrare *taieri.in* se află numărul natural *n*.
Pe linia a doua se află cele *n* numere naturale ce reprezintă lungimile barelor inițiale.
Pe linia a treia se află un număr natural *m* ce reprezintă numărul de seturi de 4 numere.
Pe fiecare din următoarele *m* linii se află câte patru numere naturale *a b c d* cu semnificația de mai sus.
Numerele de pe aceeași linie sunt separate prin câte un spațiu.
h2. Date de ieșire
În fișierul de ieșire $taieri.out$ ...
Fișierul de ieșire *taieri.out* va conține *m* valori 0 și 1, separate prin câte un spațiu.
Pentru fiecare set de 4 numere, în ordinea apariției lor în fișierul de intrare, se scrie în fișierul de intrare valoarea 1, dacă se poate obține numărul dorit de bare pentru toate cele 4 lungimi din setul corespunzător, respectiv 0 în caz contrar.
h2. Restricții
h2. Restricții și precizări
* $... ≤ ... ≤ ...$
* Lungimile barelor sunt numere naturale nenule cel mult egale cu 10 000 000.
* 0 ≤ *a*; *b*; *c*; *d* ≤ 10 000 000.
* Pentru teste în valoare de 16 puncte 1 ≤ *n* ≤ 1 000, 1 ≤ *m* ≤ 1 000, iar pentru toate seturile dintr-un test avem *b* = 0, *c* = 0 și *d* = 0.
* Pentru alte teste în valoare de 28 puncte 1 ≤ *n* ≤ 1 000 și 1 ≤ *m* ≤ 1 000.
* Pentru alte teste în valoare de 56 puncte 1 ≤ *n* ≤ 1 000 000 și 1 ≤ *m* ≤ 100 000.
h2. Exemplu
h2. Exemple
table(example).
|_. taieri.in |_. taieri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. taieri.in |_. taieri.out |_. Explicații |
| 5
10 12 8 3 1
3
2 3 2 2
31 0 0 0
1 13 0 1
| 1 1 0
| *La primul set* - 2 3 2 2 trebuie obținute două bare de lungime 1,
trei bare de lungime 2, două de lungime 4 și două de lungime 8.
Putem tăia bara de lungime 10 în una de 8 și una de 2.
Avem deja a doua bară de lungime 8. Ne mai rămân astfel bare cu
lungimile: 2, 12, 3 și 1.
Cele două bare de lungime 4 le putem tăia din cea de lungime 12,
rămânându-ne bare de lungimile 2, 4, 3 și 1.
Pentru cele 3 de lungime 2 putem folosi prima bară și pe a doua o
tăiem în două bucăți, iar pe cele 4 de lungime 1 le putem obține
folosind barele cu lungimile 3 și 1 rămase.
*La al doilea set* - 31 0 0 0 putem obține din prima bară dată 10 bare
de lungime 1, din a doua 12 bare de lungime 1, din a treia
încă 8 bare de lungime 1 și mai avem ultima bară deja de lungime 1,
așadar se pot obține cele 31 de bare necesare.
Remarcați că nu a fost nevoie să folosim bara de lungime 3.
Se observă că nu este nevoie să obținem bare de lungimile 2, 4, 8.
*La al treilea set* - 1 13 0 1, oricum am tăia barele avute
la dispoziție,nu putem obține întreg setul format din:
o bară de lungime 1, 13 bare de lungime 2 și o bară de lungime 8.
|
== include(page="template/taskfooter" task_id="taieri") ==
