== include(page="template/taskheader" task_id="thread") ==
Gigel are N thread-uri, numerotate de la $1$ la $N$. Thread-ul $i$ ({$1 ≤ i ≤ N$}) execută operaţia $x += c{~i~}$.
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.
Operaţia $x += c ~i~$ este alcatuită din urmatoarele operatii atomice:
- se citeste valoarea lui x din memorie,
- se adauga la aceasta c_i,
- se scrie rezultatul in memorie.
Initial valoarea x este 0 si cele N thread-uri se executa in paralel. Cand doua thread-uri se executa in paralel, operatiile atomice executate de threaduri sunt intercalate. Se cere sa se gaseasca cate valori posibile poate lua variabila x la sfarsitul executiei tutoror thread-urilor.
h2. Date de intrare
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~}$.
Fişierul de intrare $thread.in$ ...
h2. Date de ieşire
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.
În fişierul de ieşire $thread.out$ ...
h2. Restricţii
* $1$ ≤ $T$ ≤ $128$
* $1$ ≤ $N$ ≤ $256$
* $0$ ≤ $c_i$ ≤ $256$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. thread.in |_. thread.out |
| 1
2
1 2
| 3
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
