L'héritière informaticienne – Qualification 2007

É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.