976 Cabine

[•pauldb]

Aici puteti discuta despre problema Cabine.

[•lamez0r]

va rog daca se poate sa ma lamuriti daca ideea mea despre problema e corecta sau nu. E clar ca primele cabine ocupate vor fi cele de la capat. Strategia pe care eu o aplic pentru ocuparea urmatoarelor cabine este urmatoarea: Aleg cel mai lung sir de cabine neocupate consecutive si imi plasez vorbitorul, in cabina din centrul intervalului dupa care repet procedura. Nu ma intereseaza detalii legate de timpul de executie, ci doar daca acesta este modul optim de alegere al cabinei; si anume acela de a plasa vorbitorul intr'o cabina care are numar maxim de cabine libere atat la stanga cat si la dreapta sa.

Merci.

[•wefgef]

Nu aceasta este strategia.

[•ciprianf]

Am si eu o nelamurire:
avem n = 7 si k = 2
1 0 0 0 0 0 1

Cod:

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

Deci prima persoana ar alege pozitia 5 si apoi a2a persoana poz 3
Dar solutia buna nu ar fi fost: prima pers pe poz 3 si a2a pe poz 4?

[•stocarul]

NU, pentru că la restricțiile problemei scrie:

Niciunul dintre ocupanții cabinelor nu termina de vorbit la telefon pana cand nu se ocupa toate cabinele.

[•ciprianf]

Aceasta restrictie nu ne garanteaza doar faptul ca dupa ce un om a intrat in cabina acesta nu mai iese?
Nu inteleg ce legatura are cu exemplul meu

[•stocarul]

Ne mai garantează și faptul că vor veni oameni până se vor ocupa toate cabinele.

[•Mishu91]

Am si eu o nelamurire:
avem n = 7 si k = 2
1 0 0 0 0 0 1

Cod:

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

Deci prima persoana ar alege pozitia 5 si apoi a2a persoana poz 3
Dar solutia buna nu ar fi fost: prima pers pe poz 3 si a2a pe poz 4?

Dacă primul alege poziția 3 și al doilea 4, atunci al treilea ar alege 5, deci al doilea nu poate alege 4, ci 5. Dar, acum configurația ar fi 1010101, si următorul s-ar duce în 2, iar apoi în 4, deci primului nu îi convine.
Așadar, prima persoană alege 5, iar a doua 3.

[•ciprianf]

Ok, am inteles, ms, eu defapt intelesesem gresit problema deoarece credeam ca vor veni doar K persoane