== include(page="template/taskheader" task_id="beculete") ==
Poveste și cerință...
!>problema/beculete?beculete.png!
Ion și-a cumpărat o instalație de beculețe de Crăciun. Ea are forma unei rețele triunghiulare cu latura de $N$ beculețe. Fiecare beculeț este conectat cu două beculețe de pe linia anterioară, cu excepția beculețelor de la capetele unei linii, care sunt conectate doar cu un beculeț de pe linia anterioară. Când este pusă în priză, instalația se aprinde după următoarele reguli:
* Beculețul de pe prima linie se aprinde garantat.
* Primul beculeț de pe o linie se aprinde dacă primul beculeț de pe linia anterioară este aprins.
* Similar, ultimul beculeț de pe o linie se aprinde dacă ultimul beculeț de pe linia anterioară este aprins.
* Celelalte beculețe se aprind dacă exact unul din cele două beculețe cu care sunt conectate pe linia anterioară este aprins.
În rețea există beculețe defecte. Unele nu se aprind niciodată, iar altele stau mereu aprinse, fără a respecta regulile de mai sus. În figură, pe linia a 4-a se află un beculeț stins permanent și unul aprins permanent.
Cunoscând mărimea rețelei și amplasarea beculețelor defecte, Ion se întreabă ce configurație se formează pe ultima linie a rețelei.
h2. Date de intrare
Fișierul de intrare $beculete.in$ ...
Fișierul de intrare $beculete.in$ conține pe prima linie numerele $N$ și [$D$], separate printr-un spațiu. Ele reprezintă latura rețelei, respectiv numărul de beculețe defecte. Pe următoarele $D$ linii se găsesc tripleți $L C V$, indicând că pe linia $L$ al [$C$]-lea beculeț este defect. El este permanent stins dacă $V = 0$, respectiv permanent aprins dacă $V = 1$.
h2. Date de ieșire
În fișierul de ieșire $beculete.out$ ...
În fișierul de ieșire $beculete.out$ se vor afișa $N$ numere de 0 și 1, reprezentând starea beculețelor de pe ultima linie a rețelei, de la stânga la dreapta. Un beculeț stins este indicat prin valoarea 0, iar unul aprins prin valoarea 1.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 50.000$
* $1 ≤ D ≤ 10.000$
* Pentru fiecare defect, $2 ≤ L ≤ N$, $1 ≤ C ≤ L$ și $V ∈ {0, 1}$
* Beculețele defecte apar în fișierul de intrare ordonate după linie, apoi după coloană.
h2. Exemplu
table(example).
|_. beculete.in |_. beculete.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|_. beculete.in |_. beculete.out |_. Explicație |
| 5 2
4 1 0
4 3 1
| 0 1 0 0 1
| Vezi figura.
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="beculete") ==
