Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | licenta.in, licenta.out | Sursă | FMI No Stress 6 |
| Autor | Alex Palcuie | 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
Licenta
Ajunsă în ultimul an de facultate, Mihaela se hotărăşte să îşi termine lucrarea de licenţă intitulată 'Polinomul minimal a unei rădăcini de ordin O într-o extensie algebrică de grad G'. Fiindcă in lucrarea ei a obţinut rezultate legate de existenţa marţienilor, aceasta doreşte să se întâlnească cu îndrumătorul ei, decanul.
Din păcate, timpul nu e de partea ei. Mihaela are la dispoziţie o mulţime de intervale S de dimensiune N la care poate veni în facultate.
Decanul este o persoană foarte ocupată, precum Mihaela, are la îndemână o mulţime de intervale T de dimensiune M în care este la biroul său.
Mihaela are nevoie de exact K minute pentru a explica ideile prezente în lucrarea ei indrumătorului. Pentru că eroina lucrează la conjectura P=NP vă roagă să găsiţi un interval de timp de fix K secunde astfel încât ea să fie la facultate iar profesorul ei îndrumător prezent în birou.
În caz că există mai multe soluţii de forma [X, Y], ea doreşte să afişaţi intervalul cu X minim. Dacă nu există o soluţie atunci afişaţi -1 pe prima linie.
Date de intrare
Fişierul de intrare licenta.in conţine pe prima linie numărul natural K specificat în enunţ. Pe a doua linie este un singur număr natural N reprezentând dimensiunea mulţimei S.
Următoarele N linii conţin câte 2 numere naturale separate prin câte un spaţiu: XS[i], YS[i] specificând intervalele de minute în care Mihaela este la facultate.
Următoarea linie conţine numărul natural M.
Următoarele M linii conţin câte 2 numere naturale separate prin câte un spaţiu: XT[j], YT[j] specificând intervalele de minute în care profesorul este la biroul său.
Date de ieşire
Prima linie conţine 2 numere naturale separate prin câte un spaţiu X Y, reprezentând intervalul de timp în care Mihaela se întâlneşte cu Decanul.
Restricţii
- 1 ≤ K < 109
- 1 ≤ N ≤ 105
- 0 ≤ XS[i] < YS[i] < 109 oricare 1 ≤ i ≤ N
- 1 ≤ M ≤ 105
- 0 ≤ XT[j] < YT[j] < 109 oricare 1 ≤ j ≤ M
- Pentru 40 de puncte 1 <= N * M <= 5 * 106
- Pentru a lua 100 de puncte, you need to do it for the watch.
Exemplu
| licenta.in | licenta.out |
|---|---|
| 4 2 1 10 11 13 2 2 4 5 12 | 5 9 |
Explicaţie
Mihaela poate să ajungă la facultate în intervalele [1, 10]; [11, 13].
Decanul este în biroul său în intervalele [2, 4]; [5 12].
Se observă că dacă Miruna se întâlneşte începând cu minutul 5, aceasta reuşeşte să îi explice întreaga lucrare de licenţă timp de 4 minute. Ca urmare, soluţia este intervalul [5, 9].
