[ONI][IX] Bere

Am uitat omis cateva zile aceasta sectiune pentru ca sunt putin mai ocupat.De acum revin cu 2 probleme de anul trecut de la ONI ce mi`au placut si sunt relativ simple 🙂 .

N prieteni, numerotati de la 1 la N, beau bere fara alcool la o masa rotunda. Pentru fiecare prieten i se cunoaste C_i – costul berii lui preferate. Din cand in cand, cate un prieten, fie el k, cumpara cate o bere pentru o secventa de prieteni aflati pe pozitii consecutive la masa, incepand cu el, in sensul acelor de ceasornic. El este dispus sa cheltuiasca x bani si doreste sa faca cinste la un numar maxim posibil de prieteni.

Cerinta

Se cere numarul de beri pe care le va cumpara fiecare prieten k in limita sumei x de bani de care dispune. In caz ca x este mai mare decat costul berilor pentru toti prietenii de la masa, se vor achizitiona maxim N beri.

Date de intrare

Prima linie a fisierului de intrare br.in contine doua numere naturale N si T separate printr-un spatiu reprezentand numarul de prieteni si respectiv numarul de prieteni care doresc sa faca cinste prietenilor sai.
A doua linie a fisierului de intrare contine N numere naturale C₁, C₂ … C_N, separate prin cate un spatiu, reprezentand costurile berilor preferate de fiecare prieten. Berea pentru prietenul i are costul Ci.
Fiecare din urmatoarele T linii contine cate doua numere separate printr-un spatiu:
k₁ x₁
k₂ x₂
…
k_T x_T
precizand indicele cate unui prieten care face cinste si respectiv suma de bani de care acesta dispune..

Date de iesire

Fisierul de iesire br.out va contine T linii, fiecare cu un singur numar D_i reprezentand numarul de beri pe care le va cumpara prietenul k_i cu suma de bani x_i in conditiile problemei.

Restricții

• 1 ≤ N ≤ 15.000
• 1 ≤ T ≤ 10.000
• 1 ≤ Ci ≤ 100
• 1 ≤ ki ≤ N
• 1 ≤ xi ≤ 3.000.000
• Un program corect, care se incadreaza in timp pentru T ≤ 4000, va obtine cel putin 30 de puncte
• Un program corect, care se incadreaza in timp pentru N ≤ 2000, va obtine cel putin 60 de puncte
• Prietenii beau numai berea lor preferata.

Exemplu

br.in

5 4
10 5 15 22 13
1 32
4 50
1 9
4 200

br.out

3
4
0
5

Timp execuție pe test 0.1 sec
Limita de memorie 16384 kbytes

Explicație

Prietenul 1 cumpara cate o bere pentru el si pentru prietenii 2, 3. Costul celor 3 beri este 30.
Prietenul 4 cumpara 4 beri: cate una pentru el si pentru prietenii 5, 1, 2. Costul celor 4 beri este 50.
Cu 9 bani prietenul 1 nu poate cumpara nici macar berea lui.
Prietenul 4 cumpara 5 beri. Costul celor 5 beri este sub limita de cost 200.

Solutii

Aceasta problema prezinta mai multe solutii ce ar putea fi abordate, toate oferind acelasi punctaj (maxim).Voi descrie o solutie mai lenta( O(n * T) in cazul defavorabil (abordarea mea de la ONI 2009)) si va voi propune o solutie ce se poate face in timp logaritimic(O(T * log n)).

Solutia O(n * T) :
1. Citim initial intr`un vector pret, reprezentand costul berilor celor N prieteni.
2. Pentru a aduce optimizarea ce face diferenta dintre cele 100 de puncte si aproximativ 60-70 de puncte(aceasta solutie fiind cea dorita pentru un semi-punctaj) intr`o situatie similara calculam si suma totala a costurilor berilor.
3. Pentru fiecare i de la 1 la T verificam daca suma totala este depasita de suma prietenului i,atunci afisam valoarea N,daca valoarea este mai mica decat a primului prieten ,iar in caz contrar scadem si ne deplasam la urmatorul prieten(in acelasi timp incrementand o variabila contor_i).
4. Datorita faptului ca aceasta solutie intra in timp la limita si cu putin putin noroc nu este sugerata, insa se poate aduce o mica optimizare(neimplementata in solutia prezentata).Putem considera faptul ca daca suma prietenului i este aproape de st, sa se construiasca un alt vector ce va pastra suma totala necesara de la primul pana la al i`lea prieten si sa se inceapa de la al n-lea prieten calcularea ultimului prieten ce ii poate oferi bere.

Solutie O(n*T) problema Bere

Solutia O(T * log n)
1. Calculam sirul de sume partiale Sum_i = C₁ + C₂ … + C_i
2. Suma costurilor berilor pe orice interval (i,j) va fi Sum_j – Sum_i – 1.
3. Folosind cautare binara si folosind vectorul Sum, cauti indicele p pana unde se pot cumpara berile incepand de la pozitia k.
4. Trebuie tinut cont de faptul ca sirul este circular si trebuie sa stabilesti unde se face cautarea binara : fie in intervalul [0,k] fie in intervalul [k+1,n-1]