h3. (problema grea, clasa a 9-a, problema usoara, clasa a 10-a)

Putem considera $N$ puncte coliniare {$A{~1~}$}, {$A{~2~}$}... {$A{~N~}$}. Problema cere, daca cunoastem lungimile a exact $M$ segmente, sa determinam lungimea segmentului {$A{~X~}$}{$A{~Y~}$}. O rezolvare {$O(N^3^)$} nu este dificil de gasit. Vom afla lungimea tuturor segmentelor care se pot forma. Vom retine intr-o coada toate acele segmente carora le stim lungimea. Initial, in coada se afla doar cele $M$ segmente. Cand suntem pe un element in coada si vrem sa aflam ce noi segmente putem introduce, iteram un punct "de rupere" {$K$}. Sa presupunem ca stim lungimea segmentului {$A{~i~}A{~j~}$}. Distingem urmatoarele cazuri:

Putem considera $N$ puncte coliniare. Problema cere, daca cunoastem lungimile a exact $M$ segmente, sa determinam lungimea segmentului {$XY$}. O rezolvare {$O(N^3^)$} nu este dificil de gasit. Vom afla lungimea tuturor segmentelor care se pot forma. Vom retine intr-o coada toate acele segmente carora le stim lungimea. Initial, in coada se afla doar cele $M$ segmente. Cand suntem pe un element in coada si vrem sa aflam ce noi segmente putem introduce, iteram un punct "de rupere" {$K$}. Sa presupunem ca stim lungimea segmentului {$A{~i~}A{~j~}$}. Distingem urmatoarele cazuri:

* {$K < i$} si stim lungimea segmentului {$A{~K~}A{~i~}$} => inseram in coada segmentul {$A{~K~}A{~j~}$} cu lungimea egala cu suma lungimilor segmentelor {$A{~K~}A{~i~}$} si {$A{~i~}A{~j~}$}
* {$i < K < j$}

** stim lungimea segmentului {$A{~K~}A{~j~}$} => inseram in coada segmentul {$A{~i~}A{~K~}$} cu lungimea egala cu diferenta dintre lungimilor segmentelor {$A{~i~}A{~j~}$} si {$A{~K~}A{~j~}$}
* {$K > j$} si stim lungimea segmentului {$A{~j~}A{~K~}$} => inseram in coada segmentul {$A{~i~}A{~K~}$} cu lungimea egala cu suma lungimilor segmentelor {$A{~i~}A{~j~}$} si {$A{~j~}A{~K~}$}

Daca in final segmentul {$A{~X~}A{~Y~}$} a fost inserat in coada, atunci afisam lungimea acestuia.
 
Rezolvarea {$O(N+M)$} se bazeaza pe faptul ca nu avem nevoie sa stim lungimile tuturor segmentelor, ci doar a celor care au unul din capete punctul {$A{~X~}$}. Notam cu {D{~i~}} lungimea segmentului {$A{~X~}A{~i~}$}. Fiecare punct va fi identificat printr-un nod intr-un graf. Lungimea unui segment va fi lungimea muchiei intre intre doua noduri. Acum putem aplica o parcurgere BF din nodul $X$ si respectam toate cazurile care apar. In final, in {D{~Y~}} se afla lungimea segmentului {$A{~X~}A{~Y~}$}.
 

Daca in final segmentul XY a fost inserat in coada, atunci afisam lungimea acestuia.

h2. 'Branza':problema/branza