taieri

Time limit: 0.2s Memory limit: 64MB Input: taieri.in Output: taieri.out

Avem la dispoziție nn 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 aa, bb, cc, dd, trebuie să decidem dacă putem obține aa bare de lungime 11, bb bare de lungime 22, cc bare de lungime 44 și dd bare de lungime 88. Odată aplicată o tăiere de lungime LL asupra unei bare, restul poate fi în continuare folosit pentru a tăia alte bare de oricare dintre lungimile dorite.

Cerință

Cunoscând nn - numărul de bare metalice și lungimile celor nn bare metalice avute la dispoziție, pentru fiecare din seturile de patru numere a b c da \ b \ c \ d date, determinați dacă, pornind de la cele nn 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 nn. Pe linia a doua se află cele nn numere naturale ce reprezintă lungimile barelor inițiale. Pe linia a treia se află un număr natural mm ce reprezintă numărul de seturi de patru numere. Pe fiecare din următoarele mm linii se află câte patru numere naturale a b c da \ b \ c \ d 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 mm valori 00 și 11, 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 11, dacă se poate obține numărul dorit de bare pentru toate cele patru lungimi din setul corespunzător, respectiv 00 în caz contrar.

Restricții și precizări

  • Lungimile barelor sunt numere naturale nenule cel mult egale cu 10 000 00010 \ 000 \ 000.
  • 0a,b,c,d10 000 0000 \leq a, b, c, d \leq 10 \ 000 \ 000;
# Punctaj Restricții
1 16 n,m1 000n, m \leq 1 \ 000 și b=c=d=0b = c = d = 0
2 28 n,m1 000n, m \leq 1 \ 000
3 56 n,m100 000n, m \leq 100 \ 000

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 – 2 3 2 22 \ 3 \ 2 \ 2 trebuie obținute două bare de lungime 11, trei bare de lungime 22, două de lungime 44 și două de lungime 88. Putem tăia bara de lungime 1010 în una de 88 și una de 22. Avem deja a doua bară de lungime 88. Ne mai rămân astfel bare cu lungimile: 22, 1212, 33 și 11. Cele două bare de lungime 44 le putem tăia din cea de lungime 1212, rămânându-ne bare de lungimile 22, 44, 33 și 11. Pentru cele 33 de lungime 22 putem folosi prima bară și pe a doua o tăiem în două bucăți, iar pe cele 44 de lungime 11 le putem obține folosind barele cu lungimile 33 și 11 rămase.

La al doilea set – 31 0 0 031 \ 0 \ 0 \ 0 putem obține din prima bară dată 1010 bare de lungime 11, din a doua 1212 bare de lungime 11, din a treia încă 88 bare de lungime 11 și mai avem ultima bară deja de lungime 11, așadar se pot obține cele 3131 de bare necesare. Remarcați că nu a fost nevoie să folosim bara de lungime 33. Se observă că nu este nevoie să obținem bare de lungimile 22, 44, 88.

La al treilea set – 1 13 0 11 \ 13 \ 0 \ 1, oricum am tăia barele avute la dispoziție, nu putem obține întreg setul format din: o bară de lungime 11, 1313 bare de lungime 22 și o bară de lungime 88.

Log in or sign up to be able to send submissions!