Simulări pe vectori — sistemul trăiește într-un șir

De ce contează?

Un șir de oameni la coadă, fiecare pasează o minge celui din dreapta. Dacă toți o pasează „în același timp”, mingea se mută o poziție. Dar dacă fiecare o pasează imediat ce o primește, ajunge instantaneu la capăt. Diferența — actualizare simultană sau în cascadă — e inima simulărilor pe vectori.

Când folosești un vector

Reprezinți sistemul printr-un vector când obiectele stau pe o linie: au o singură coordonată (poziția). Becuri, locuri de parcare, căsuțe pe un drum, oameni la coadă. Indexul vectorului = poziția.

Simularea modifică elementele vectorului pe măsură ce aplici evenimentele.

Observația-cheie

Capcana centrală: când noua valoare a unei celule depinde de vecinii ei, actualizarea „pe loc” poate strica valoarea veche de care are nevoie celula următoare. Soluția: un al doilea vector pentru noua stare.

Exemplu: propagarea unui val

Pe un șir, o celulă „activă” (1) le activează pe vecinele ei la pasul următor. Stare inițială: doar poziția 3 e activă. Vrem starea după un pas.

cur	0	0	0	1	0	0	0
	0	1	2	3	4	5	6

Starea curentă: activă doar poziția 3

Regula: next[i] = 1 dacă i sau un vecin al lui erau activi.

next	0	0	1	1	1	0	0
	0	1	2	3	4	5	6

Noua stare: 3 a rămas activă și i-a activat pe 2 și 4

Dacă am fi scris direct în același vector de la stânga la dreapta, activarea lui 2 ar fi influențat greșit calculul pentru 3 — de-aceea folosim next.

Implementare C++

#include <iostream>
using namespace std;

int cur[100], next_[100]; // doua stari: curenta si urmatoarea

int main() {
    int n, pasi;
    cin >> n >> pasi;
    for (int i = 0; i < n; i++) cin >> cur[i];

    for (int t = 0; t < pasi; t++) {
        for (int i = 0; i < n; i++) {
            int activ = cur[i];
            if (i > 0 && cur[i - 1] == 1) activ = 1;     // vecin stang
            if (i < n - 1 && cur[i + 1] == 1) activ = 1; // vecin drept
            next_[i] = activ; // scriem in next, citim din cur
        }
        for (int i = 0; i < n; i++) cur[i] = next_[i]; // trecem la noua stare
    }

    for (int i = 0; i < n; i++) cout << cur[i] << " ";
    cout << "\n";
    return 0;
}

Citim mereu din cur, scriem în next_, apoi copiem. Toate celulele „văd” aceeași stare veche → actualizare simultană.

Complexitate

Aspect	Cost
Un pas de simulare	O(n)
`pasi` pași	O(pasi · n)
Memorie	O(n) (două vectoare)

Greșeli frecvente

Greșeli frecvente de concurs:

Actualizare în cascadă neintenționată. Scrierea pe loc când valoarea depinde de vecini propagă efectul în același pas. Folosește next când e nevoie de simultaneitate.
Acces în afara vectorului. La capete, cur[i-1] sau cur[i+1] ies din vector. Verifică i > 0 și i < n-1 înainte.
Uiți să copiezi next în cur. Fără pasul de „trecere la noua stare”, simularea rămâne blocată în starea inițială.
Confunzi pașii cu evenimentele. Un „pas” aici e o actualizare a întregului vector; nu-l confunda cu un eveniment punctual pe o singură celulă.

Recapitulare

Folosești un vector când obiectele au o singură coordonată (poziția pe o linie).
Când noua valoare depinde de vecini, calculează în next citind din cur, apoi interschimbă — actualizare simultană.
Atenție la margini și la pasul de copiere next → cur; cost O(pasi · n).