Fişierul intrare/ieşire:drept.in, drept.outSursăad-hoc
AutorDin FolclorAdăugată deioanabIoana Bica ioanab
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.indrept.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 sa te autentifici pentru a trimite solutii. Click aici