Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | trapezoid.in, trapezoid.out | Sursă | BOI 2011 |
| Autor | Adăugată de |  Serban Cercelescu •oldatlantian | |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Trapezoid
Considera doua linii orizontale alese arbitrar. Un trapezoid T_i are doua varfuri situate pe linia superioara si doua situate pe linia inferioara (vezi figura de mai jos). Vom denumi a_i, b_i, c_i, d_i varfurile stanga-sus, dreapta-sus, stanga-jos si dreapta-jos ale trapezoidului T_i. O multime de trapezoizi se numeste independenta daca niciunul dintre membrii sai nu se intersecteaza.
Cerinta
Dandu-se N trapezoizi, aflati cardinalitatea celei mai mari submultimi indepedente de-a sa. De asemenea, trebuie sa aflati si numarul de submultimi independente maximale, modulo 30013.
Date de intrare
Pe prima linie se va afla N, numarul de trapezoizi dati. Fiecare din urmatoarele N linii va contine cele 4 numere: a_i, b_i, c_i, d_i. Nu vor exista doua trapezoide ce se intersecteaza intr-un singur punct.
Date de ieşire
În fişierul de ieşire trapezoid.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| trapezoid.in | trapezoid.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
