Atenție! Aceasta este o versiune veche a paginii., scrisă la 2020-02-19 09:39:21.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire drept.in, drept.out Sursă ad-hoc
Autor din folclor Adăugată de avatar ioanab Ioana Bica ioanab
Timp de execuție pe test 0.2 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii