ZOJ Problem Set - 3873
a, b, c and d are all positive integers which satisfy bc - ad > 0. Your task is to minimize the following function of a positive integer n.
⌊x⌋, the floor function, means the largest integer not greater than x.
You need to find a positive integer n to minimize the above function. If there are multiple n's minimizing it, find the smallest one.
There are multiple test cases. The first line of input contains an integer T ≈ 100000 indicating the number of test cases. For each test case:
There are four positive integers: a, b, c and d. (1 <= a, b, c, d <= 1018)
For each case, print the smallest positive integer n which minimizes the function.
3 1 2 3 4 3 4 4 5 97 37 101 31
2 4 1
Author: ZHOU, Yuchen
Source: The 12th Zhejiang Provincial Collegiate Programming Contest