Devinette – Regional event 2013

Énoncé¶

Vous jouez à une devinette avec Joseph Marchand : il pense à un nombre entre 1 et N que vous devez trouver. Pour chaque nombre que vous suggérez, Joseph vous dit si c'est plus haut ou plus bas. Mais vous ne devez pas trouver ce nombre en le moins de coups possibles, non : chaque coup vous coûte la valeur que vous suggérez.

Ainsi, si pour trouver un nombre entre 1 et 5 :

• 3 ?
• Plus.
• 4 ?
• Plus.
• C'est 5 ! Mon coût est de 3 + 4 = 7.

Partir de 2 aurait été plus judicieux :

• 2 ?
• Plus.
• 4 ?
• Moins.
• C'est 3 ! Mon coût est de 2 + 4 = 6.

Quel est le coût minimal au pire pour deviner le nombre auquel pense Joseph Marchand ?

Entrée¶

• Sur la première ligne, le nombre N.

Sortie¶

Un nombre : le coût minimal pour deviner le nombre de Joseph.

Contraintes¶

• 1 <= N <= 200