Soluţia problemei Papagali

O primă observaţie este că dacă avem x papagali dintr-o specie, atunci ei pot fi cuplaţi în (x-1) * (x-3) * (x-5) * ... * 1 moduri. Acest fapt este adevărat deoarece cel mai din stânga papagal poate fi cuplat cu oricare dintre ceilalţi N-1 papagali, apoi cel mai din stânga papagal necuplat încă poate fi cuplat cu oricare dintre ceilalţi N-3 papagali necuplaţi încă, şi tot aşa.

În ceea ce priveşte aşezarea papagalilor într-un şir, sunt Nr = comb(N, A₁) * comb(N-A₁, A₂) * comb(N-A₁-A₂, A₃) * ... * comb(A_K, A_K) moduri de a aşeza papagalii. Acest fapt poate fi justificat astfel: sunt comb(N, A₁) moduri de a alege poziţiile pe care stau papagalii din prima specie, apoi sunt comb(N-A₁, A₂) moduri de a alege (dintre poziţiile neocupate încă) poziţiile pe care stau papagalii de a doua specie, şi tot aşa. Prin dezvoltarea combinărilor, obţinem Nr = N! / (A₁! * A₂! * ... * A_K!).

Combinând cele două observaţii, obţinem că numărul de scheme de papagali este: S = N! / (A₁!! * A₂!! * ... * A_K!!), unde x!! = x * (x-2) * ... * 2.

Dacă vrem să cumpărăm papagali noi, atunci vom cumpăra câte 2 papagali noi la fiecare pas şi vom precalcula răspunsurile pentru toate query-urile posibile. La fiecare pas trebuie să cumpărăm papagali dintr-o specie care conţine număr minim de papagali la momentul respectiv. Pentru a afla numărul minim de papagali dintr-o specie la un anumit pas, putem menţine un heap sau un vector de frecvenţa.