Șmenul lui Mars


Editat de Candale Silviu (silviu) la data 2018-09-15

Vezi Șmenul lui Mars pe infoarena.ro!

“Șmenul lui Mars” este o metodă de gestionare unor operații pe secvențe într-un vector atribuită lui Marius Andrei (mars), binecunoscută sub acest nume în lumea olimpicilor la informatică. Neștiind un nume mai bun, îl păstrăm și aici!

Să presupunem că avem un vector A[] cu n elemente, indexate de la 1 la n, inițial nule, în care se fac mai multe operații Adună(s,d,X) prin care toate elementele din secvența delimitată de indicii s d cresc cu valoarea X. Se cere afișarea elementelor din A după efectuarea acestor operații.

Operațiile pot fi efectuate eficient construind un vector suplimentar B[], cu n+1 elemente, astfel încât A[i]=B[1]+B[2]+...+B[i]. Operația Adună(s,d,X) devine: B[s] += x, B[d+1] -= x;

La final, elementele lui A se reconstituie astfel: A[i]=B[1]+B[2]+...+B[i]

A[1] = B[1];
for(int i = 2 ; i <= n ; i ++)
    A[i] = A[i-1] + B[i];

Fișiere atașate


Probleme ataşate

Nr. Problema Clasa Dificultate Operații I/O
1 #1222 - TV 10 concurs fișiere
2 #1233 - Paint 9 concurs fișiere
3 #1268 - EasyQuery 9 dificilă fișiere
4 #1512 - Mars 9 dificilă consola
5 #1835 - twoop 9 concurs fișiere
Editat de Candale Silviu (silviu) la data 2018-09-15