Beri

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 Gapdan va plati prima bere 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

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 in ordine crescatoare, problema cunoscuta si sub numele Statistici de ordine.