Champ d'astéroïdes – Épreuve régionale 2020

Niveau 2

Énoncé

L'équipage AlphaX1 en mission pour rejoindre une planète lointaine potentiellement habitable se retrouve malheureusement au cours de son voyage nez à nez avec un champ d'astéroïdes.

Il va devoir consommer du carburant pour éviter les astéroïdes sur son passage, mais il n'y en a qu'une quantité limitée $V$ dans les réservoirs. L'équipage a besoin de vous afin de déterminer s'il a suffisamment de carburant pour éviter tous les astéroïdes sur sa route ou s'il est condamné. Pour éviter un astéroïde de taille $T$, l'ordinateur de bord d'AlphaX1 estime avoir besoin de $T * C$ litres de carburant. Fort de votre expérience vous savez que :

  • Un astéroïde de taille <= 20 ne nécessitera jamais plus que 40L de carburant.
  • Un astéroïde de taille >= 80 ne nécessitera jamais plus que 120L de carburant.

Votre but étant de calculer la quantité optimale de carburant nécessaire pour traverser le champ d'astéroïdes ou -1 s'il n'y a pas assez de carburant.

Entrée

  • Sur la première ligne, le volume de carburant $V$ disponible.
  • Sur la deuxième ligne, la quantité de carburant $C$ nécessaire pour éviter un astéroïde de taille 1.
  • Sur la troisième ligne, le nombre $N$ d'astéroïdes.
  • Sur la dernière ligne, $N$ entiers séparés par des espaces représentant les tailles $T_i$ des astéroïdes du chemin.

Sortie

Vous afficherez en sortie la quantité de carburant nécessaire pour traverser le champ d'astéroïdes ou -1 s'il n'y a pas assez de carburant.

Contraintes

  • $1 \le V \le 1000$
  • $1 \le C \le 100$
  • $1 \le N \le 50$
  • $1 \le T_i \le 100$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
500
3
4
15 50 30 80
Exemple de sortie
400
Commentaire

Ici l'équipage possède 500 litres de carburant, et l'ordinateur anticipe que le vaisseau devra consommer 3 fois la taille de chaque astéroïde en carburant afin de les éviter.

Pour le premier astéroïde cela représente 15 * 3 = 45 litres, or vous savez par expérience qu'il n'en faudra jamais plus que 40 litres (l'astéroïde étant assez petit).

Le deuxième et troisième astéroïdes nécessitent 50 * 3 = 150 et 30 * 3 = 90 litres.

Pour le dernier, 80 * 3 = 240 litres mais encore une fois de votre expérience cet astéroïde ne demandera pas plus de 120 litres de carburant.

Au total c'est donc 40 + 150 + 90 + 120 = 400 litres qui seront utilisés.

Exemple d'entrée
250
5
6
20 13 3 10 5 23
Exemple de sortie
-1
Commentaire

Au total ce sont 40 + 40 + 15 + 40 + 25 + 115 = 275 litres nécessaires.

L'équipage n'a donc pas assez de carburant en réserve.