Jumping kangaroo P76214


Statement
 

pdf   zip

html

A kangaroo is in a certain position n ≥ 1, and he wants to reach the position 1. Spending x units of energy, the kangaroo can make a step to the position n − 1. If n is an even number, spending y units of energy, the kangaroo can jump to the position n/2.

Your task is to write a program that given the initial position n, the constant x and the constant y, prints the minimal cost of energy in order to the kangaroo goes from n to 1.

Input

The input is a sequence of at most 10000 lines, each one with n<108, x<105 and y<105 in this order, separated by spaces. All the numbers of the input are integers strictly positive. A special line with the zeros indicates the end of the input and must not be processed.

Output

For each line of the input, your program must print the minimal cost of going from n to 1 making steps of cost x and jumps of cost y. This number will always be less than 108.

Score

  • (30 points) Solving all the inputs of instance.
  • (70 points) Solving all the other inputs.
Public test cases

  • Input

    1 200 200
10 1 100
10 100 1
1024 1 1
1024 1 5
1234567 3 43
0 0 0

    Output

    0
9
103
10
42
766
    • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++