Problem: ChefWM CodeChef Solution
Chef recently created a new Tiling Window Manager called ChefWM. He wants to find out the maximum number of columns of windows he can fit on the screen and he needs your help.
Consider the screen to be an axis-aligned rectangle in the xyxy-plane, with its bottom-left corner at (0,0)(0,0) and top-right corner at (N,M)(N,M) (that is, the screen has width NN units and height MM units). ChefWM works as follows:
- First, the screen is divided into one or more columns of equal integer width.
- Then, each column is divided into two or more windows of equal integer height. Note that all windows within a column must have the same height, but windows in different columns may have different heights.
- Finally, Chef would like the following condition to hold:
- No two windows from different columns can have their horizontal boundary share the same yy-coordinate (apart from y=0y=0 and y=My=M). See the figures below for more details.
It is not allowed to leave any empty space on the screen, i.e, the division performed in the first two steps above must cover the entire screen.
Here is an example of a tiling that satisfies all the conditions, for N=8N=8 and M=6M=6.
Below are two tilings that satisfy all conditions except the last. The one on the left has a horizontal edge at y=2y=2 in both columns, while the one on the right has a horizontal edge at y=2y=2 in column 11 and column 33.
What is the maximum number of columns that ChefWM can fit on the screen while following the above conditions? Note that you do not need to maximize the number of windows, you only need to maximize the number of columns.
It may be possible that no columns can be created under these conditions, in that case, print 00.
- The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
- Each test case consists of a single line of input, containing two space-separated integers N,MN,M — the coordinates of the top-right corner of the screen.
For each test case, output a single line containing one integer — the maximum number of columns ChefWM can create for the screen.
Sample Input 1
5 8 210 1 100 100 5 10 1 9 2310
Sample Output 1
4 1 1 0 3
Test Case 1: It is possible to make 44 columns as follows:
- The first column has 77 windows of height 3030 each
- The second column has 22 windows of height 105105 each
- The third column has 55 windows of height 4242 each
- The last column has 33 windows of height 7070 each
It can be seen in the diagram below that the edges from any two windows from different columns do not have the same yy-coordinate except for y=0y=0 and y=my=m.
Test Case 2: There can only be one column no matter how many windows you keep (as long as there are at least 22 windows).
Test Case 3: You can have a single column with 55 windows. It can be shown that this is the maximum number of columns that can possibly satisfy the given restrictions.
The Melancholy of Problem Setter CodeChef Solution