Enunțul problemei br, de clasa a 9-a, dată în 2009 la ONI, se găsește pe .campion și InfoArena.

Rezumat br

La o masă rotundă sunt așezați n prieteni care beau bere fără alcool. Berea preferată a fiecărui prieten i are costul c[i]. Din când în când, un prieten cumpără câte o bere pentru o secvență de prieteni aflați pe poziții consecutive la masă, în sensul acelor de ceasornic, începând cu el. Să se răspundă la t întrebări de forma k x cu semnificația: Care este numărul maxim de beri pe care le poate cumpăra prietenul k folosind maxim x bani? Se vor cumpăra maxim n beri.

Soluție br

În primul rând, vom calcula vectorul de sume parțiale ps pentru vectorul c, pentru a putea mai apoi să determinăm în $O(1)$ suma valorilor pe anumite secvențe. Rezolvăm fiecare întrebare individual. În primul rând, observăm că dacă x >= ps[n], atunci se pot cumpăra beri pentru toți prietenii, așa că afișăm direct n.

Dacă nu, având în vedere că masa este circulară, s-ar putea ca secvența căutată să treacă prin n, iar apoi prin 1, ceea ce ne-ar îngreuna căutarea capătului din dreapta. (Asta se poate întâmpla cel mult o singură dată, căci altfel ne-am încadra în cazul x >= ps[n].) Pentru a verifica acest lucru, testăm dacă ps[n] - ps[k - 1] <= x. Dacă da, scădem ps[n] - ps[k - 1] din x, adăugăm n - k + 1 la soluție, și ne rămâne să rezolvăm aceeași problemă pentru noul x și k = 1. Rezultatul îl vom adăuga la soluția curentă.

Ne-am simplificat problema: Acum trebuie să găsim capătul din dreapta p al unei secvențe de lungime maximă ce începe cu k, astfel încât ps[p] - ps[k - 1] <= x, știind că k <= p <= n. Se poate observa ușor că sumele parțiale formează un șir crescător, deoarece costurile berilor sunt pozitive. Asta înseamnă că pentru p = k, k + 1, …, n, valorile ps[p] - ps[k - 1] sunt în ordine crescătoare. Așadar, putem face o simplă căutare binară pe rezultat, astfel:

La final, rezultatul, adică p, se va afla în lo.

Complexitatea algoritmului este $O(n + t \cdot \log_2 n)$.

Sursă C++ br

Dacă ai vreo nedumerire cu privire la problema br, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!