Programare Competitivă

Simulări

O simulare e un program care imită pas cu pas un proces din lumea reală sau dintr-un scenariu abstract. În loc să găsim o formulă directă sau un algoritm complicat, urmăm instrucțiunile problemei literal — poziție cu poziție, tact cu tact.

Multe probleme de olimpiadă (mai ales la clasele mici) sunt exact asta: nu cer vreo idee genială, ci doar să transpui corect în cod ce zice enunțul.

Când folosești simulare?

  • Enunțul descrie un proces cu pași repetitivi: „la fiecare secundă…“, „pentru fiecare rundă…”, „un robot se mișcă…”
  • Limitele sunt mici (N, T ≤ 10⁴ – 10⁵), deci îți permiți să execuți toți pașii.
  • Nu vezi o formulă simplă sau un pattern matematic.
  • Regulile sunt clare dar complexe — un algoritm „deștept” ar fi greu de conceput, dar respectarea regulilor literal e directă.

Ce fac eu?

Înainte să încep o rezolvare, încerc să descopăr la ce s-a gândit autorul…

Componentele unei simulări

Orice simulare are trei piese:

1. Reprezentarea sistemului

Cum stocăm informația despre „lumea” pe care o simulăm.

  • Variabile simple (poziții x, y, viteze vx, vy, un contor).
  • Vectori / matrici (o hartă, o listă de obiecte).
  • Struct-uri (când fiecare obiect are mai multe atribute).

2. Starea sistemului

O „fotografie” a tot ce e necesar la un moment dat. Trebuie să alegi ce stochezi:

// Exemplu: minge pe grilă
int x, y;         // poziția
int dx, dy;       // direcția
int pas;          // al câtelea pas

Regulă: starea trebuie să conțină tot ce ai nevoie pentru a calcula următorul pas. Dacă uiți un detaliu, simularea iese greșită.

3. Bucla de evenimente (time loop)

O buclă care avansează starea un pas o dată:

cât timp nu s-a terminat simularea:
    1. privești starea curentă
    2. aplici regulile → starea nouă
    3. (opțional) notezi/afișezi ceva

Șablon general

// 1. inițializează starea
citește datele inițiale;

// 2. simulează T pași
for (int t = 1; t <= T; t++) {
    // aplică regulile de tranziție
    calculează noua stare pe baza celei vechi;
    actualizează variabilele;
}

// 3. afișează rezultatul final
fout << stareaFinala;

Exemplu 1: minge care sare într-un dreptunghi

O minge pornește din (x, y) și se mișcă cu direcția (dx, dy) într-un dreptunghi N × M. La fiecare pas își schimbă poziția. Când lovește un perete, direcția se inversează pe axa respectivă. Unde se află după T pași?

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main() {
    int N, M, x, y, dx, dy, T;
    fin >> N >> M >> x >> y >> dx >> dy >> T;

    for (int t = 1; t <= T; t++) {
        x += dx;
        y += dy;

        // reflexie pe pereți
        if (x < 1) { x = 2 - x; dx = -dx; }
        if (x > N) { x = 2 * N - x; dx = -dx; }
        if (y < 1) { y = 2 - y; dy = -dy; }
        if (y > M) { y = 2 * M - y; dy = -dy; }
    }

    fout << x << " " << y;
    return 0;
}

Starea: (x, y, dx, dy).
Tranziția: poziție += direcție, apoi reflexie la perete.
Complexitate: O(T).

Exemplu 2: turist pe hartă cu direcții

Un turist primește o secvență de comenzi: N (nord), S (sud), E (est), V (vest). Pornește din (0, 0). Care e cea mai lungă distanță de origine pe care o atinge?

#include <fstream>
#include <string>
#include <cmath>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main() {
    string cmd;
    fin >> cmd;

    int x = 0, y = 0;
    int maxDist = 0;

    for (char c : cmd) {
        if (c == 'N') y++;
        else if (c == 'S') y--;
        else if (c == 'E') x++;
        else if (c == 'V') x--;

        int dist = x * x + y * y;
        if (dist > maxDist) maxDist = dist;
    }

    fout << maxDist; // pătratul distanței (să evităm sqrt)
    return 0;
}

Truc: comparăm pătratele distanțelor — evităm sqrt (mai lent și impreciz).

Exemplu 3: coadă la bancă (event-driven)

N clienți vin la bancă. Clientul i sosește la momentul t[i] și are nevoie de d[i] minute. Există un singur casier. Calculează timpul total de așteptare.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main() {
    int N;
    fin >> N;

    int timpCurent = 0;
    long long asteptareTotala = 0;

    for (int i = 0; i < N; i++) {
        int t, d;
        fin >> t >> d;

        if (timpCurent < t) timpCurent = t; // casierul așteaptă clientul
        else asteptareTotala += timpCurent - t; // clientul așteaptă casierul

        timpCurent += d; // clientul e servit
    }

    fout << asteptareTotala;
    return 0;
}

Starea: timpCurent (când se eliberează casierul).
Eveniment: sosirea unui client.
Regulă: max(timpCurent, t) + d.

Exemplu 4: evaporarea unei matrici

Avem o matrice N × M cu valori. La fiecare secundă, fiecare celulă își pierde 1 unitate (dar nu coboară sub 0). Câte secunde până toată matricea devine 0?

int maxim = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i][j] > maxim) maxim = a[i][j];

fout << maxim; // numărul de secunde = cea mai mare valoare

Optimizare: aici simularea pas cu pas ar fi O(N·M·T). Dar observăm că răspunsul e chiar maximul din matrice → O(N·M). Când poți, înlocuiește simularea cu raționament matematic.

Exemplu 5: Jocul Vieții (Game of Life simplu)

Matrice de N × N celule. La fiecare tact:

  • O celulă moartă cu exact 3 vecini vii devine vie.
  • O celulă vie cu 2 sau 3 vecini vii rămâne vie. Altfel, moare.

Câte celule vii sunt după T tacturi?

int a[50][50], b[50][50];
int N, T;

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

void pas() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            int vecini = 0;
            for (int d = 0; d < 8; d++) {
                int ni = i + dx[d], nj = j + dy[d];
                if (ni >= 0 && ni < N && nj >= 0 && nj < N && a[ni][nj] == 1)
                    vecini++;
            }
            if (a[i][j] == 1) b[i][j] = (vecini == 2 || vecini == 3) ? 1 : 0;
            else              b[i][j] = (vecini == 3) ? 1 : 0;
        }
    // copiez b în a
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) a[i][j] = b[i][j];
}

Regulă de aur pentru simulări pe matrice cu vecini: folosește două matrici — una veche, una nouă. Altfel, modificările făcute la (i, j) afectează calculul pentru (i+1, j) și strici totul.

Șablon: simulare cu două stări (copie ↔︎ original)

Pentru procese simultane (toate celulele se actualizează în același tact):

int a[NMAX][NMAX]; // starea curentă
int b[NMAX][NMAX]; // starea următoare

for (int t = 1; t <= T; t++) {
    // calculează b din a
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            b[i][j] = regulaTranzitie(a, i, j);

    // copiază b în a
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            a[i][j] = b[i][j];
}

Sau — truc memorie — folosește un singur tablou 3D a[2][N][M] și alternează indicele t % 2:

int a[2][NMAX][NMAX];
int cur = 0;

for (int t = 1; t <= T; t++) {
    int next = 1 - cur;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            a[next][i][j] = regulaTranzitie(a[cur], i, j);
    cur = next;
}
// răspunsul e în a[cur]

Evită copierea explicită.

Când simularea devine prea lentă

Dacă T = 10⁹, simularea directă O(T) nu merge. Soluții:

1. Găsește un ciclu

Multe sisteme intră într-o stare care se repetă după un număr finit de pași. Detectezi ciclul și răspunzi direct.

mapare: stare → primul tact la care a apărut
la fiecare pas:
    dacă stare nouă e deja în mapare:
        ciclu găsit, calculezi direct t % ciclu
    altfel:
        adaugi în mapare

2. Observă invarianți

Dacă suma/maximul/alt ceva nu se schimbă, poți răspunde fără simulare.

3. Ridicarea la putere a matricilor

Pentru tranziții liniare (Fibonacci, grafuri), se folosește exponențiere rapidă pe matrice → O(log T).

4. Simulare leneșă

Nu calculezi ce nu ți se cere. Procesează doar evenimente cheie, sari peste „timpul mort”.

Greșeli frecvente

1. Modificarea stării curente în timpul actualizării

// GREȘIT la matrice cu vecini
for (i, j)
    a[i][j] = regula(a); // următoarea celulă vede valoarea modificată!

Folosește două matrici (sau o matrice 3D cu toggle).

2. Bucle infinite prin uitarea condiției de oprire

while (!gata) {
    // ...
    if (conditie) gata = true; // uitat în niște ramuri
}

Mereu pune un maxim de pași ca siguranță: for (int t = 0; t < MAX_PAȘI && !gata; t++).

3. Off-by-one la indici

Dacă matricea e 1..N × 1..M, vecinii (0, j) sau (N+1, j) sunt în afară. Verifică întotdeauna:

if (ni >= 1 && ni <= N && nj >= 1 && nj <= M) { ... }

4. Starea incompletă

Uiți să stochezi ceva ce afectează tranziția (ex. direcția mingii). Rezultat: simulare greșită, „sare” aleator.

5. Efecte de ordine

La simulări „secvențiale” (fiecare celulă se actualizează pe rând), ordinea de iterare poate schimba rezultatul. Atenție la enunț: „simultan” vs „unul câte unul”.

6. T mare cu simulare O(T)

Verifică complexitatea înainte. Dacă T ≥ 10⁹, caută ciclu sau formulă — nu merge O(T).

Checklist pentru probleme de simulare

Înainte să scrii cod:

Ce să reții

  • Simularea = urmezi regulile problemei pas cu pas, fără șmecherii.
  • Trei componente: reprezentare (variabile) + stare (variabilele la momentul curent) + buclă de evenimente (regulile de tranziție).
  • Șablon: inițializare → for t = 1..T: aplică tranziția → afișează.
  • Pentru procese simultane pe matrice: folosește două tablouri (vechi → nou).
  • Pentru vecini: vectori de direcție dx[], dy[].
  • Evită sqrt când poți compara cu pătratele distanțelor.
  • Dacă T e enorm: caută cicluri, invarianți sau formulă.
  • Simularea e directă — cea mai obișnuită eroare e modificarea stării curente în timp ce o folosești ca input.
Cuprins Inapoi Inainte