Revizia anterioară Revizia următoare
Fișierul intrare/ieșire | drept.in, drept.out | Sursă | ad-hoc |
---|---|---|---|
Autor | din folclor | Adăugată de | Ioana Bica • ioanab |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 65536 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Dreptunghiuri
In timpul orei de matematica, Bianca nu este atenta si incepe sa deseneze N dreptunghiuri pe caiet. La un moment dat, isi pune urmatoarea intrebare: Care este numar maxim K de dreptunghiuri, pe care poate sa le aleaga, astfel incat primul sa incapa in al doilea, al doilea in al treilea,...., al k-1-lea in al k-lea? Pentru ca nu stie raspunsul la aceasta intrebare, il roaga pe prietenul ei Stefan sa o ajute. Stefan se gandeste putin si gaseste un algoritm prin care sa rezolve problema Biancai si sa afle numarul maxim. Gasiti si voi algoritmul lui Stefan.
Se dau N dreptunghiuri pentru care se stie lungime L si latime l. Se cere sa raspundeti la intrebarea Biancai. Se considera ca un dreptunghi D1 cu lungime L1 si latime l1 incape in alt dreptunghi D2 cu L2 si l2 daca L1<L2 si l1<l2.
Date de intrare
Fisierul de intrare drept.in constine pe prima linie numarul N de dreptunghiuri. Urmatoarele N linii contin 2 numere intregi ce reprezinta lungimea L si latimea l fiecarui dreptunghi.
Date de iesire
În fisierul de iesire drept.out se va afisa pe primul rand numarul maxim K de dreptunghiuri ce pot fi alese astfel incat primul sa intre in al doilea, al doilea in al treile,...., al k-1-lea in al k-lea.
Restrictii
- 1 ≤ N ≤ 100.000
- 0 ≤ l ≤ L ≤ 1.000.000
Exemplu
drept.in | drept.out |
---|---|
7 26 12 14 17 8 3 18 14 5 2 20 17 16 2 |
4 |
Explicatie
Se aleg dreptunghiurile 5,3,4,6, in aceasta ordine.