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
În timpul orei de matematică, Bianca nu este atentă Și începe să deseneze N dreptunghiuri pe caiet. La un moment dat, își pune următoarea întrebare: Care este numărul maxim de dreptunghiuri K, pe care poate sa le aleagă, astfel încât primul să încapă în al doilea, al doilea în al treilea,...., al *K*-1-lea in al *K*-lea? Pentru că nu știe răspunsul la această întrebare, îl roagă pe prietenul ei Ștefan să o ajute. Ștefan se gândește puțin și găsește un algoritm prin care să rezolve problema Biancăi și să afle numărul maxim. Găsiți și voi algoritmul lui Ștefan.
Se dau N dreptunghiuri pentru care se știe lungimea L si latimea l. Se cere să răspundeți la întrebarea Biancăi. Se consideră că un dreptunghi D1 cu lungime L1 și lățime l1 încape în alt dreptunghi D2 cu lungime L2 și lățime l2 daca L1 < L2 și l1 < l2.
Date de intrare
Fișierul de intrare drept.in conține pe prima linie numărul N de dreptunghiuri. Următoarele N linii conțin 2 numere întregi ce reprezintă lungimea L si lățimea l fiecarui dreptunghi.
Date de iesire
În fișierul de ieșire drept.out se va afișa 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.