Diferente pentru problema/pcb intre reviziile #2 si #9

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="pcb") ==
Poveste şi cerinţă...
_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.
h2. Date de intrare
Fişierul de intrare $pcb.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $pcb.out$ ...
Î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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$
* $1 ≤ X ≤ N$
* $1 ≤ A[i] ≤ B[i] ≤ N$
h2. Exemplu
table(example). |_. pcb.in |_. pcb.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 5 3 4
1 3
3 4
3 3
| 3
|
h3. Explicaţie
...
Folosind câte o singură dată fiecare comutator se pot aprinde toate becurile din intervalul [1, 4].
== include(page="template/taskfooter" task_id="pcb") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
10156