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

Î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 rănd numărul maxim K de dreptunghiuri ce pot fi alese astfel încât primul să intre în al doilea, al doilea în al treilea, ..., al K-1-lea in al K-lea.

Restricţii

  • 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

Explicaţie

Se aleg dreptunghiurile 5,3,4,6, în această ordine.

Trebuie sa te autentifici pentru a trimite solutii. Click aici