Fişierul intrare/ieşire:beculete.in, beculete.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Beculețe (clasele 9-10)

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.

Date de intrare

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.

Date de ieşire

Î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.

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ă.

Exemplu

beculete.inbeculete.outExplicaţie
5 2
4 1 0
4 3 1
0 1 0 0 1
Vezi figura.
Trebuie sa te autentifici pentru a trimite solutii. Click aici