Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-05-17 17:31:20.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:thread.in, thread.outSursăONIS 2014, Runda Finala
AutorStefan CiobacaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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

  • 1T50
  • 1N256
  • 0c_i256

Exemplu

thread.inthread.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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?