|
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 |