Fişierul intrare/ieşire:startrek.in, startrek.outSursăONI 2017, clasele 11-12
AutorEugen NodeaAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.instartrek.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?