Ormie and the cookie
All submissions for this problem are available.
Ormie the little pig and his love for cookies is well known . This time he could not resist and ate all the cookies that he was supposed to share with his girl . So he deicded to fetch some more cookies for her just to make sure he is not tortured later . But there is a problem , the nearest location from where he can get cookies is located on a hill which is very slippery and difficult to climb . He takes help from his friends to fetch the cookies . Each friend can climb Ui distance upwards but slips and falls by Di distance downwards . Each friend takes unit time to climb a unit distance . Help Ormie in finding the minimum time taken to reach the top . He promises to share one cookie with you also .
Note : Once the top is reached there is no falling back.
- The first line contains T , the number of test cases.
- The first line of each test case contains two space separated integers N (the number of friends) and H (Height of the hill).
- Now N line follows which contains two space separated integers Ui (the number of unit distance climbed upwards) and Di (the number of unit distance a friend falls by) .
- For each test case output minimum time taken to climb the hill .
Constraints and Subtasks:
Subtask 1: 40 points
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100
- 0 < D < U ≤ 105
- 1 ≤ H ≤ 105
Subtask 2: 60 points
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 10 5
- 0 < D < U ≤ 109
- 1 ≤ H ≤ 109
Input: 2 5 10 1 0 2 1 3 2 4 3 5 4 4 20 5 4 7 3 9 2 11 3 Output: 10 28
In the first case,
Friend1 will go 1 step upward and 0 downward.So, he will reach in 10 steps.
Friend2 will go 2 steps upward and 1 downward. So, in 3 steps he moves a distance of 1, thereby reaching destination in 26 steps.
Friend3 will go 3 steps upward and 2 downward. So, in 5 steps he moves a distance of 1, thereby reaching destination in 38 steps.
Friend4 will go 4 steps upward and 3 downward. So, in 7 steps he moves a distance of 1, thereby reaching destination in 46 steps.
Friend5 will go 5 steps upward and 4 downward. So, in 9 steps he moves a distance of 1, thereby reaching destination in 50 steps.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.