Bonnie i Clide P28004

0.72 Bonnie i Clide acaben de robar un banc. Tenen una bossa amb $n$ xecs amb valors enters de diners (curiosament tots al seu nom: ”a pagar a Bonnie o a Clide”) i se la volen dividir completament de tal manera que cadascú rebi exactament la mateixa suma de diners. Podran fer-ho?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de xecs $n$, seguit d’$n$ naturals entre 1 i $1000$. Podeu suposar $1 \le n \le 100$, i que la suma dels valors és un nombre parell.

0.28

Sortida

Per a cada cas, escriviu la mínima diferència possible a l’hora de repartir els xecs.

Observacions

• Es poden obtenir 20 punts amb casos amb $n \le 20$.

• Una solució poc optimitzada pot rebre fins a 80 punts dels 100 totals.