Fişierul intrare/ieşire:mezzaluna.in, mezzaluna.outSursăAlgoritmiada 2017, Runda Finala, Seniors
AutorAdrian Budau, Mihai CalanceaAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.8 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mezzaluna

Dorin are un blat olimpic infinit de pizza ce se intinde pe axa OX. Acesta a observat faptul ca, cu cat taie mai des blatul de pizza, cu atat gustul va deveni mai bun. Astfel, avand la dispozitie un set de N intervale deschise, fiecare interval reprezentand o taietura pe care acesta poate sa o faca, scopul vostru este sa determinati numarul maxim de taieturi pe care Dorin le poate efectua.

Formal, Dorin poate selecta un interval pe care sa il taie in unul din cele 2 cazuri:

  • Blatul curent este infinit. Prin taierea cu un nou interval (C, D), blatul ia forma acestui interval.
  • Blatul curent este un interval (A, B). Putem selecta un nou interval (C, D) doar daca acesta micsoreaza intervalul curent. Formal, daca intersectia dintre (A, B) si (C, D) este un interval (X, Y), acesta trebuie sa fie nevid si trebuie sa difere de intervalul (A, B). Noul blat va lua forma intervalului (X, Y). A se nota ca intervalele fiind deschise, intervalul (X, X) este considerat a fi vid.

Dandu-se N si multimea celor N intervale cu care putem taia blatul, determinati numarul maxim de taieturi pe care il putem face, precum si numarul de moduri in care putem efectua aceste taieturi in numar maxim. Doua moduri de a taia blatul sunt considerate distincte daca multimile de intervale intermediare prin care trece forma blatului pe parcursul taierii sunt distincte. A se nota ca este posibil ca o anumita multime de intervale intermediare sa fie obtinuta prin serii de operatii care folosesc intervale diferite din cele N oferite, dar ea va fi numarata o singura data.

Date de intrare

Fişierul de intrare mezzaluna.in va contine pe prima linie un numar natural N. Pe urmatoarele N linii vor fi cate 2 numere natural [A, B] reprezentand cele N intervale.

Date de ieşire

Fişierul de ieşire mezzaluna.out va contine 2 numere naturale, numarul maxim de taieturi pe care il putem obtine, precum si numarul de moduri in care putem obtine acest maxim, modulo 1.000.000.007.

Restricţii

  • 1 ≤ A < B ≤ 2.000
  • 1 ≤ N ≤ 100.000
  • Pentru teste in valoare de 30 de puncte, se garanteaza ca N ≤ 200
  • Rezolvarea corecta a primei cerinte valoreaza 40% din punctajul testului

Exemplu

mezzaluna.inmezzaluna.out
4
1 4
1 3
2 4
2 3
3 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?