h1. 'Problema cu becuri':problema/pcb

Construim un graf cu $N + 1$ noduri in care fiecare nod reprezinta o stare. Starea initiala este reprezentata de nodul $0$. Fiecare nod $i > 0$ va reprezenta starea in care sunt aprinse doar becurile $[0,i-1]$.
 
Pentru fiecare comutator care schimba becurile din intervalul $[a,b]$ adaugam o muchie intre nodurile
$a$ si $b+1$. Explicatia este: $a$ reprezinta becurile aprinse in intervalul $[0,a-1]$ la care se adauga
cele din intervalul $[a,b]$ si rezulta $[0,b]$, adica nodul $b+1$.
 
Deci, putem aprinde becurile $[0,X-1]$ daca exista un drum de la nodul $0$ la nodul $X$. Raspunsul la problema va fi distanta minima a unui astfel de drum, ceea ce putem afla cu o 'parcurgere in latime':problema/bfs (deoarece toate muchiile au costul $1$).
 

h1. 'Raci':problema/raci
h1. 'Suma5':problema/suma5