winter-challenge-2008/runda-2/solutii/sn

winter-challenge-2008/runda-2/solutii#sn

h1. Siguranta Nationala

h2(#sn). 'Siguranta Nationala':problema/sn

Problema se rezolva prin metoda Greedy. Se parcurge in ordinea crescatoare a capetelor stanga tinand $2$ variabile $Rss$ si $Rsa$:

La pasul $i$ avem urmatoarele cazuri (presupunem ca $Rss ≤ Rsa$):
# {$B{~i~}$} ≤ $Rss$, in acest caz nu conteaza de ce tip va fi considerat intervalul $i$, deoarece toate punctele din $[1,{$B{~i~}$}]$ au fost acoperite anterior

# {$B{~i~}$} > $Rss$, in acest caz intervalul va fi de tip 'sol-aer', iar $Rss$ va primi valoarea {$B{~i~}$}.

# {$B{~i~}$} > $Rss$, in acest caz intervalul va fi de tip 'sol-aer', iar $Rsa$ va primi valoarea {$B{~i~}$}.

Din pacate limitare memoriei facea imposibila stocarea intervalelor. Din fericie ele era deja sortate, deci se puteau preprocesa pe parcursul citirii. De asemenea, cand se stabilea tipul unui interval se afisa in fisierul de iesire.

Din pacate limitare memoriei facea imposibila stocarea intervalelor. Din fericire ele erau deja sortate, deci se puteau preprocesa pe parcursul citirii. De asemenea, cand se stabilea tipul unui interval se afisa in fisierul de iesire.

Astfel algoritmul foloseste $O(1)$ memorie si are complexitatea $O(n)$.