Echilibru

echilibru

== 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 de pietre, 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 ≤ 8
* 1 ≤ T ≤ 30
* 0 ≤ G{~i~} ≤ 10^6^

h2. Exemplu

  2 4 8 6 7
  3 2 4 6 2 5 3
  3 1 2 3 4 5 6

| 10

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

1010{~(2)~} = 10{~(10)~}

9724