Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | fnaf.in, fnaf.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 18 |
| Autor | George Marcus | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 1 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
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 o inchizi ca sa te aperi. 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)).
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 (exceptie momentul cand se deschide o usa si se inchide cealalta - clarificare in primul exemplu).
Gasiti timpul total minim in care usile vor sta inchise daca Georgel joaca optim.
Date de intrare
Fişierul de intrare fnaf.in ...
Date de ieşire
În fişierul de ieşire fnaf.out ...
Restricţii
- 1 ≤ N ≤ 106
- 1 ≤ t, D ≤ 109
Exemplu
| fnaf.in | fnaf.out |
|---|---|
| 3 3 3 1 S 4 S 4 D 3 4 6 S 8 D 9 S 2 10 10 S 25 S | 6 -1 15 |
Explicaţie
Testul 1
Usa stanga poate fi inchisa in intervalul de timp [1,4] (satisfacand evenimentele 1,2) si a usa dreapta in intervalul [4,7] (satisfacand evenimentul 3).
De notat faptul ca avem voie sa avem doua usi inchise simultan doar in cazul in care se schimba usa inchisa.
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.
