Bazandu-ne pe acelasi principiu ca si cel anterior, constatam ca putem retina o tabela de dispersie / tabela hash pentru toate momentele de timp in care s-a pariat. Pentru fiecare moment de timp vom retine in hash valoarea de bani castigata de cei $N$ oameni. In final, vom afisa doar momentele de timp care exista in hash.

h2. 'Beri':problema/beri
 
h4. $Solutia 1: O(N log N) - 50 puncte$
 
Avand in vedere ca pretul celor $N$ beri scade cu cate un leu pe minut, este evident ca ordinea acestora in functie de pret va ramane neschimbata la orice moment de timp (daca berea $i$ este mai scumpa decat berea $j$ la momentul $0$, atunci berea $i$ va fi mai scumpa decat berea $j$ si la orice alt moment de timp). Vom construi vectorul $C[i]$ dupa formula din enunt:
 
* $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:
 
* $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.
 

h2. 'Melodii':problema/melodii
Solutii prezentate de ==user(user="maritim" type="tiny")==.