Fişierul intrare/ieşire:bile5.in, bile5.outSursăONI 2009, clasa a 10-a
AutorMugurel Ionut AndreicaAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.2 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bile5

N prieteni stau în jurul a N urne cu bile. Prietenii şi urnele sunt numerotate cu numere de la 0 la N-1. Fiecare urnă i (0 ≤ i ≤ N-1) conţine Si bile. Prietenii doresc să extragă bile din urne şi să le pună în buzunare. Datorită aşezării, din urna i pot extrage bile doar prietenii i şi ((i+1) mod N). Fiecare prieten i (0 ≤ i ≤ N-1) are o capacitate a buzunarelor de Pi bile (adică nu poate extrage mai mult de Pi bile în total). Prietenul 0 este liderul lor şi îşi pune întrebări de forma: dacă eu extrag exact x bile din urna 0, atunci care este numărul maxim de bile pe care le pot extrage în total toţi prietenii, folosind o strategie adecvată şi considerând limitările problemei? O strategie adecvată determină câte bile extrage fiecare prieten din fiecare urnă din care poate extrage bile, considerând că prietenul 0 extrage neapărat x bile din urna 0.

Cerinta

Pentru fiecare valoare posibilă a lui x (de la 0 la min(S0, P0)), determinaţi numărul maxim de bile pe care le pot extrage cei N prieteni în total din cele N urne.

Date de intrare

Prima linie a fişierului bile5.in conţine numărul de teste T descrise în continuare. Prima linie a fiecărui test conţine numărul N de prieteni. Urmează apoi N linii. Linia i dintre acestea (0 ≤ i ≤ N-1) conţine numerele întregi Si şi Pi, separate printr-un spaţiu.

Date de ieşire

În fişierul de ieşire bile5.out veţi afişa răspunsurile pentru fiecare test, în ordinea în care acestea sunt date în fişierul de intrare. Pentru fiecare valoare posibilă a lui x (considerând ordinea crescătoare a valorilor) pentru testul respectiv, veţi afişa o linie conţinând numărul maxim total de bile pe care îl pot extrage prietenii din urne.

Restricţii

  • 1 ≤ T ≤ 10
  • 2 ≤ N ≤ 15 000
  • 1 ≤ Si ≤ 16 000
  • 1 ≤ Pi ≤ 16 000
  • 40% dintre teste au N ≤ 500 şi max(Si,Pi) ≤ 500 (0 ≤ i ≤ N-1)
  • A mod B reprezintă restul împărţirii întregi a lui A la B.
  • O bilă poate fi extrasă o singură dată, de un singur prieten.

Exemplu

bile5.inbile5.out
2
4
5 5
3 4
8 6
3 4
4
2 3
6 5
2 4
3 1
17
18
19
19
19
18
13
13
12

Explicaţie

Pentru primul test x poate lua valori între 0 şi min(S0, P0)=5.
Pentru x=0, cei 4 prieteni pot extrage în total 17 bile.
Pentru x=1, cei 4 prieteni pot extrage în total 18 bile.
Pentru x=2, cei 4 prieteni pot extrage în total 19 bile.
Pentru x=3, cei 4 prieteni pot extrage în total 19 bile.
Pentru x=4, cei 4 prieteni pot extrage în total 19 bile.
Pentru x=5, cei 4 prieteni pot extrage în total 18 bile.
Valoarea lui x a fost inclusă de fiecare dată în numărul total de bile ce pot fi extrase de cei 4 prieteni.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content