Pagina principala | Inscriere | Autentificare | Probleme | Runde | Clasament | Anunturi | Echipa | Regulament | Exit


Vizualizare solutie pentru problema: aranjari

Titlul problemei aranjari
Grupa Grupa A
Problema numarul 1
Runda numarul 18
Solutie oficiala Aranjari - indicatii de rezolvare
Vom numi pozitii critice pozitiile in care o persoana se gaseste intre doua persoane mai tinere
ca ea.Vom determina numarul posibilitatilor de aranjare a n persoane cu i pozitii critice,
numar notat cu P(n,i). Atunci numarul cerut va fi P(n,0)+P(n,1)+...+P(n,k).
Avem P(n,0)=0 (fiindca exista cel putin o pozitie critica, a persoanei cea mai in varsta),
P(n,i)=0 pentru i>n/2 si relatia P(n,i)=2i*P(n-1,i)+(n+1-2i)*P(n-1,i-1).
Sa justificam aceasta relatie, asezand la masa persoanele in ordinea crescatoare a varstei :
Daca am asezat primele n-1 persoane astfel ca sa avem i pozitii critice, persoana a n-a trebuie
asezata astfel ca sa nu formeze o noua pozitie critica, ceea ce se poate asezandu-l la o pozitie
critica de forma x[j-1]x[j+1] inainte sau dupa x[j], deci 2i posibilitati
Daca am asezat primele n-1 persoane astfel ca sa avem i-1 pozitii critice, persoana a n-a
trebuie sa formeze o noua pozitie critica, deci sa nu fie in cele 2*(i-1) pozitii care nu dau
o noua pozitie critica, raman n-1-2*(i-1)=n+1-2i posibilitati.
Vom construi o matrice P de dimensiuni n x k, pornind de la relatiile scrise

Algoritm aranjari
Citeste n,k
pt. i=1,n
pt. j=1,k P[i,j]=0 sf.
sf.
P[3,1]=1
pt. i=4,n
pt. j=1,i/2
P[i,j]=2j*P[i-1,j]+(i+1-2j)*P[i-1,j-1]
sf.
sf.
S=0
pt. i=1,k
S=S+P[n,i]
sf.
scrie S
sf. algoritm


Sursa "oficiala" se gaseste in arhiva cu teste.

Download arhiva teste de intrare  

Click aici pentru a va intoarce

© 2002 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com