Coffre-fort

Vous êtes preneur de son, spécialisé dans l'enregistrement du cri d'animaux tels que la Carpe Muette De Chine Orientale et le Ver Annelé Tubicole Des Fumeurs Noires. Ne parvenant à effectuer que très peu de prises correctes, vous avez décidé de vous reconvertir dans la redistribution de richesses au profit de soi, profession bien plus lucrative. Plus précisément, vous vous spécialisez dans le cambriolage de coffres-forts, en particulier ceux dont le code doit être fourni en tournant une roue graduée vers diverses positions successives.

Vous cachez un micro à côté du coffre-fort de la victime, vous notez le numéro que porte la roue, puis vous enregistrez les clics produits par ladite roue lorsque le propriétaire du coffre effectue la combinaison. Grâce à votre ouïe fort développée, vous parvenez à compter les clics de chaque déplacement, ainsi qu'à deviner dans quel sens la roue est tournée.

Votre objectif est maintenant de retrouver la combinaison du coffre, à partir de la position initiale de la roue, ainsi que du nombre de crans et du sens de chaque déplacement.

Limites de temps et de mémoire (Python)

  • Temps : 1,5 s sur une machine à 1 GHz.
  • Mémoire : 32 000 ko.

Contraintes

  • 2 <= N <= 10 000, où N est le nombre de crans sur la roue du coffre-fort. La roue est numérotée de 0 à N-1 inclus.
  • 0 <= P < N, où P est la position initiale de la roue du coffre-fort.
  • 0 <= M <= 10 000, où M est le nombre de mouvements effectués sur la roue du coffre-fort.
  • -N < Ki < N, où Ki est le nombre de crans dont la roue est tournée au mouvement i. Ki > 0 si la roue est tournée dans le sens des numéros de position croissants, Ki < 0 si la roue est tournée dans l'autre sens. Les Ki sont tous différents de zéro.

Entrée

  • La première ligne de l'entrée contient trois entiers séparés par des espaces : N, P et M.
  • Chacune des M lignes suivantes contient un entier Ki par mouvement, le nombre de crans dont la roue est tournée au mouvement i.

Sortie

Vous devez écrire K entiers à raison d'un par ligne. La ligne numéro i doit donner la position de la roue du coffre-fort après le mouvement Ki. La dernière ligne doit donc contenir la position finale de la roue du coffre-fort, après tous les mouvements. Chaque position doit être un entier compris entre 0 et N-1 inclus.

Exemple

entrée :

10 3 5
2
8
-5
9
3

sortie :

5
3
8
7
0

Commentaires

L'illustration suivante correspond à l'exemple d'entrée :

Squelette de code C++:

#include <cstdio>

int main()
{
   // lecture de l'entrée
   int tailleRoue, posInitiale, nbMouvements;
   scanf("%d%d%d", &tailleRoue, &posInitiale, &nbMouvements);
   ...
      // lecture d'un mouvement
      int nbCrans;
      scanf("%d", &nbCrans);
      ...
      // affichage d'une position
      printf("%d\n", ...);
   ...
   return 0;
}
Squelette de code Caml:
let scan_int () = Scanf.scanf " %d" (fun x -> x)
let show_int x  = Printf.printf "%d\n" x

let taille_roue = scan_int()
let position_initiale = scan_int()
let nb_mouvements = scan_int()

let _ =
   ...
      (* lecture d'un mouvement *)
      let nb_crans = scan_int() in
      (* affichage d'une position *)
      show_int ...;
   ...
   
(* Note: ne pas mettre de point-virgule à la fin du code *)

Source : https://www.france-ioi.org/ Créé par : Guillaume Ryder.