L'héritière informaticienne – Qualification 2007

Level 4

Énoncé

Le problème de Josephus.

Un vieil homme qui a beaucoup (vraiment beaucoup) de descendants (N) veut choisir lequel sera son héritier. Il les dispose en cercle, les numérote de 0 à N-1, et se met à en éliminer un sur K jusqu'à ce qu'il n'en reste qu'un... À quelle position doit se placer l'informaticienne de la famille pour être celle qui est choisie ?

Si le vieil homme a sept enfants et qu'il en élimine un sur trois, il compte 0, 1, élimine le 2, compte 3, 4, élimine le 5, compte 6, 0, élimine le 1, compte 3, 4, élimine le 6 (2 et 5 déjà éliminés), et ainsi de suite (il élimine 4 et 0). La fille chanceuse (ou informaticienne) se place donc en numéro 3.

De même, la fonction renvoie 0 pour N=1 (c'est le seul restant), 1 pour N=2 et K=3 (on compte 0, 1, 0, donc 0 éliminé), 2 pour N=5 et K=2, et 37 pour N=42 et K=7.

Contraintes

  • 0 < N
  • 0 < K

Entrée

La première ligne de l'entrée contient les deux entiers N et K.

Sortie

La sortie contient un entier : la position de l'héritière.

Runtime constraints

Maximum memory usage
500 kilobytes
Maximum execution time
1250 milliseconds

Input/output samples

Sample input
7 3
Sample output
3

Submit your solution

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