Fişierul intrare/ieşire:comentariu.in, comentariu.outSursăONIS 2015, Runda Finala
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test10 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Comentariu

În anul 3015, finala ONIS a ajuns un fenomen intergalactic cu sute de mii de participanţi, milioane de probleme şi zeci de soluţii acceptate pe concurs. Modul în care se face clasamentul a suferit şi el schimbări:

1. Nu mai există penalizare, deoarece nu vrem să inducem ideea că există concurenţi care ar fi în vreun fel penali.
2. Toate echipele care au acelaşi număr de probleme ocupă acelaşi loc în clasament.
3. Aceste locuri sunt numere consecutive.

Un exemplu de clasament:

Loc #EchipăNumăr Probleme
1Echipa Angajaţilor10
2Echipa cu referinţe Anime6
2Echipa cu referinţe mai mainstream6
3Echipa cu aptitudini muzicale5

Finala are şi comentatori live, fiind un eveniment foarte popular. Însă comentatorii, în mod asemănător cu cei care comentează meciuri de fotbal, nu sunt capabili de o analiză foarte fină, ci preferă să recite statistici mai mult sau mai puţin relevante. Astfel, în ora dintre finalul concursului şi premiere, comentatorii s-au hotărât să calculeze cel mai bun, respectiv cel mai prost loc pe care îl ocupa fiecare echipă după dezgheţarea clasamentului.

Mai exact, pentru fiecare din cele N echipe se cunosc valorile preFreeze[i], numărul de probleme corect rezolvate de către echipa i înainte de îngheţarea clasamentului, respectiv freeze[i], numărul de probleme la care echipa i a submitat surse în timpul îngheţării clasamentului. Astfel, fiecare echipă poate avea în final, din punctul de vedere al telespectatorului, între preFreeze[i] şi preFreeze[i] + freeze[i] probleme rezolvate.

Având aceste informaţii, vi se cere să calculaţi pentru fiecare echipă valorile worstCase[i], adică cel mai prost loc pe care poate ieşi echipa i, respectiv bestCase[i], cel mai bun loc pe care poate ieşi echipa i.

Date de intrare

Fişierul de intrare comentariu.in va conţine pe prima sa linie numărul T, numărul de teste din fişier. Urmează T teste care au următoarea structură: pe prima linie se află numărul N, semnificând numărul de echipe din clasament. Urmează N perechi de numere întregi, preFreeze[i] freeze[i] având semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire comentariu.out va exista câte o linie pentru fiecare echipă din fiecare test. Această linie trebuie să conţină două valori: bestCase[i] worstCase[i].

Restricţii

  • 1 ≤ T ≤ 50
  • 1 ≤ N ≤ 750
  • Toate valorile din fişier sunt în intervalul [0, 1.000.000].
  • Echipele sunt date într-o ordine aleatoare.

Exemplu

comentariu.incomentariu.out
1
3
0 1
0 1
0 1
1 2
1 2
1 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?