Fişierul intrare/ieşire:fnaf.in, fnaf.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorGeorge MarcusAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test2 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

FNAF

Georgel joaca Five Nights at Freddy’s, un joc in care controlezi doua usi. Cand se apropie un monstru de usa stanga sau de cea dreapta, trebuie sa inchizi usa respectiva ca sa il opresti. Insa resursele sunt limitate si nu poti tine usile inchise tot timpul.

Se dau N evenimente de forma (t, usa), ceea ce inseamna ca la timpul t trebuie sa fie inchisa usa respectiva (ex: (7, STANGA)). Putem considera ca jocul incepe la momentul -Infinit.

Usile sunt vechi, asa ca dupa ce o usa a fost inchisa, ea va ramane inchisa cel putin d secunde. De asemenea, o singura usa poate fi inchisa la un moment dat, exceptand momentul in care se schimba usa (clarificari in exemplu). Daca inchidem o usa la momentul t, trebuie sa o tinem inchisa pana la momentul t + d. Putem sa o deschidem la momentul t + d si sa o inchdem pe cealalta usa tot la momentul t + d.

Gasiti timpul total minim in care usile vor sta inchise daca Georgel joaca optim sau specificati daca este imposibila satisfacerea tuturor evenimentelor.

Date de intrare

Fişierul de intrare fnaf.in va contine pe prima linie un numar intreg T reprezentand numarul de teste. Fiecare test are urmatorul format: pe prima linie se vor afla doua numere intregi N si d, reprezentand numarul de evenimente si durata minima pentru care trebuie sa stea inchisa o usa; pe fiecare dintre urmatoarele N linii se va afla descrierea unui eveniment (t, usa), numarul intreg t fiind timpul la care se intampla evenimentul si caracterul usa care reprezinta partea din care vine monstrul: S pentru stanga, D pentru dreapta.

Date de ieşire

În fişierul de ieşire fnaf.out se vor afla raspunsurile pentru cele T teste. Raspunsul pentru un test consta intr-un singur rand pe care se va afla timpul total minim in care usile vor sta inchise daca Georgel joaca optim sau -1 daca este imposibila satisfacerea tuturor evenimentelor.

Restricţii

  • 1 ≤ T ≤ 30
  • 1 ≤ N ≤ 2 * 105
  • 1 ≤ t, d ≤ 109
  • Evenimentele vor fi date in ordine cronologica.
  • Intr-un moment de timp poate fi atacata o singura usa (nu se intampla doua evenimente simultan).
  • Vor fi cel mult 106 evenimente in fisierul de intrare.

Exemplu

fnaf.infnaf.out
3
3 3
1 D
2 S
4 D
3 4
6 S
8 D
9 S
2 10
10 S
25 S
9
-1
15

Explicaţie

Testul 1
Inchidem usa dreapta la momentul -2 pana la 1, apoi inchidem usa stanga in intervalul de timp [1, 4] si apoi usa dreapta in intervalul [4, 7].

Testul 2
E imposibil pentru ca intre primul si ultimul eveniment sunt 3 secunde si usa trebuie sa stea inchisa cel putin 4 secunde, asa ca nu putem satisface al doilea eveniment fara sa ratam unul dintre primul sau ultimul eveniment.

Testul 3
Inchidem usa la momentul 10 si o tinem inchisa pana la 25.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?