Matei-Dan Epure (motty)

Vezi solutiile trimise	Nume	Matei-Dan Epure
	Cont	motty
	Rating	624
	Statut	Helper
	Forum	trimite mesaj privat, vezi activitate

Despre mine

• Sunt elev in clasa a 10-a la Colegiul National de Informatica "Tudor Vianu"
• Am inceput informatica in octombrie 2008 _{(clasa a 9-a)}
• In God we Trust!
• Gibson rulez \m/!

Distinctii primite

• Mentiune la ONI 2009 _{(clasa a 9-a)}
• Premiul I la Concursul de Informatica "Urmasii lui Moisil" Iasi - 2009

Profesori

Victor Manz •rapidu36
Filip Cristian Buruiana •filipb
Andrei Parvu •andrei.12

Prieteni pe infoarena

Gabriel Bitis •gabitzish1
Gheorghe Cosmin •gcosmin
Carabet Cosmin Andrei •cosmin79
Irina Stanescu •ira
Sorescu Ilinca •ilinca
Iancu David Traian •funkydvd
Barbulescu Dan •punkist
Andrei Poenaru •AndreyP
Tataranu Vlad •tvlad
Farcasanu Alexandru Ciprian •ciprianf
Mandu Dragos •drag0s93
Andrei Duma •AndreiDuma
Pandele Ioana •Ioanna
Andrei-Bogdan Antonescu •andrei-alpha
Tache Alexandru •hadesgames
Sfrent Andrei •andreisfrent
Matei Ionita •Nemultumitu

Numerele lui Stirling

Se numesc :

Numerele lui Stirling de speta I :

s(n,m) = numarul de permutari de ordin _n cu exact _m cicluri.

Numerele lui Stirling de speta II :

S(n,m) = numarul de partitionari ale unei submultimi de _n elemente in _m submultimi nevide.

Cerinta

Pentru _n si _m date, sa se calculeze una dintre cele 2 functii, _s(n,m) sau _S(n,m).

Date de intrare

Prima linie a fisierului de intrare _stirling.in contine numarul de teste T. Urmatoarele T linii contin cate un set de 3 numere, _s, _n si _m. Variabila _s poate lua valorile 1 si 2, avand semnificatia ca se doreste rezultatul functiei de speta I sau speta II.

Date de iesire

Pentru fiecare test, afisati in fisierul _stirling.out rezultatul functiilor modulo 98999, fiecare pe cate un rand.

Restrictii

• 0 < T < 1001
• 0 <= n,m <= 200

Exemplu

Indicatii de rezolvare

Backtracking:
Ideea "naiva" de rezolvare a acestei probleme presupune generarea tuturor permutarilor de ordin n si calcularea numarului de cicluri a fiecareia dintre acestea. Aceasta rezolvare are complexitatea exponentiala si va obtine 10 puncte. O astfel de sursa poate fi gasita aici.

http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind
http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
http://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html
http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html

In urma unei demonstratii matematice, luandu-se in considerare relatiile prezentate pe cele doua link-uri de mai devreme, rezulta recurentele :

s(n,m) = s(n-1,m-1) + n*s(n-1,m)

S(n,m) = S(n-1,m-1) + k*S(n-1,m)

Recursivitate:

Pentru un singur test, o metoda optima de rezolvare este cea care foloseste o functie recursiva si calculeaza la fiecare pas elementele necesare recurentei pasului actual. Totusi, daca nu este folosita memorizarea, la un numar mai mare de teste, aceasta rezolvare va iesi din timp. Folosind aceasta metoda veti obtine 50 de puncte, o sursa ce foloseste aceasta metoda poate fi gasita aici.

Programare dinamica:

Solutia optima a acestei probleme este cea care foloseste metoda programarii dinamice. astfel vor fi precalculate 2 matrici s[N][M] si S[N][M] cu semnificatia s[i][j]=s(i,j) si S[i][j]=S(i,j). Folosindu-se aceasta metoda, la fiecare test vom raspunde in o(1) la intrebare si deci complexitatea va fi o(N*M + T). Aceasta rezolvare obtine 100 de puncte si o sursa ce o foloseste poate fi gasita aici.