[ONI][IX] Bere
0Am 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 Ci – 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 C1, C2 … CN, 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:
k1 x1
k2 x2
…
kT xT
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 Di reprezentand numarul de beri pe care le va cumpara prietenul ki cu suma de bani xi 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 contori).
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.
Solutia O(T * log n)
1. Calculam sirul de sume partiale Sumi = C1 + C2 … + Ci
2. Suma costurilor berilor pe orice interval (i,j) va fi Sumj – Sumi – 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]