Équilibre – Qualification 2012

Niveau 2

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

Contraintes d'exécution

Utilisation mémoire maximum
2000 kilo-octets
Temps d'exécution maximum
300 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
9
Exemple de sortie
9
3
Commentaire

Exemple avec 9 pains au chocolat

Après une première pesée de 9 pains, nous savons que le pain au chocolat le plus lourd se trouve au pire dans un tas de 3 pains. Une deuxième pesée de 3 pains permet de déterminer le pain au chocolat le plus lourd.

Exemple d'entrée
6
Exemple de sortie
6
2
Commentaire

Pour la première pesée de 6 pains, il est certes possible de mettre 3 pains sur chacun des plateaux, mais on se retrouvera avec 3 pains à analyser pour la pesée suivante ; tandis que si on en met 2 sur chacun des plateaux et qu'on en laisse 2 à l'extérieur, il ne restera plus que 2 pains à analyser pour la deuxième pesée.

Exemple d'entrée
42
Exemple de sortie
42
14
5
2