L'Hôtel d'Hel-Baldr – Épreuve régionale 2024

Niveau 1 ⋅ Validation weight: 100%

Énoncé

Voulant prendre une pause de toutes ses aventures, Jøsëf Marchand espère se reposer une nuit à l'Hôtel d'Hel-Baldr, afin de reprendre des forces. Cependant, cet hôtel possède une politique assez particulière qui s'applique à l'arrivée de nouveaux visiteurs…

Jøsëf Marchand a réservé la chambre $N$, et commence à s'installer. Cependant, dès lors qu'une nouvelle personne réserve une chambre dans l'Hôtel, tous les clients doivent changer de chambre selon des règles précises :

  • Les clients qui étaient dans une chambre dont le numéro $i$ était un multiple de trois se déplacent dans la chambre $\frac i 3$,
  • Les clients qui étaient dans une chambre dont le numéro $i$ n'était pas un multiple de trois, mais un multiple de deux, se déplacent dans la chambre $\frac i 2$,
  • Les autres clients, qui étaient dans une chambre dont le numéro $i$ n'était ni un multiple de deux, ni un multiple de trois, doivent se déplacer dans la chambre $5 \times i + 1$.

Indiquez à Jøsëf Marchand le nombre de redirections dont il fera l'objet avant qu'il soit assigné pour la première fois à la chambre 1.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, l'étage initial de Jøsëf Marchand.

Sortie

Affichez, sur une ligne, le nombre de redirections que Jøsëf Marchand va subir avant d'atteindre la chambre 1.

Contraintes

  • $1 \le N \le 10\,000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
42
Exemple de sortie
7
Commentaire

Au départ, Jøsëf reçoit la chambre 42.

Lorsque le premier client entre, vu que 42 est un multiple de trois, Jøsëf doit se mouvoir dans la chambre $\frac {42} 3 = 14$.

Lors de l'entrée du second client, comme Jøsëf se situe dans la chambre 14, qui est un multiple de deux mais pas un multiple de trois, Jøsëf doit se diriger vers la chambre $\frac {14} 2 = 7$.

Lors de l'entrée du troisième client, comme Jøsëf se situe dans la chambre 7, qui n'est ni un multiple de deux ni un multiple de trois, Jøsëf se dirige vers la chambre $5 \times 7 + 1 = 36$.

Le quatrième client entre, 36 étant un multiple de trois, Jøsëf se déplace dans la chambre $\frac {36} 3 = 12$.

Le cinquième client entre, 12 étant toujours un multiple de trois, Jøsëf va dans la chambre $\frac {12} 3 = 4$.

Un sixième client réserve sa chambre, 4 étant un multiple de deux mais pas un multiple de trois, Jøsëf se dirige vers la chambre $\frac 4 2 = 2$.

Enfin, un septième et dernier client rentre dans l'hôtel. Jøsëf se situant dans la chambre 2, qui est un multiple de deux mais pas un multiple de trois, il se positionne finalement dans la chambre $\frac 2 2 = 1$.

Il aura fallu 7 redirections au total avant que Jøsëf Marchand ne se retrouve pour la première fois dans la chambre 1.

Exemple d'entrée
1
Exemple de sortie
0
Commentaire

Comme Jøsëf se situe d'ores et déjà dans la chambre 1, il n'a pas besoin de se faire rediriger avant de se retrouver pour la première fois dans la chambre 1.

La réponse est donc 0.