Thread

thread

== 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") ==

9902