Correction de copies – Épreuve régionale 2014

Niveau 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

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
2000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5
2 5 3 4 2
Exemple de sortie
1
Commentaire

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.

Exemple d'entrée
8
30 5 3 4 2 3 7 8
Exemple de sortie
0
Commentaire

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

Exemple d'entrée
10
33 8 13 12 61 19 42 12 31 55
Exemple de sortie
1