Problema BR – ONI 2009, Clasa a 9-a

Problema BR – ONI 2009, Clasa a 9-a

  • Dificultate:
  • Autor: Cristian George Strat
  • Online: InfoArena

Rezumat

La o masă rotundă sunt așezați nn prieteni care beau bere fără alcool. Berea preferată a fiecărui prieten ii are costul c[i]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 tt întrebări de forma kxk x cu semnificația: Care este numărul maxim de beri pe care le poate cumpăra prietenul kk folosind maxim xx bani? Se vor cumpăra maxim nn beri.

Soluție

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

if (x >= ps[n]) {
fout << n << '\n';
continue;
}

Dacă nu, având în vedere că masa este circulară, s-ar putea ca secvența căutată să treacă prin nn iar apoi prin 11 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 xps[n]x \ge ps[n] Pentru a verifica acest lucru, testăm dacă ps[n]ps[k1]xps[n] - ps[k - 1] \le x Dacă da, scădem ps[n]ps[k1]ps[n] - ps[k - 1] din xx adăugăm nk+1n - k + 1 la soluție, și ne rămâne să rezolvăm aceeași problemă pentru noul xx și k=1k = 1 Rezultatul îl vom adăuga la soluția curentă.

if (ps[n] - ps[k - 1] <= x) {
sol += n - k + 1;
x -= ps[n] - ps[k - 1];
k = 1;
}

Ne-am simplificat problema: Acum trebuie să găsim capătul din dreapta pp al unei secvențe de lungime maximă ce începe cu kk astfel încât ps[p]ps[k1]xps[p] - ps[k - 1] \le x știind că kpnk \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,,np = k, k + 1, \ldots, n valorile ps[p]ps[k1]ps[p] - ps[k - 1] sunt în ordine crescătoare. Așadar, putem face o simplă căutare binară pe rezultat, astfel:

int lo = k - 1, hi = n + 1;
while (hi - lo > 1) {
int md = (lo + hi) / 2;
if (ps[md] - ps[k - 1] > x)
hi = md;
else
lo = md;
}

La final, rezultatul, adică pp se va afla în lolo

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

Sursă C++

Problema BR
#include <fstream>
#define NMAX 15010
std::ifstream fin("br.in");
std::ofstream fout("br.out");
int n, t;
int ps[NMAX];
int main() {
fin >> n >> t;
for (int i = 1; i <= n; i++) {
fin >> ps[i];
ps[i] += ps[i - 1];
}
for (int it = 0; it < t; it++) {
int k, x; fin >> k >> x;
if (x >= ps[n]) {
fout << n << '\n';
continue;
}
int sol = 0;
if (ps[n] - ps[k - 1] <= x) {
sol += n - k + 1;
x -= ps[n] - ps[k - 1];
k = 1;
}
int lo = k - 1, hi = n + 1;
while (hi - lo > 1) {
int md = (lo + hi) / 2;
if (ps[md] - ps[k - 1] > x)
hi = md;
else
lo = md;
}
sol += lo - k + 1;
fout << sol << '\n';
}
return 0;
}

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

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii