Prologin
2025
Énoncé¶
Avant l'épreuve écrite, par souci d'équité, nous veillons à ce que chaque candidat ingurgite la même quantité de nourriture. Par conséquent, tous nos pains au chocolat font exactement le même poids. Cependant, cette fois-ci, l'un des N pains au chocolat dont nous disposons est plus lourd que les autres. À l'aide d'une balance à deux plateaux, vous devez le dépister, en manipulant le moins de pains au chocolat possible à chaque pesée.
Lors d'une pesée, vous manipulez trois tas de pains au chocolat : un tas sur le plateau gauche de la balance, un tas sur le plateau droit, ainsi que le tas restant, à l'extérieur de la balance. On vous demande de décrire le pire cas : celui où le pain au chocolat le plus lourd se trouve toujours dans un des plus gros tas, en indiquant à chaque pesée le nombre d'éléments qu'il vous reste à analyser.
Contraintes¶
- 2 <= N <= 999 999 999 est le nombre de pains au chocolat.
Entrée¶
L'entrée standard contient un entier N représentant le nombre de pains au chocolat dont nous disposons.
Sortie¶
Vous devez écrire P lignes sur la sortie standard, où P est le nombre de pesées à effectuer au minimum dans le pire cas. La k-ième ligne contiendra un entier représentant le nombre de pains au chocolat restant à analyser pour la pesée no k.
