Fişierul intrare/ieşire:cabine.in, cabine.outSursăAlgoritmiada 2010, Runda 3
AutorAndrei GrigoreanAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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:

  1. Se alege cabina pentru care timpul petrecut pana cand se ocupa ambele cabine vecine este cat mai mare.
  2. 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.incabine.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content