Fişierul intrare/ieşire:trapezoid.in, trapezoid.outSursăBOI 2011
AutorAdăugată deoldatlantianSerban Cercelescu oldatlantian
Timp execuţie pe test1.0 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Trapezoid

Considera doua linii orizontale alese arbitrar. Un trapezoid Ti are doua varfuri situate pe linia superioara si doua situate pe linia inferioara (vezi figura de mai jos). Vom denumi ai, bi, ci, di varfurile stanga-sus, dreapta-sus, stanga-jos si dreapta-jos ale trapezoidului Ti. 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 de cardinal maxim, 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: ai, bi, ci, di. Nu vor exista doua trapezoide ce se intersecteaza intr-un singur punct.

Date de ieşire

Singura linie a fisierului de iesire va contine doua numere separate prin spatiu: cardialitatea celei mai mari submultimi independente, apoi numarul submultimilor independente de cardinal maxim modulo 30013.

Restricţii

  • 1N100.000
  • 1ai, bi, ci, di ≤ 1.000.000.000
  • Pentru un raspuns corect la prima cerinta, veti primi 40% din punctajul testului
  • Pentru 40% din teste, N ≤ 5.000

Exemplu

trapezoid.intrapezoid.out
7
1 3 1 9
4 7 2 8
11 15 4 12
10 12 15 19
16 23 16 22
20 22 13 25
30 31 30 31
3 8

Explicaţie

Atentie, imaginea de mai sus nu este o reprezentare fidela a datelor de intrare. Laturile sus jos au fost mutate pentru vizibilitate.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?