JDCC '16 Contest 1 P4 - Guess My Age

View as PDF

Submit solution

Points: 7
Time limit: 3.0s
Memory limit: 128M

Problem type

Mathemagical Lily, the greatest mathemagician of them all, has invented a new act. With a few yes or no questions, she is able to guess the age of any person!

However, she has noticed that some people are bothered when she guesses their age to be too high. Hence, using as few guesses as she can is not always the best option for her. Can you help her integrate this new discovery of people not enjoying being called old into her routine?

A volunteer for Lily's act has an age between 1 and N years old. Lily repeatedly asks questions of the form "Are you over X years old?" to help her determine the person's age. Once Lily is sure of the person's age, she proclaims "Your age is ____!", bewildering her volunteer.

However, her volunteers aren't always amazed. We can measure each volunteer's disillusion with a disillusion score. For every question Lily asks, the volunteer's score increases by 100. Additionally, every time Lily asks if the volunteer is older than he/she really is, the score increases by K.

Lily would like to minimize the disillusion that her volunteers experience. Can you help her figure out, in the worst case, how disillusioned a volunteer will be?


A test case contains two integers N (1 \le N \le 5 000) and K (0 \le K \le 5 000).


Output the minimum disillusion score that Lily can achieve in the worst case.

Sample Input

10 0

Sample Output


Sample Input

10 100

Sample Output


Sample Input

10 5000

Sample Output


Explanation of Sample Input/Output

In the first case, the volunteer does not care if Lily guesses too high, so Lily can guess however she wants. If the volunteer's age is 9, then she could ask the questions:

Are you over 5 years old? -> Yes
Are you over 7 years old? -> Yes
Are you over 8 years old? -> Yes
Are you over 9 years old? -> No

In fact, Lily only needs 4 questions in any case, so the volunteer will have a disillusion score of 400 at worst.

In the third case, the person really doesn't like being called old, so Lily needs to be careful. Her best strategy is to try every age in increasing order, asking:

Are you over 1 years old? -> Yes
Are you over 2 years old? -> Yes
Are you over 9 years old? -> No, how dare you?!?

In the worst case, Lily needs 9 questions and must guess too high at some point, so the worst case score is 5 900.


There are no comments at the moment.