Assiettes revisité – Regional event 2008

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.