Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | campion.in, campion.out | Sursă | Stelele Informaticii 2006, clasele 11-12 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Bogdan-Cristian Tataroiu •bogdan2412 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 36096 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Campion
 Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema! |
Zaharel lucreaza din greu la site-ul infoarena 2.0. Treaba lui este sa construiasca un sistem de rating al utilizatorilor, in functie de competitiile la care a participat fiecare.
In primul rand, va trebui sa numere cati concurenti au fost campioni pe parcursul timpului. Pentru a simplifica problema, vom considera momentele de timp ca fiind numere reale intre 0 si T.
Fiecare din cei N utilizatori infoarena au inceput sa concureze la timpul 0 si au avut un rating Ri (1 ≤ i ≤ N). Se stie, de asemenea, ca fiecare concurent isi imbunatateste rating-ul cu Di (1 ≤ i ≤ N) pentru fiecare unitate de timp care trece.
Un utilizator se numeste campion daca exista un moment de timp in care a avut cel mai mare rating dintre toti utilizatorii. Daca doi sau mai multi utilizatori au fiecare cel mai mare rating intr-un moment de timp, se considera ca toti sunt campioni.
Cerinta
Ajutati-l pe Zaharel sa determine numarul de utilizatori care au fost campioni.
Date de intrare
In fisierul campion.in se afla pe prima linie numerele naturale N si T reprezentand numarul de utilizatori si limita superioara a momentelor de timp. Urmeaza N linii fiecare continand doua numere naturale Ri Di, reprezentand rating-ul initial si valoarea cu care se imbunatateste per unitate de timp, al fiecarui utilizator.
Date de iesire
Fisierul de iesire campion.out va contine o singura linie pe care se va afla numarul de concurenti care au fost campioni.
Restrictii
- 1 ≤ N ≤ 20 000
- 0 ≤ T ≤ 100 000 000
- 0 ≤ Ri ≤ 1 000 000 000
- 0 ≤ Di ≤ 1 000 000
- Rating-ul fiecarui utilizator nu va depasi 2 000 000 000 pentru orice moment de timp din intervalul [0...T]
- Toatele numerele din fisierul de intrare sunt numere naturale
- Pot exista utilizatori cu acelasi rating de inceput si aceasi valoare de imbunatatire
Exemplu
| campion.in | campion.out |
|---|---|
| 3 6 20 0 4 2 15 1 | 2 |
Explicatie
Concurentul 1 este initial campion, iar la momentul 5 concurentul 3 devine campion. Concurentul 2 devine campion la momentul 11, dar T = 6, deci nu se ia in considerare.
