Ora de sport - program informatica

Ora de sport - program informatica

Profesorul de sport doreste sa aleaga un elev care sa conduca un grup dintr-o clasa de n elevi la incalzirea de la ora de sport. Deoarece el ar vrea ca la fiecare ora, in principiu, sa fie alt elev care are acest rol, la inceputul orei ii aranjeaza pe elevi la intamplare si le imparte tricouri nenumerotate de 1 la n. Apoi da comenzi una dupa alta, rostind cuvintele "stanga" sau " dreapta", urmand ca dupa fiecare comanda jumatatea "opusa" comenzii date din sirul de elevi sa plece spre zona de incalzire, iar dintre cei ramasi sa aleaga mai departe. Daca numarul grupului de elevi impartit la un moment dat este impar, elevul din mijloc pleaca si el la incalzire. Alegerea se repeta pana cand ramane un singur elev pe care profesorul il numeste conducator pentru ziua respectiva.

Intr-o zi profesorul se intreaba oare cati elevi au sansa sa devina conducatori si care ar fi acestia? Dar el ar vrea sa mai stie si daca un elev purtand un tricou cu un anumit numar poate sau nu sa devina conducator si, in caz afirmativ, ce comenzi trebuie sa spuna pentru ca aceasta sa ajunga conducator?

Scrieti un program care determina elevii care pot fi conducatori, cunoscand numarul total al elevilor din clasa. Apoi, pe baza numarului de pe tricoul unui elev dat, stabiliti daca acesta poate fi in ziua respectiva conducator sau nu. In caz afirmativ, determinati o succesiune de comenzi stanga-dreapta in urma carora el devine conducator.

Date de intrare

Fisierul de intrare SPORT.IN contine doua numere naturale n si t , separate printr-un spatiu, reprezentand numarul de elevi din clasa, respectiv numarul de ordine de pe tricoul unui elev.

Date de iesire:

Fisierul de iesire SPORT.OUT va contine pe prima linie numerele de pe tricourile elevilor care pot deveni conducatori, separate prin cate un spatiu. Pe a doua linie se va afla cuvantul 'DA' sau cuvantul 'NU', dupa cum elevul cu numarul t pe tricou poate sa fie conducator sau nu. In caz afirmativ, pe a treia linie veti scrie un sir de caractere format din litere mici 's' si 'd' care reprezinta succesiunea de comenzi necesara. Daca pe al doilea rand ati scrie 'NU', in fisier nu se mai scrie nimic.

Restrictii si precizari

• 0<n<=10000
• 0<t<=n.

Exemple:

SPORT.IN SPORT.OUT

7 3 1 3 5 7

DA

SPORT.IN SPORT.OUT

7 4 1 3 5 7

NU

REZOLVARE!!!!

Sa observam ca enuntul precizeaza exlicit modelul dupa care se desfasoara activitatea profesorului care urmareste descoperirea/stabilirea conduc[torului grupului de elevi.

-Nu exista criterii de inteligenta(profesorul ar putea fi subiectiv..) 

-Nu exista considerente privind inaltimea, greutatea sau culoarea ochilor(sirul nu este ordonat dupa nici un criteriu), ci doar dupa numarul de pe tricouri. Rezulta ca aceste numere vor fi considerate numere de ordine(indici)in sir.

Ceea ce "alege" profesorul este jumatatea care ramane (de aici rezultand si jumatatea care pleaca). Rezulta ca rezolvarea, adica stabilirea raspunsului la cerinta problemei este dirijata de comenzile profesorului, grupul se injumatateste, ramanand in continuare de impartit jumatatea "preferata", adica cea care nu a a plecat.

Se obsera ca faptul ca daca la un moment dat pleaca, de exemplu, jumatatea din stanga din sir, nu are nici o legatura cu o comanda viitoare imediata sau ulterioara a profesorului; el alege sa plece o parte sau alta din grupul existent la momentul respectiv. Altfel spus, faptul ca dintre copii c1,c2,c3,,cq, unde q=[1+n)/2]-1, nu are nici o legatura cu faptul ca la un pas viitor se va alege jumatate dintr-un sir cp, cp-1, cr.

Rezulta ca impartirea unui astfel de subsir se poate face independent de impartirea celorlalte subsiruri. In conclzie, problema se imparte in subprobleme independente. In astfel de probleme metoda de rezolvare recomandata este Divide et impera.

Stabilita fiind metoda, sa definim o subproblema: la un moment dat avem elevii cu numerele de ordine st, st+1,.dr intr-un subsir care urmeaza sa fie impartit. La comanda profesorului, acest sir se imparte in doua subsiruri, in functie de parietatea lungimii sirului (st-dr+1):

1.     Daca st-dr+1 este numar par rezulta subsirurile formate din copiii avand numerele de ordine st+1, st+2,mij si mij+1, mij+2,..,dr, unde mij este [(st+dr)/2];

2.     Daca st-dr+1 este numar impar, vor rezulta subsirurile(st+1, st+2, mij-1) si (mij+1, mij+2,..,dr),urmand ca cel cu numarul de ordine mij sa mearga direct la incalzire.

In functie de comanda ramane in continuare in "prelucrare" fie subsirul din stanga, fie cel din dreapta. Sa observam ca daca numarul n este putere a lui 2, vor putea deveni conducatori toti copii. Adica, daca n=2^k , la prima impartire obsinem doua subsiruri, ambele de lungimi puteri ale lui 2, (care, evident, sunt numere pare) si asa mai departe, fiecare impartire da nastere la subsiruri avand numar par de elevi. De exemplu, daca n 16 , prima impartire conduce la subsiruri formate din elementele avand indice intre 1..8 si 9..16 . Daca s-a comandat stanga , raman copiii cu numerele de ordine 1 si 2. In functie de urmatoarea comanda conducator va fi fie 1 fie 2. In functie de urmatoarea comanda conducator va fi fie 1 fie 2. Dar la fel s-ar imparti si celelalte subsiruri in functie de comenzile profesorului.

Sa vedem ce se intampla daca n nu este putere a lui 2, dar este numar par. Evident, impartinand un astfel de numar la 2, putem obtine, fie un numar par fie unul impar. De exemplu, daca n=10, si prima comanda este dreapta , ramane subsitul 6..10. O comanda noua dreapta da nastere subsirului 9..10, deoarece mij ar avea valoarea 8, dar copilul care are acest numar de ordine pleaca la incalzire deoarece in subsirul 6..10 au fost 5 (un numar impar) de elevi.

Rezulta ca daca avem subsirul st, st+1, ,dr, unde numarul de elevi (dr-st+1) este impar, eleul avand numarul de ordine mij= [(st+dr)/2] nu poate s[ fie conduc[tor. Asa pare, ca impartind pur si simplu numarul n in mod repetat la 2, am putea raspunde la prima intrebare( oare cati elevi au sansa sa fie conducatorii si care ar fi acestia?). Dar nu este asa! Trebuie sa rezolvam aceeasi subproblema pentru subsiruri rezultate atat in partea stanga, cat si in partea dreapta!

Cea de-a doua intrebare(un elev purtand un tricou cu un anumit numar poate sau nu deveni conducator?) intr-un fel este "inversa" primei intrebari. Adica, indepartand dintre cei n elevi pe cei care nu pot fi conducatori, raman cei care pot fi. Rezulta ca vom pastra numerele de ordine care in urma divizarii repetate raman singure intr-un subsir. Din cauza ca sirul nu se imparte exact in doua, ci in functie de paritatea elementelor, cel din mijloc se elimina din prelucrare, este nevoie de o variabila suplimentara mij1 in care pastram numarul de ordine al mijlocului sirului, urmand ca in functie de paritatea elementelor in subsirul actual sa stabilim limitele subsirurilor rezultate.

Subalgoritm Com1(st,dr);

daca st<dr atunci

mij<- (st+dr) div 2

mij<- mij+1

daca (dr-st+1) este numar impar atunci

mij<- mij-1  

sfarsit daca

Com1(st, mij)

Com1(mij1, dr)

altfel

scrie st

sfarsit daca

Sfarsit subalgoritm.

In a treia intrebare ni se cer comenzile care trebuie spuse pentru ca un anumit elev sa ajunga conducator. Pentru aceasta vom determina mijlocul subsirului, apoi in functie de valoare, vom elimina(depasi) sau nu acest punct de mijloc. Daca numarul de ordine este mai mic, il vom cauta in continuare in stanga, ceea ce necesita comanda stanga, altfel in dreapta, corespunzator unei comenzi dreapta. Comenzile (caracterele corespunzatoare) le vom pastra intr-o variabila de timp string.

Subalgoritm Com2 (st, dr);

Daca st<dr atunci

mij<- (st+dr) div 2

t1<- mij

mij1<- mij+1

daca (dr-st+1) este numar impar atunci

mij<-mij-1

sfarsit daca

daca t<=t1 atunci

comanda<- comanda+'s'

Com2(st, mij)

altfel

comanda<- comanda+'d'

Com2 (mij1, dr)

sfarsit daca

altfel

daca t=st atunci gasit <- adevarat

sfarsit daca

sfarsit daca

Sfarsit subalgoritm.