*Aceasta pagina trebuie sa ramana private pana la finalul concursului.*

h1(#cabine). 'Cabine':problema/cabine
 
Vom incerca sa gasim ordinea in care vor fi ocupate cabinele. Ne vom folosi de urmatoarea strategie greedy:
 
* Prima si ultima cabina vor fi intotdeauna alese la inceput, deoarece ele nu se vor afla niciodata intre alte doua cabine ocupate.
* In cazul in care nu exista doua cabine libere adiacente, fiecare persoana care soseste va alege cabina cu indicele cel mai mic.
* Daca exista cel putin doua cabine adiacente, prima persoana care soseste va alege cabina cu indicele cel mai mare pentru care cabina vecina din dreapta este la randul ei libera. Demonstratie: In continuare vom considera ca aceasta cabina are indicele $P$. Fie $X$ numarul de cabine libere din stanga lui $P$. Cabina $P+1$ va fi ocupata dupa cele $X$ aflate la stanga, deci cabina $P$ va avea cel putin un vecin liber timp de $X+1$ secunde. Acelasi timp se obtine si pentru cabina $P+1$, dar aceasta are indicele mai mare. Daca ar fi fost aleasa o cabina cu indice mai mic decat $P$, s-ar fi obtinut un timp mai mic decat $X+1$.
 
Cunoscand aceasta strategie, putem sa simulam modul in care sunt alese cabinele folosind doua parcurgeri ale sirului de intrare.

private

public