ZOJ Problem Set - 3360
In the cc98 planet, people use a calendar which is similar to Gregorian calendar. Because the number of days in a year are not an integer, people have to make rules for leap year so that the average number of days in several years can be equal to the real value.
For instance, in the Earth, one year contains 365.2422 days accurately. So in Gregorian calendar, every 4 years, there will be an extra day in February, which is called leap year. But every 100 years, such as 1800 or 1900, the leap year doesn't appear. Furthermore, every 400 years, such as 1600 or 2000, the leap year appears again. So that the average number of days is 365.2425, which is nearly to the real value.
Now people in cc98 have calculated that decimal part of days number in a year. It can be describe as A/B. Now they need rules for the leap year. Please help them.
The calendar must satisfy following rules:
The following picture shows an example where N0=2, N1=3, N2=4:
Firstly, all even years are marked as "1st Leap", which are all leap years. Then blue lines indicate "2nd Leap" years. They are turned back to normal year. Finally, the red lines shows when "3rd Leap" years are. Some years (1st, 25th and 49th) which be turned back in last step become leap year again. Well, that is how rules work. So there are 9 extra days in 24 years. and 9/24 = 3/8 days are added to each year.
Now you're asked to tell people in cc98 how many Nis they need at least and what they are.
There are multiple test cases. The first line of input contains an integer T (T<= 500), indicating the number of test cases. Then T test cases follow. Every case has a single line which contains two integer A and B. (1 ≤ A < B < 10000)
A single line contains Nis, separated by a blank. If more than 5 Nis have to be used, output "Too complex". If there are different sets of Nis, anyone is OK.
4 97 400 303 400 3 8 9340 9511
4 25 4 4 25 4 2 4 Too complex
Case 1: 1st leap: 4 2nd leap: 4*25 3rd leap: 4*25*4 97/400=1/4-1/(4*25)+1/(4*25*4) Case 2: Same as case 1, but a negative leap year. 303/400=1-1/4+1/(4*25)-1/(4*25*4) Case 3: 1st leap: 2 2nd leap: 4 3/8=1/2-1/(2*4) It is a better solution than what shown in picture.
Author: HUANG, Minzhi
Source: ZOJ Monthly, July 2010