Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pcb.in, pcb.out | Sursă | Infoarena Monthly 2014, Runda 9 |
| Autor | Radu Stefan Voroneanu | Adăugată de |  Teodor Plop •Teodor94 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Problema cu becuri
Nu este doar o pură întâmplare... Antonio chiar s-a gândit la becuri când a conceput această problemă.
Antonio are un şir de N becuri, numerotate de la 1 la N. Iniţial, toate becurile sunt stinse. El are la dispoziţie M comutatoare cu care poate stinge sau aprinde anumite becuri după bunul său plac. Comutatorul i schimbă starea becurilor din intervalul [ A[i], B[i] ] (becurile stinse din acest interval se aprind, iar cele aprinse se sting).
Antonio doreşte să aprindă toate becurile din intervalul [1, X], printr-un număr minim de apăsări ale comutatoarelor pe care le are la dispoziţie. Să se afişeze acest număr minim de apăsări! Dacă acest lucru este imposibil, se va afişa -1.
Date de intrare
Fişierul de intrare pcb.in conţine pe prima linie trei numere naturale N M X, separate între ele prin câte un spaţiu. Pe fiecare linie i din următoarele M linii, se vor găsi două numere naturale A[i] B[i], separate între ele prin câte un spaţiu.
Date de ieşire
În fişierul de ieşire pcb.out se va găsi un singur număr natural, reprezentând numărul minim de apăsări ale comutatoarelor pentru a aprinde toate becurile din intervalul [1, X]. Dacă nu se pot aprinde toate becurile din intervalul [1, X], se va afişa -1.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 200.000
- 1 ≤ X ≤ N
- 1 ≤ A[i] ≤ B[i] ≤ N
Exemplu
| pcb.in | pcb.out |
|---|---|
| 5 3 4 1 3 3 4 3 | 3 |
Explicaţie
...
