Aceasta problema este propusa de Alexandru Susu, un coleg de la Facultatea
de Calculatoare, careia ii multumesc inca o data foarte mult si pe aceasta
cale. Problema este foarte interesanta si destul de dificila; ea a fost
propusa la faza finala a concursului ACM din 1997.
   Rezolvarile vor fi trimise ca de obicei pe adresa rezolvari@ldc.ro

 ---------------------------------------
| PROBLEMA 29: Amestecand... amestecuri |
| PUNCTAJ: 80 Dexteri                   |
| DEADLINE: Marti, 14 Septembrie        |
| TIMP DE IMPLEMENTARE: 70 minute       |
| TIMP DE EXECUTIE: 1 sec./test         |
 ---------------------------------------

   Pentru urmatoarele 70 de minute sunteti alchimist. Pentru a gasi
piatra filosofala, aurul divin, va trebuie multa maiestrie in potrivirea
elementelor. Asadar vi se dau 3 substante generic numite A,B,C, dar nu
separate, ci amestecate, cu proportii specificate.
   Acum sa vedem un exemplu de ce inseamna maiestrie: avem 2 amestecuri,
unul care contine substanta B in proportie de 2 ori mai mare decat A, si
C in proportie de 3 ori mai mare decat A - vom nota aceasta substanta cu
proportiile 1:2:3, iar cealalta substanta cu proportiile 3:7:1 (adica
substanta A e in proportie de 3 ori mai mare decat C, iar B de 7 ori mai
mare decat C). Amestecand cele 2 solutii in proportie de 1:2 (adica la o
parte din prima substanta, punem 2 parti din a doua) obtinem un amestec
cu proportiile 7:16:5. Nu avem cum sa obtinem doar din aceste 2 substante
un amestec cu proportiile 3:4:5. Dar daca am mai avea o a treia substanta
cu proportiile 2:1:2, atunci putem obtine 3:4:5, amestecand 8 parti din
1:2:3, o parte din 3:7:1 si 5 parti din 2:1:2.
   Si cum alchimia este o stiinta precisa vrem sa aflam daca dintr-un set
de substante cu proportii date putem obtine o alta substanta cu proportii
date.

   Fisierul de intrare are numele "amestec.in". Formatul este:
   - pe prima linie contine un intreg N ce reprezinta numarul de amestecuri
     date (0<=N<100)
   - urmatoarele N linii contin cate 3 numere naturale ce reprezinta
     proportiile de substante A,B, respectiv C asa cum apar in amestec.
     Cel putin unul dintre aceste numere este nenul.
   - linia N+2 contine 3 numere naturale ce reprezinta proportiile de
     substante A,B, respectiv C ale amestecului despre care trebuie sa
     determinam daca il putem obtine din primele N amestecuri. Din nou,
     cel putin unul dintre aceste numere este nenul.

   Fisierul de iesire va avea numele "amestec.out".  Fisierul va avea 2
   octeti si va contine "DA", daca se poate obtine amestecul N+1 din primele
   N sau "NU" daca nu este posibil.

   Vor exista grupuri de 3 pana la 5 teste. Punctajul pentru un test nu va fi
obtinut decat daca sunt trecute toate testele din grupul din care face parte
testul respectiv.

   Va urez sa va distrati si la multi bani.


   Exemplul 1:

    "amestec.in"                                "amestec.out"
    2                                            NU
    1 2 3
    3 7 1
    3 4 5

   Exemplul 2:

    "amestec.in"                                "amestec.out"
    3                                           DA
    1 2 3
    3 7 1
    2 1 2
    3 4 5