Diferente pentru problema/cabine intre reviziile #1 si #7

Diferente intre titluri:

cabine
Cabine

Diferente intre continut:

== include(page="template/taskheader" task_id="cabine") ==
Poveste şi cerinţă...
Pe strada Anurim exista $N$ cabine telefonice asezate una langa alta. Vom numerota aceste cabine de la $1$ la $N$ incepand cu cea mai din stanga. La un moment dat o parte din cabine sunt ocupate, iar celelalte cabine urmeaza sa fie ocupate. In fiecare secunda soseste o noua persoana care doreste sa vorbeasca la telefon. Strategia folosita de fiecare dintre cei care urmeaza sa-si aleaga o cabina este urmatoarea:
 
# Se alege cabina pentru care timpul petrecut pana cand se ocupa ambele cabine vecine este cat mai mare.
# In cazul in care exista mai multe cabine care satisfac relatia 1, se alege cabina cea mai din stanga.
 
Pentru a determina cabinele care satisfac conditia 1, fiecare persoana se foloseste de faptul ca cei care urmeaza sa soseasca vor folosi aceeasi strategie.
 
Dandu-se configuratia initiala de cabine si un numar $K$, trebuie sa aflati indicele cabinei alese de a $K$-a persoana.
h2. Date de intrare
Fişierul de intrare $cabine.in$ ...
Pe prima linie a fisierului de intrare $cabine.in$ se gasesc doua numere naturale $N$ si $K$. Pe cea de a doua linie se vor gasi $N$ numere avand valori din multimea {0, 1}. In cazul in care cabina cu indicele $i$ este libera cel de al $i$-lea numar va fi $0$, altfel va fi $1$.
h2. Date de ieşire
În fişierul de ieşire $cabine.out$ ...
Fisierul de iesire $cabine.out$ va contine un singur numar natural reprezentand indicele cabinei alese de cea de a $K$-a persoana.
h2. Restricţii
h2. Restrictii si precizari
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100000$
* $1 ≤ K ≤ numarul de cabine libere$
* Pentru $30%$ din teste $1 ≤ N ≤ 15$
* Niciunul dintre ocupantii cabinelor nu termina de vorbit la telefon pana cand nu se ocupa toate cabinele.
h2. Exemplu
table(example). |_. cabine.in |_. cabine.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 5 3
1 0 0 0 0
| 2
|
h3. Explicaţie
...
Prima persoana care soseste va alege cabina $5$ deoarece aceasta nu se va afla niciodata intre doua cabine ocupate.
Daca a doua persoana ar alege cabina $2$, atunci a treia persoana ar alege cabina $3$, deci ar dura o secunda pana cand cabina $2$ s-ar afla intre doua cabine ocupate. In schimb daca a doua persoana ar alege una din cabinele $3$ si $4$, a treia persoana ar alege cabina $2$, deci ar dura doua secunde pana cand cabina aleasa de a doua persoana s-ar afla intre doua cabine ocupate. In concluzie, a doua persoana va alege cabina $3$, deoarece are indicele mai mic decat cabina $4$.
Cea de a treia persoana va avea de ales intre cabinele $2$ si $4$, amandoua aflandu-se deja intre doua cabine ocupate. O va alege pe cea cu indicele mai mic.
== include(page="template/taskfooter" task_id="cabine") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
4541