== include(page="template/taskheader" task_id="thread") ==
Poveste şi cerinţă...
Gigel are N thread-uri, numerotate de la $1$ la $N$. Thread-ul $i$ ({$1 ≤ i ≤ N$}) execută operaţia $x += c{~i~}$.
Execuţia operaţiei $x += c{~i~}$ este alcătuită din următoarele operaţii atomice:
- se citeşte valoarea lui $x$ din memorie,
- se adaugă la aceasta $c{~i~}$,
- se scrie rezultatul în memorie.
Iniţial valoarea lui $x$ este $0$. Cele $N$ thread-uri se execută în paralel. Când thread-urile se execută in paralel, operaţiile atomice ale acestora sunt intercalate într-un mod la alegerea sistemului. Se cere să se găseasca câte valori posibile poate lua variabila $x$ la sfârşitul execuţiei tuturor thread-urilor.
h2. Date de intrare
Fişierul de intrare $thread.in$ ...
Pe prima linie din fişierul de intrare $thread.in$ se găseşte numărul $T$ de teste.
Pe urmatoarele linii se găsesc testele.
Prima linie din fiecare test conţine numărul $N$ de thread-uri.
A doua linie din fiecare test conţine numerele $c{~1~}$, ..., $c{~N~}$.
h2. Date de ieşire
În fişierul de ieşire $thread.out$ ...
Pentru fiecare test, afişati pe câte o linie a fişierului de ieşire $thread.out$ câte valori posibile poate lua $x$ la sfârşitul execuţiei.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1$ ≤ $T$ ≤ $128$
* $1$ ≤ $N$ ≤ $256$
* $0$ ≤ $c_i$ ≤ $256$
h2. Exemplu
table(example). |_. thread.in |_. thread.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
2
1 2
| 3
|
h3. Explicaţie
...
Cele două thread-uri sunt $x += 1$ şi $x += 2$.
La sfârşitul execuţiei, sunt $3$ valori posibile pentru $x$: $1$, $2$ şi $3$.
Valoarea $1$ se poate obţine astfel:
- începe primul thread (citeste $x$, care este $0$)
- se execută complet al doilea thread, dupa care $x$ devine $2$
- se continuă de executat primul thread (se adună $1$ la valoarea $0$ a lui $x$ citită la început)
Valoarea $2$ se poate obţine astfel:
- incepe al doilea thread (citeste $x$, care este $0$)
- se execută complet primul thread, după care $x = 1$
- se continuă de executat al doilea thread (se adună $2$ la valoarea $0$ a lui $x$ citită la început)
Valoarea $3$ se poate obţine astfel:
- se execută complet primul thread (dupa care $x = 1$)
- se execută complet al doilea thread (dupa care $x = 3$)
== include(page="template/taskfooter" task_id="thread") ==
