* $C[i] = ( C[i-1] * X + Y ) % Z + K$
Din formula de mai sus, reiese foarte usor faptul ca $C[i] >= K$, pentru orice $i$ intre $1$ si $N$. Deci, stim sigur ca dupa $K$ minute, pretul tuturor berilor este inca pozitiv. In continuare, vom sorta crescator numerele si vom retine suma ultimelor $K$ pe care o vom nota cu S, acestea fiind cele mai scumpe beri la toate momentele de timp. Stim ca pretul berilor scade cu cate un leu pe minut, deci prima bere o va plati integral, pentru cea de-a doua bere va plati cu $1$ leu mai putin, pentru cea de-a treia va plati cu $2$ lei mai putin, ..., pentru cea de-a $K$-a bere va plati cu $K-1$ lei mai putin. In concluzie, raspunsul va fi:
Din formula de mai sus, reiese foarte usor faptul ca $C[i] >= K$, pentru orice $i$ intre $1$ si $N$. Deci, stim sigur ca dupa $K$ minute, pretul tuturor berilor este inca pozitiv. In continuare, vom sorta crescator numerele si vom retine suma ultimelor $K$ pe care o vom nota cu S, acestea fiind cele mai scumpe beri la toate momentele de timp. Stim ca pretul berilor scade cu cate un leu pe minut, deci prima bere o va plati integral, pentru cea de-a doua bere va plati cu $1$ leu mai putin, pentru cea de-a treia va plati cu $2$ lei mai putin, ..., pentru cea de-a $K$-a bere va plati cu $K - 1$ lei mai putin. In concluzie, raspunsul va fi:
* $S - (1 + 2 + ... + K - 1) = S - (K - 1) * K / 2$
h4. $Solutia 2: O(N) - 100 puncte$
Bazandu-ne pe aceeasi idee ca si la solutia anterioara, ne dam seama ca avem nevoie sa stim care sunt cele mai scumpe $K$ beri, dar nu avem nevoie de ele intr-o ordine fixa. De aceea, putem aplica algoritmul de pivotare Quick-Sort pentru gasirea celui de-al $(N-K+1)$-lea element intr-un vector sortat, problema cunoscuta si sub numele 'Statistici de ordine':problema/sdo.
Bazandu-ne pe aceeasi idee ca si la solutia anterioara, ne dam seama ca avem nevoie sa stim care sunt cele mai scumpe $K$ beri, dar nu avem nevoie de ele intr-o ordine fixa. De aceea, putem aplica algoritmul de pivotare Quick-Sort pentru gasirea celui de-al $N-K+1$-lea element intr-un vector sortat, problema cunoscuta si sub numele 'Statistici de ordine':problema/sdo.
h2. 'Melodii':problema/melodii
