Anniversaires – Épreuve régionale 2011

Niveau 2

Énoncé

Joseph Marchand produit des ballons de baudruche. Pour monétiser au mieux son activité, il regarde régulièrement sur VisageLivre™ les anniversaires de ses amis afin de leur vendre des ballons. Cependant, Joseph Marchand est fainéant et veut donc produire tous ses ballons en une fois pour être tranquille ensuite. Il veut évidemment aussi en produire le nombre minimal.

Pour chaque anniversaire, un nombre B de ballons est nécessaire. À la fin de l'anniversaire, B/2 ballons sont craqués et les autres B/2 ballons sont encore en bon état. Radin comme il est, Joseph les récupère pour les anniversaires suivants.

En supposant que vous ayez la liste des N prochains anniversaires, déterminez le nombre de ballons à produire au départ pour en avoir suffisamment pour tous les anniversaires.

Entrée

  • Sur la première ligne, l'entier N.
  • Sur la seconde ligne, le nombre B de ballons nécessaire pour chaque anniversaire.

Sortie

Le nombre minimal de ballons à produire au départ pour satisfaire le besoin de tous les anniversaires.

Contraintes

  • 1 <= N <= 10 000
  • 2 <= B <= 10 000
  • B pair.

Contraintes d'exécution

Utilisation mémoire maximum
2048 kilo-octets
Temps d'exécution maximum
400 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
2
20 20
Exemple de sortie
30
Exemple d'entrée
4
10 20 30 40
Exemple de sortie
70
Exemple d'entrée
3
80 10 80
Exemple de sortie
125
Commentaire

Si on prend en entrée ces 3 anniversaires : 80, 10 et 80.
On voit qu'il faut :

  • 80 ballons pour le premier, j'en ai 0, il m'en faut 80, il m'en reste 0 + 80/2 = 40 ;
  • 10 ballons pour le second, j'en ai 40, il m'en faut 0, il m'en reste 30 + 10/2 = 35 ;
  • 80 ballons pour le dernier, j'en ai 35, il m'en faut 45, et on se fiche du reste.
Il me faut alors au total : 80 + 0 + 45 ballons, soit 125.