Anniversaires – Regional event 2011

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

Runtime constraints

Maximum memory usage
2048 kilobytes
Maximum execution time
400 milliseconds

Input/output samples

Sample input
2
20 20
Sample output
30
Sample input
4
10 20 30 40
Sample output
70
Sample input
3
80 10 80
Sample output
125
Note

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.

Submit your solution

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