Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | plicuri.in, plicuri.out | Sursă | FMI No Stress 4 |
| Autor | Dragos Oprica | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Plicuri
Se da un sir cu 2*N numere, reprezentand lungimea L si latimea W a N plicuri. PalanRit vrea sa puna plicurile unul intr-altul si sa obtina un astfel de sir de plicuri, care intra unul intr-altul, cat mai mare. El poate sa puna un plic i intr-un plic j daca si numai daca: L[i] < L[j] si W[i] < W[j] sau L[i] < W[j] si W[i] < L[j]. Voi trebuie sa determinati lungimea maxima a unui astfel de sir de plicuri, pentru ca PalanRit nu este instare.
h2. Date de intrare
Pe prima linie a fisierului de intrare plicuri.in se afla N, reprezentand numarul de plicuri. Pe urmatoarele N linii se afla cate doua numere L[i] si W[i], separate printr-un spatiu, reprezentand lungimea si latimea plicului i.
Date de ieşire
In fisierul de iesire plicuri.out veti afisa un singur numar, reprezentand lungimea maxima a unui sir de plicuri care respecta conditia din enunt.
Restricţii
- 1 ≤ N ≤ 100 000
- Pentru 40% din teste, 1 ≤ N ≤ 2 500
- 1 ≤ L[i], W[i] ≤ 100 000, 1 ≤ i ≤ N
- ATENTIE! Cea dea doua conditie din enunt spune defapt ca plicurile se pot roti.
Exemplu
| plicuri.in | plicuri.out |
|---|---|
| 4 4 5 1 3 2 6 7 8 | 3 |
Explicaţie
Al doilea plic cu dimensiunile L = 1 si W = 3 intra in primul plic, cu dimensiunile L = 4 si W = 5, care la randul lui intra in ultimul plic cu dimensiunile L = 7 si W = 8. O alta solutie cu numar maximal de plicuri care intra unul in altul este sirul de plicuri 2, 3, 4, ambele avand lungimea 3.
