Diferente pentru problema/echilibru intre reviziile #15 si #2

Diferente intre titluri:

Echilibru
echilibru

Diferente intre continut:

== include(page="template/taskheader" task_id="echilibru") ==
Fie o multime de $2 * N$ pietre de diferite greutati. Sa se determine daca acestea pot fi partitionate in doua submultimi de cardinal egal (aceelasi numar de elemente = $N$) astfel incat daca punem pe cele doua talere ale unei balante cele doua submultimi de pietre, balanta se afla in echilibru.
Fie o multime de *2*N* pietre de diferite greutati. Sa se determine daca acestea pot fi partitionate in doua submultimi de cardinal egal (aceelasi numar de elemente N) astfel incat daca punem pe cele doua talere ale unei balante cele doua submultimi, balanta se afla in echilibru.
h2. Date de intrare
Fişierul de intrare $echilibru.in$ contine pe prima linie numarul de teste $T$. Pe urmatoarele $T$ linii se afla descrierile fiecarui test:
Primul numar este $N$ si este urmat de $2 * N$ numere $G{~i~}$, greutatea fiecarei pietre. Aceste numere sunt separate printr-un singur spatiu.
Fişierul de intrare $echilibru.in$ contine pe prima linie numarul de teste *T*. Pe urmatoarele T linii se afla descrierile fiecarui test:
Primul numar este N si este urmat de 2 * N numere G{~i~}, greutatea fiecarei pietre. Aceste numere sunt separate printr-un singur spatiu.
h2. Date de ieşire
Pentru fiecare test raspunsul poate fi codificat prin $1$ sau $0$, daca se poate sau nu sa se partitioneze pietrele in doua submultimi de cardinal si suma egale. In fisierul $echilibru.out$ afisati un singur numar, care reprezinta valoarea in baza $10$ a numarului care e reprezentat de $T$ biti cu valoarea codificarii raspunsului pentru fiecare test in ordine.
Pentru fiecare test raspunsul poate fi codificat prin 1 sau 0, daca se poate sau nu sa se partitioneze pietrele in doua submultimi de cardinal si suma egale. In fisierul $echilibru.out$ afisati un singur numar, care reprezinta valoarea in baza 10 a numarului care e reprezentat de T biti cu valoarea codificarii raspunsului pentru fiecare test in ordine.
h2. Restricţii
* $1 ≤ N ≤ 8$
* $1 ≤ T ≤ 30$
* $0 ≤ G{~i~} ≤ 10^6^$
* 1 ≤ N ≤ 10
* 1 ≤ T ≤ 30
* 0 ≤ G{~i~} ≤ 10^6^
h2. Exemplu
| 4
  2 4 7 6 3
  2 4 8 6 7
  3 2 4 6 2 5 3
  3 1 2 3 4 5 6
| 10
  3 2 4 6 2 5 3
| 9
|
h3. Explicaţie
Pentru primul test raspunsul e $1$ (4 + 6 = 7 + 3), pentru al 2-lea raspunsul e $0$ (nu se poate partitiona), pentru testul 3 raspunsul e $1$ (2 + 4 + 5 = 6 + 2 + 3), iar pentru ultimul test raspunsul e $0$ (nu se poate partitiona).
Pentru primul test raspunsul e *1* (4 + 6 = 7 + 3), pentru al 2-lea raspunsul e *0* (nu se poate partitiona), pentru testul 3 raspunsul e *0* (nu se poate partitiona), iar pentru ultimul test raspunsul e *1* (2 + 4 + 5 = 6 + 2 + 5).
1010{~(2)~} = 10{~(10)~} (primul test va determina valoarea celui mai semnificativ bit, al doilea test celui de-al doilea bit si asa mai departe ...)
1001{~(2)~} = 9{~(10)~}

Nu exista diferente intre securitate.

Diferente intre topic forum:

9724