Sujet 2 (B)

On considère une suite $\left(u_n\right)_{n\geq1}$ définie par ses deux premiers termes $u_1$ et $u_2$ de la manière suivante : entre la n-ieme et la (n+1)-ieme occurrence de $u_1$ dans la suite, $u_2$ est répété $u_n$ fois. Par exemple, si $u_1=4$ et $u_2=2$, la suite commence par 4 2 2 2 2 4 2 2 4 2 2 4 2 2 4 2 2 4 2 2 2 2 4 (les "2"s sont par blocs de 2 ou 4 et la suite du nombre de "2" entre deux "4" successif est la suite u elle-même). Etant donnés $u_1$, $u_2$ et n, trouver $u_n$.

Limites de temps et de mémoire (Python)

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

Entrée

L'entrée du programme contient une ligne pour $u_1$, une pour $u_2$ et une pour n, le tout suivi d'un retour à la ligne. $u_1$ et $u_2$ sont des chiffres distincts et non-nuls, $u_n$ est un entier strictement positif. Dans les cas de tests, n n'excédera jamais 1000000.

Sortie

La sortie du programme doit être $u_n$, suivi d'un retour à la ligne.

Exemples

Exemple 1

entrée :

4
2
9

sortie :

4

Exemple 2

entrée :

7
3
1337

sortie :

7

Exemple 3

entrée :

7
4
1000000

sortie :

4

Commentaires

Squelettes de codes :

(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les 
mettre dans des variables, et afficher votre resultat final en sortie. *)

(* On lit la somme a atteindre, en cents, et on la stocke dans un entier n *)
let u1 = int_of_string (input_line stdin);;
let u2 = int_of_string (input_line stdin);;
let n = int_of_string (input_line stdin);;

(* fonction pour afficher votre solution *)
let affiche_solution i =
  print_int i;
  print_newline();;

(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)

(* Debut de votre programme *)


(* Fin de votre programme *)


Source : http://www.france-ioi.org/