Fişierul intrare/ieşire: | startrek.in, startrek.out | Sursă | ONI 2017, clasele 11-12 |
Autor | Eugen Nodea | Adăugată de | Bogdan Ciobanu •bciobanu |
Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Startrek
"Spaţiul: ultima frontieră. Acestea sunt călătoriile navei stelare Enterprise. Misiunea ei neîncetată: să exploreze lumi noi şi stranii, să caute noi forme de viaţă şi noi civilizaţii, să meargă acolo unde nimeni nu a mai fost vreodată."
Jean-Luc Picard – căpitanul navei Enterprise stabileşte noua destinaţie: Imperiul Stelar Romulan. Gaura de vierme nou descoperită de echipaj asigură calea de acces spre Quadrantul Beta – aria galactică unde se află Imperiul Stelar Romulan.
Ipotetic, putem privi gaura de vierme ca un segment de dreaptă partiţionat în N sectoare de lungimi egale numerotate de la 1 la N pe care nava le va parcurge exact în această ordine. În funcţie de distorsiunile spaţiu-timp întâlnite, nava poate parcurge într-un an sideral (UTC – timpul universal coordonat) cel puţin p sectoare şi cel mult q sectoare. Pentru fiecare sector căpitanul Picard trebuie să informeze Federaţia despre anul în care a fost parcurs. Datorită interferenţelor transmisia datelor este deficitară. Astfel, Federaţia nu primeşte informaţii din toate cele N sectoare.
Cerinţă
Cunoscând descrierea a M transmisii primite de Federaţie de forma: s t, unde s reprezintă indicele unui sector, iar t reprezintă anul în care este parcurs acesta, să se determine numărul maxim de ani în care este străbătută gaura de vierme formată din N sectoare numerotate de la 1 la N.
Date de intrare
Fişierul de intrare startrek.in conţine pe prima linie patru numere naturale N, p, q şi M, separate prin câte un spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii se află descrierea celor M transmisii primite de Federaţie, în ordinea crescătoare a anilor şi a sectoarelor.
Date de ieşire
Fişierul de ieşire startrek.out va conţine două linii. Pe prima linie se va afla un număr natural nenul A ce reprezintă numărul maxim de ani siderali necesar parcurgerii celor N sectoare. Pe cea de a doua linie se vor găsi N valori despărţite prin câte un spaţiu ce reprezintă descrierea temporală minimal lexicografică a sectoarelor parcurse, pentru fiecare sector fiind specificat anul.
Restricţii
- 2 ≤ N ≤ 100.000
- 2 ≤ p < q ≤ N
- 1 ≤ M ≤ N
- fiecare sector trebuie parcurs în totalitate în cadrul aceluiaşi an sideral;
- întreaga călătorie trebuie parcursă într-un număr întreg de ani siderali (cu alte cuvinte: parcurgerea a cel puţin p sectoare şi cel mult q sectoare este valabilă şi pentru primul şi ultimul an);
- pentru datele de intrare există întotdeauna soluţie;
- pentru 30 de puncte 2 ≤ N ≤ 100, 2 ≤ p < q ≤ 50
- pentru 70 de puncte 2 ≤ N ≤ 30.000, 2 ≤ p < q ≤ 300
- pentru 100 de puncte 2 ≤ N ≤ 100.000, 2 ≤ p < q ≤ N
Exemplu
startrek.in | startrek.out | Explicaţie |
---|---|---|
5 2 3 1 2 1 | 2 1 1 1 2 2 | Ştim că al doilea sector este parcurs în primul an. 1 1 2 2 3 nu poate fi soluţie deoarece în anul 3 nu sunt parcurse minim 2 sectoare. Sunt necesari 2 ani pentru parcurgerea celor 5 sectoare. Primele 3 sectoare vor fi parcurse în primul an, următoarele 2 sectoare în cel de-al doilea an. |
7 2 5 2 2 1 6 3 | 3 1 1 1 2 2 3 3 | Sunt necesari 3 ani pentru parcurgerea celor 7 sectoare. Primele 3 sectoare vor fi parcurse în primul an, următoarele 2 sectoare în cel de-al doilea an, iar ultimele 2 sectoare în cel de-al treilea an. |
16 3 4 2 5 2 15 5 | 5 1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 | Sunt necesari 5 ani pentru parcurgerea celor 16 sectoare. |