Devinette – Regional event 2013

Level 6

É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

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
8000 milliseconds

Input/output samples

Sample input
5
Sample output
6
Sample input
42
Sample output
129

Submit your solution

You have to register or log in to be able to submit your solution.