== include(page="template/taskheader" task_id="combl") ==
Fie $S$ o multime de perechi $(a,b)$ de numere naturale. $S = {(a{~1~},b{~1~}), (a{~2~},b{~2~}), (a{~3~},b{~3~}), ...}$
Spunem ca o pereche $(x,y)$ este *S-compatibila* daca se poate scrie ca _combinatie liniara_ a perechilor din $S$ cu coeficienti din *[0, 1]*.
Mai exact perechea $(x,y)$ este $S-compatibila$ daca exista coeficientii reali $c{~1~}$, $c{~2~}$, ..., $c{~N~}$ apartinand intervalului $[0, 1]$ astfel incat
* $x = c{~1~} * a{~1~} + c{~2~} * a{~2~} + c{~3~} * a{~3~} + ... + c{~N~} * a{~N~}$
* $y = c{~1~} * b{~1~} + c{~2~} * b{~2~} + c{~3~} * b{~3~} + ... + c{~N~} * b{~N~}$
unde $(a{~1~},b{~1~})$, $(a{~2~},b{~2~})$, $(a{~3~},b{~3~})$, ..., $(a{~N~},b{~N~})$ sunt perechile din $S$.
Pornind de la o multime S initial vida trebuie sa puteti suporta urmatoarele operatii:
* $Insert (a,b)$ - se insereaza perechea $(a,b)$ in $S$
* $Erase (a,b)$ - se sterge perechea $(a,b)$ din $S$
* $Query (x,y)$ - se verifica daca perechea $(x,y)$ este $S-compatibila$
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $combl.in$ va contine pe prima linie un singur numar natural $Q$ reprezentand numarul de operatii ce trebuiesc executate.
Urmatoarele $Q$ linii vor descrie fiecare cate o operatie, astfel
* Daca primul numar de pe linie este egal cu $1$ operatia descrisa este o operatie de tip $Insert$. Dupa numarul $1$ vor urma $2$ numere naturale $a$ si $b$ reprezentand perechea ce va fi adaugata multimii $S$.
* Daca primul numar de pe linie este egal cu $2$ operatia descrisa este o operatie de tip $Erase$. Dupa numarul $2$ vor urma $2$ numere naturale $a$ si $b$ reprezentand perechea ce va fi stearsa din multimea $S$.
* Daca primul numar de pe linie este egal cu $3$ operatia descrisa este o operatie de tip $Query$. Dupa numarul $3$ vor urma $2$ numere naturale $x$ si $y$ reprezentand perechea pentru care se interogheaza daca este $S-compatibila$ sau nu.
Fişierul de intrare $combl.in$ ...
h2. Date de ieşire
În fişierul de ieşire $combl.out$ trebuie sa se gaseasca tot atatea linii cate operatii de tip $Query$ au fost in fisierul de intrare $combl.in$.
Astfel, pe linia a $i$-a din fisierul de iesire trebuie sa se gaseasca cuvantul $"DA"$ (fara ghilimele) daca perechea $(x,y)$ de la a $i$-a operatie de tip $Query$ era $S-compatibila$ cu multimea $S$ de la momentul respectiv sau $"NU"$ (fara ghilimele) in caz contrar.
În fişierul de ieşire $combl.out$ ...
h2. Restricţii
* $1 ≤ Q ≤ 150.000$
* $0 ≤ numarul de operatii de tip *Insert* ≤ 50.000$
* $1 ≤ a{~i~}, b{~i~} ≤ 10.000$
* $0 ≤ x, y ≤ 1.500.000.000$
* $Perechile de la operatiile de tip *Insert* sunt diferite doua cate doua$
* $Orice operatie de tip *Erase* este valida, mai exact nu va exista operatie de sterge a unei perechi *(a,b)* daca perechea *(a,b)* nu face parte din S$
* $Orice operatie de tip *Query* este valida, mai exact oricand va aparea o astfel de operatie multimea S va fi nevida$
* $Pentru teste in valoare de *20* de puncte nu vor fi decat *2* operatii de tip *Insert* in fisierul de intrare$
* $Pentru alte teste in valoare de *40* de puncte $Q$ ≤ 3.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. combl.in |_. combl.out |
| 9
1 1 2
1 2 1
3 2 2
2 1 2
3 2 2
1 1 3
1 4 2
3 0 3
3 5 4
| DA
NU
NU
DA|
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
* La prima operatie de tip $Query$ multimea $S$ este formata din perechile $(1,2)$ si $(2,1)$.
Putem obtine perechea $(2,2)$ ca
** $x = *2/3* * 1 + *2/3* * 2 = 2$
** $y = *2/3* * 2 + *2/3* * 1 = 2$
* La a doua operatie de tip $Query$ multimea $S$ este formata doar din perechea $(2,1)$. Nu putem obtine $(2,2)$ in niciun fel.
* La a treia operatie de tip $Query$ multimea $S$ este formata din perechile $(2,1)$, $(1,3)$ si $(4,2)$. Pentru a obtine $x = 0$ trebuie ca toti coeficientii $c$ sa fie egali cu $0$, deci si $y$ ar trebui sa fie egal cu $0$, insa noi avem nevoie de $y = 3$.
* La a patra operatie de tip $Query$ multimea $S$ este formata din perechile $(2,1)$, $(1,3)$ si $(4,2)$.
Putem obtine perechea $(5,4)$ ca
** $x = *0.2* * 2 + *0.6* * 1 + *1* * 4 = 0.4 + 0.6 + 4 = 5$
** $y = *0.2* * 1 + *0.6* * 3 + *1* * 2 = 0.2 + 1.8 + 2 = 4$
...
== include(page="template/taskfooter" task_id="combl") ==
