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.
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
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.
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
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.
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 ș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.
* 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. Exemple
table(example).
|_. 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 1
| *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.
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.
*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") ==
