Etichete : .campion, algoritmica, informatica, kperms, OJI, ONI, Probleme algoritmica

De curând Gigel a devenit atras de permutări, în special de acele permutări cu N elemente ce conţin exact K secvenţe descrescătoare maximale.

Cerinţă

Scrieţi un program care să determine câte permutări de N elemente cu exact K secvenţe descrescătoare maximale există?

Date de intrare

Fişierul de intrare kperms.in va conţine o singură linie pe care se afla numerele naturale N şi K separate printr-un spaţiu.

Date de ieşire

Fişierul de ieşire kperms.out va conţine o singură linie pe care va fi scris numărul de permutări de N elemente cu exact K secvenţe descrescătoare maximale modulo 666013.

Restricţii

• 2 ≤ N ≤ 1000
• 1 ≤ K ≤ N
• Prin secventa se intelege o succesiune de de elemente situate pe pozitii consecutive. O secvenţă descrescătoare este considerată maximală dacă nu mai poate fi adăugat în secvenţă un element (evident, la unul dintre capetele secvenţei) astfel încât secvenţa să rămână descrescătoare.

Exemple

Solutie

Aceasta problema are nevoie de o tehnica ce se bazeaza pe programare dinamica. Vom considera
Vom considera :
d[i][j] = cate permutari de i elemente cu j secvente descrescatoare maximale

Presupunem ca avem o permutare cu i-1 elemente si cu j secvente descrescatoare maximale. Observam ca putem insera elementul i intre i pozitii (la inceput, la sfarsit, sau intre oricare 2 elemente consecutive).
Daca introducem pe i inaintea uneia dintre cele j secvente numarul de secvente descrescatoare va ramane la fel
iar daca inseram in celelalte i – j + 1 pozitii numarul de secvente descrescatoare creste cu 1.

Recurenta va ajunge astfel:

d[1][1] =1
d[i][j] = (i – j + 1) * d[i – 1] [j – 1]  + j * d[i – 1][ j ]

Rezolvarile mele difera putin, eu am folosit doua abordari mai “ciudate”, ca de obicei. In ambele situatii m-am folosit de faptul ca datorita recurentei dezvoltate mai sus, vom avea nevoie de doar de ultimile doua linii din matrice.

In primul caz am folosit doi pointeri cu care am jonglat pentru a schimba intre ele liniile, prima devenind ultima si invers.Solutia o puteti descarca de aici.
Cea de-a doua situatie se bazeaza pe acelasi lucru, doar ca am folosit doar un singur vector si doua variabile care schimba pozitiile indicilor si muta locatiile la inceputul vectorului sau la pozitia n+ceva .Solutia a doua o puteti descarca aici.

Recomandam, pe aceeasi tema

Despre autorul articolului :

Avădănei Andrei - Autorul a scris 591 articole (vezi lista completa).

Contact | andrei@worldit.info | @worldIT – @AndreiAvadanei

Fondator si redactor worldit.info, ma numesc Andrei si sunt pasionat de programare , in special de algoritmica si web development. Forumul WorldIT iti sta la dispozitie daca ai nevoie de suport tehnic, informatii si sugestii privind diverse produse prezentate pe blog si nu numai. Mai multe detalii despre activitatile mele aici.