Atenție! Aceasta este o versiune veche a paginii., scrisă la 2016-06-10 11:24:42.
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

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.

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

Indicii de rezolvare

Arată 3 categorii