| Fişierul intrare/ieşire: | cabine.in, cabine.out | Sursă | Algoritmiada 2010, Runda 3 |
| Autor | Andrei Grigorean | Adăugată de |  Andrei Grigorean •wefgef |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cabine
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.
Date de intrare
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.
Date de ieşire
Fisierul de iesire cabine.out va contine un singur numar natural reprezentand indicele cabinei alese de cea de a K-a persoana.
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.
Exemplu
| cabine.in | cabine.out |
|---|---|
| 5 3 1 0 0 0 0 | 2 |
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.
