De ce contează?
La un joc pe calculator apeși tasta dreapta și personajul se mută; apeși spațiu și sare. Fiecare apăsare e un eveniment care schimbă ce e pe ecran. Simularea unui sistem e exact asta: o listă de evenimente, fiecare modificând starea după o regulă.
Ce este un eveniment
Un eveniment e o regulă care transformă starea curentă în starea următoare. Primește sistemul așa cum e acum și îl modifică: „intră o mașină”, „becul k se aprinde”, „robotul face un pas”.
În cod, un eveniment e de obicei o modificare a reprezentării (un element de vector, un contor) plus, eventual, o verificare dinainte.
Schema oricărei simulări: stare inițială → aplici evenimentele în ordine → stare finală. Fiecare eveniment pornește din starea lăsată de cel dinainte. Ordinea contează.
Pas cu pas pe numere
Parcaj cu 5 locuri (0 = liber, 1 = ocupat), stare inițială toate libere. Evenimente: intra 2, intra 0, iese 2, intra 4.
| loc | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 |
eveniment "intra 2": locul 2 era liber -> devine 1 -> 0 0 1 0 0
eveniment "intra 0": locul 0 era liber -> devine 1 -> 1 0 1 0 0
eveniment "iese 2" : locul 2 era ocupat -> devine 0 -> 1 0 0 0 0
eveniment "intra 4": locul 4 era liber -> devine 1 -> 1 0 0 0 1
stare finala: 1 0 0 0 1 (2 locuri ocupate)| loc | 1 | 0 | 0 | 0 | 1 |
0 | 1 | 2 | 3 | 4 |
Implementare C++
#include <iostream>
#include <string>
using namespace std;
int loc[100]; // 0 = liber, 1 = ocupat
int main() {
int n, q;
cin >> n >> q; // n locuri, q evenimente
// stare initiala: toate libere (vector global = 0)
for (int e = 0; e < q; e++) {
string tip;
int p;
cin >> tip >> p; // ex: "intra 2" sau "iese 2"
if (tip == "intra") {
if (loc[p] == 0) loc[p] = 1; // verificam: locul era liber
} else { // "iese"
if (loc[p] == 1) loc[p] = 0; // verificam: locul era ocupat
}
}
int ocupate = 0;
for (int i = 0; i < n; i++) ocupate += loc[i];
cout << "Locuri ocupate: " << ocupate << "\n";
return 0;
}Verificările loc[p] == 0 / == 1 sunt precondiții: un eveniment imposibil (intri pe un loc deja ocupat) nu trebuie să strice starea.
Complexitate
| Aspect | Cost |
|---|---|
| Un eveniment (modificare simplă) | O(1) |
| Q evenimente | O(Q) plus eventual O(n) la final |
Greșeli frecvente de concurs:
- Ignori precondiția. „Iese o mașină” dintr-un loc gol, sau „intră” pe unul ocupat — dacă nu verifici, starea devine incoerentă (contoare negative, dubluri).
- Schimbi ordinea evenimentelor. Simularea respectă ordinea dată. A le sorta sau a le aplica invers schimbă rezultatul.
- Actualizezi parțial starea. Dacă un eveniment afectează mai multe componente (vector și contor), actualizează-le pe toate, altfel se desincronizează.
- Recalculezi totul la fiecare eveniment. Dacă poți actualiza starea în O(1) (un singur loc), n-o reparcurge complet de fiecare dată — devine lent la Q mare.
Recapitulare
- Un eveniment transformă starea curentă în următoarea, după o regulă (cu eventuală precondiție).
- Simularea = stare inițială → aplici evenimentele în ordine → stare finală.
- Verifică validitatea înainte de a aplica și actualizează toate componentele stării afectate.