1471 . Scientefic Experiment

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

John wants to be a scientist. A first step of becoming a scientist is to perform experiment. John has decided to experiment with eggs. He wants to compare the hardness of eggs from different species. He has decided to use a nearby large multi-storied building for this purpose. For each species he will try to find the highest floor from which he can drop the egg and it will not break. The building has (n+1) floors numbered from 0 to n. John has a book from which he knows that



  • If an egg is dropped from the topmost floor, it will surely break.

  • If an egg is dropped from floor 0, it will not break.

  • The eggs of same species are of same strength. That means if any egg breaks when dropped from the kth floor; all the eggs of that species will break if dropped from kth floor.

  • If an egg is unbroken after dropping it from any floor, it remains unharmed, that means the strength of the egg remains same.

  • To know the status of the dropped egg John has to go outside the building.

    • Unfortunately John has a few problems.



  • He can only carry one egg at a time.

  • He can buy eggs from a shop inside the building and an egg costs x cents.

  • To enter the building he has to pay y cents if he has no egg with him and z cents if he carries an egg with him.

  • He does not want to waste any egg so he will not leave any unbroken egg on the ground. But if an egg is broken, he leaves it there.

  • If he has an intact egg at the end, he can sell it for x/2 cents. He does not need to enter the building to sell the egg.

    • These problems are not going to tame John’s curious mind. So he has decided to use an optimal strategy and minimize his cost in the worst case. As John is not a programmer, he has asked for your help.

    Input Format

    Input starts with a positive integer T (T≤ 50) denoting the number of cases.


    Each case contains a line with 4 integer n x y z as described in the statement. You may assume that 1 < n ≤ 1000 and 1 ≤ x, y, z ≤ 105 and x is even.

    Output Format

    For each test case, print the case number and the minimized worst case cost.

    Sample Input 1

    7
4 2 998 1000
16 2 1000 1000
16 1000 1 1
4 1000 1 1
7 2 2 2
9 2 1 100
11 2 100 1

    Sample Output 1

    Case 1: 2000
Case 2: 4008
Case 3: 1015
Case 4: 1003
Case 5: 10
Case 6: 24
Case 7: 111

    Hints

    Problem Source

    Migrated from old NTUJ.

    Regional Kuala Lumpur 2010

    Subtasks

    No. Testdata Range Score

    Testdata and Limits

    No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
    0 1000 65536 200
    Submit
    Back to Top