Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | thread.in, thread.out | Sursă | ONIS 2014, Runda Finala |
| Autor | Stefan Ciobaca | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Thread
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.
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.
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.
Restricţii
- 1 ≤ T ≤ 50
- 1 ≤ N ≤ 256
- 0 ≤ c_i ≤ 256
Exemplu
| thread.in | thread.out |
|---|---|
| 1 1 1 2 | 3 |
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)
