Correction de copies – Regional event 2014

Level 5

Enoncé

Rien ne va plus dans les bureaux de Prologin. Il ne reste qu'un mois avant la finale, et les finalistes n'ont toujours pas été sélectionnés.

La plupart des organisateurs étant occupés à des activités passionnantes, telles que la logistique, l'administration système ou le débogage du sujet de la finale, il ne reste plus que deux personnes pour corriger les copies des candidats.

Pour aller le plus rapidement possible, on fera corriger toutes les copies d'une même épreuve par la même personne, afin de minimiser le nombre de sujets à maîtriser pour chacun des deux correcteurs.

À partir du nombre de copies de chaque épreuve, on aimerait savoir s'il existe une façon de répartir équitablement les copies entre les deux correcteurs.

Entrée

  • Sur la première ligne, le nombre n d'épreuves régionales

  • Sur la seconde ligne, n entiers li, correspondant aux nombres de copies pour chaque épreuve.

Sortie

1 s'il est possible de répartir équitablement les copies entre les deux correcteurs, 0 sinon.

Contraintes

  • 2 <= n <= 1 000
  • 0 <= li <= 10 000
  • 2 <= Σ li <= 40 000

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
5
2 5 3 4 2
Sample output
1
Note

On peut répartir les paquets comme ceci : {5, 3} et {4, 2, 2}. En effet, 5 + 3 = 8 et 4 + 2 + 2 = 8. On renvoie donc vrai.

Sample input
8
30 5 3 4 2 3 7 8
Sample output
0
Note

On a beau chercher, il n'y a aucun moyen de répartir équitablement ces copies… on renvoie donc 0.

Sample input
10
33 8 13 12 61 19 42 12 31 55
Sample output
1

Submit your solution

You have to register or log in to be able to submit your solution.