Jump – Épreuve régionale 2014

Niveau 1

Enoncé

Mario, quand il s'ennuie dans son travail de plombier, devient astronaute et s'amuse à sauter de planète en planète.

Il a devant lui une ligne de planètes toutes espacées de telle sorte que depuis l'une d'entre elles, Mario ne puisse sauter que d'un peu moins de la moitié de la distance qui la sépare d'une de ses deux voisines. La planète d'arrivée doit donc avoir une gravité strictement plus forte que celle de départ si Mario souhaite atterrir dessus.

Afin de commencer à planifier son voyage galactique, Mario souhaite savoir combien de planètes sont atteignables depuis une planète voisine.

Entrée

  • Sur la première ligne, le nombre n de planète.
  • Sur la deuxième ligne, les tailles si des planètes.

Sortie

Le nombre de planètes atteignables par ses voisines.

Contraintes

  • 1 <= n <= 20 000
  • 0 <= si <= 10 000

Contraintes d'exécution

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

Exemples d'entrée/sortie

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

La deuxième, troisième, cinquième et sixième planète sont atteignables car au moins une de leur voisine a une gravité plus faible.

Exemple d'entrée
5
10 5 20 15 20
Exemple de sortie
3
Exemple d'entrée
20
233 138 758 930 579 895 955 841 401 528 907 120 211 119 282 405 853 861 459 536
Exemple de sortie
14