Assiettes revisité – Regional event 2008

Level 6

ENONCE

Cimone est confrontée à un problème totalement imaginaire : elle dispose d'une pile d'assiettes, qui ont toutes la même dureté. Cimone habite dans une tour de N étages (numérotés de 1 à N), et la dureté d'une assiette est définie comme le premier étage à partir duquel celle-ci se casse une fois lancée par la fenêtre. La dureté d'une assiette vaut 1 au minimum et N au maximum. Si une assiette ne se casse pas en arrivant en bas, Cimone peut aller la rechercher.

Cimone dispose d'une pile énorme d'assiettes, et veut déterminer leur dureté. Pour cela, elle s'autorise à en casser quelques unes (disons, K). Pour chaque stratégie permettant de déterminer la dureté des assiettes, il y a un nombre maximal d'assiettes à lancer, qui permet de déterminer avec certitude la dureté des assiettes. Ecrivez une fonction qui détermine ce nombre pour la stratégie optimale (c'est-à-dire celle pour laquelle ce nombre est minimal), étant donné N et K.

Voici un exemple de stratégie (non optimale !), pour N=100, et K=2. Cimone décide de lancer la première assiette à l'étage 40. Si celle-ci se casse, cela signifie que la dureté des assiettes vaut au plus 40. Cimone lance donc une assiette à chaque étage 1, 2, 3, 4, ... Dès qu'une assiette se casse, elle aura trouvé la dureté des assiettes. En revanche, si la première assiette lancée à l'étage 40 ne s'est pas cassée, Cimone décide de lancer une assiette à chaque étage 41, 42, 43, 44, 45..., pour déterminer la dureté des assiettes. Ainsi, au pire, Cimone fera 1+Max(39, 59) = 60 lancés. La solution du problème pour N=100 et K=2 vaudra donc au plus 60.

ENTREE

Les deux nombres N (1\<=N\<=500) et K (1\<=K\<=10), sur la même ligne et séparés d'un espace

SORTIE

Un entier, le nombre maximal de lancés de la stratégie optimale de Cimone.

Runtime constraints

Maximum memory usage
16000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
6 2
Sample output
3
Sample input
100 2
Sample output
14

Submit your solution

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