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

Rezumat

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

Î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 \ge 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 \ge ps[n]$.) Pentru a verifica acest lucru, testăm dacă $ps[n] - ps[k - 1] \le 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] \le x$, știind că $k \le p \le 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, \ldots, 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++

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!

PayPal