POJ 3393

Lucky and Good Months by Gregorian Calendar

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 1159 Accepted: 354

Description

Have you ever wondered why normally an year has 365 days, not 400 days? Why August have 31 days, but February have only 28 days? Why there are 7 days, not 6 days, in a week? Do people in ancient time use the same calendar as we do? There are many interesting conjectures and theories about those problems. Now we will tell you one story that may help explaining plausible answers to these questions. Using information in the story, you are then ask to solve an interesting problem using computer. Note that there are many theories about the calendar system discussed. This problem set will tell only one of them in a simplified way.

Throughout history, people keep track of time by observing the relative positions of the earth, the moon and the sun. A day is the amount of time the earth completes a self rotation. An year is defined to be the amount of time the earth orbits the sun. The earth takes roughly 365.242190 days to orbit the sun with some small variations. For practical purpose, a calendar year needs to have an integral number of days. Hence people need to add leap days to keep the calendar synchronized with the sun. If you keep a calendar year to have 365 years, you need to add one more day in a leap year roughly about every 4 years. However, this kind of calendar will not be in perfect synchronization with the earth’s position orbiting the sun because it advanced 365.25 days in average, which is slightly more than the actual period.

Depending on how accurate you can measure the period of the earth orbiting the sun, you need to invent different formulas for leap years. Several famous Western calendar systems have been invented, not to mention the more complex Oriental systems. In order to save programmers’ efforts, we will not discuss the Oriental, such as Chinese, calendar systems. We will focus on major Western calendar systems. The earliest one may be the Julian calendar created by Julius Caesar in 46 BC. It is not accurate enough and will have one day off every 128 years. The next one is the Astronomical Julian calendar invented by Joseph Justus Scaliger around the 16th century. Both have simple formulas to determine which year is a leap year.

The next major one is called Gregorian calendar that was invented at the year 1582 because the synchronization of the earth’s orbiting and the calendar is finally noticed by people. In this system, a leap year is dropped every 100 years unless it is every 400 years. By doing this modification, the average number of days in a calendar year is 365.2425. Note that this system is also not perfect. It adds one more day every 3289 years. There are other more modifications suggested, such as the one by Astronomer John Herschel, the Greek Orthodox, and the SPAWAR group in the US Navy. For simplicity, people use Gregorian calendar system though it may not be perfect.

The following is the formula for the Gregorian calendar to determine whether an year is a leap year or not. An year y, y > 1582 and y ≠ 1700, is a leap year if and only if

y is divisible by 4, and

y is not divisible by 100 unless it is divisible by 400.

An year y, 0 < y < 1582 is a leap year if and only if

y is divisible by 4.

Hence year 4 is a leap year, year 100 is a leap year, year 1900 is not a leap year, but year 2000 is a leap year. A leap year has 366 days with the extra day February 29. A non-leap year has 365 days.

During your computation, you may also want to observe the following facts about Gregorian calendar. Many calendar systems were used by people in different areas in the Western world at the same time. The current Western calendar system, primarily follows Gregorian calendar, and is so called the Gregorian Reformation, was adopted by Britain and the possessions on September 3, 1752. For lots of reasons that we are sure you do not want to read in this problem description, 11 days are eliminated starting September 3, 1752 in order for people not to rewrite history. That is, in the Gregorian calendar, there is no days in between September 3, 1752 and September 13, 1752. Note that Rome adopted the Gregorian calendar at the year 1582, when it was invented. Also for historical reasons, the year 1700 is declared a leap year in the Gregorian calendar. There are other variations about the Gregorian calendar system, however, we will use the one that is defined above.

A lunar month is defined to be the average time between successive new or full moons which is 29.531 days. People observe in average 12.368 full moons in an year. Unfortunately, this is also not an integral number in terms of days. Hence if we set an year to have 12 months with each month having 30 days, we need to add several days each year. To save the trouble, an alternative way is to have the number of days in a month to alternative between 30 and 31. However, this introduces one extra day. After lots of struggle, the Gregorian calendar defined the numbers of days in each month during a non-leap year to be 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, respectively from the first month to the 12th month. One more day is added on February in the leap year. The names for the months in sequence from the first month — January, February, March, April, May, June, July, August, September, October, November, and December, are also very interesting and have lots of stories associated with them. For example, the Roman Senate named the month of July after Julius Caesar to honor him for reforming their calendar. However, we do not have time to cover them here.

In ancient time, a week may have different number of days, say from 4 to 10 days. In the Gregorian calendar system, a week corresponds roughly to the moon’s quarter phase whose position can be clearly observed by people. Hence people can easily measure a week. Also for some other reasons, such as religion, it is defined as 7 days. The names of the 7 days in sequence — Sunday, Monday, Tuesday, Wednesday, Thursday, Friday and Saturday, all have interesting stories. However, we also do not have time to cover them here.

Throughout history, people believe the relative positions of the stars can decide their fate. This is also true for people living in an island T. In island T, people are working from Monday through Friday every week and enjoy holidays on every Saturday and Sunday without exceptions. There is no other holidays. From ancient tales, a month is called lucky if the last working day in this month is Friday. For examples, the last working day of September, 2006 is September 29, 2006 — which is Friday. Hence it is lucky. The last working day of July, 2006 is July 31, 2006 — which is Monday. Hence it is not lucky. The last working day of August, 2006 is August 31, 2006 — which is Thursday. Hence it is also not lucky. It is believed that if one eats only vegetable everyday during a lucky month, he/she will have a good fortune in getting rich.

Also from ancient tales, a month is called good if the first working day in this month is Monday. For examples, the first working day of July, 2006 is July 3, 2006 — which is Monday. Hence it is good. The first working day of October, 2006 is October 2, 2006 — which is Monday. Hence it is also good. The first working day of August, 2006 is August 1, 2006 — which is Tuesday. Hence it is not good. The first working day of September, 2006 is September 1, 2006 — which is Friday. Hence it is also not good. It is believed that if one goes to bed before 10 PM every day during a good month, he/she will be very healthy. A month can be both good and lucky at the same time.

Given a period of time, your task is to report the number of lucky months and the number good months during this period of time using the described Gregorian calendar system.

Input

The first line contains the number of test cases w, 1 ≤ w ≤ 10. Then the w test cases are listed one by one. Each test case consists of 1 line with four numbers:

Ys Ms Ye Me

where two numbers are separated by a single blank, Ys is an integer, 0 < Ys < 10000, denoting the starting year in western style, Ms is an integer, 1 ≤ Ms ≤ 12, denoting the starting month, Ye is an integer, 0 < Ye < 10000, denoting the ending year in western style, Me is an integer, 1 ≤ Me ≤ 12, denoting the ending month.

Note that you can be sure the month indicated by Ms, Ys is never after the month indicated by Me, Ye.

Output

For each test case, output the number of lucky months and the number of good month in between the month Ms of the year Ys (including this month) and the month Me of the year Ye (including this month) in one line. The two numbers are separated by a single blank.

Sample Input

2
2006 9 2006 9
2006 7 2006 9

Sample Output

1 0
1 1

题目大意是分别计算所给起始年月份至终止年月份之间每月第一个工作日为周一和最后一个工作日为周五，这两种情况各自的数量

这题最关键的是使用蔡勒公式（维基百科），计算所给年月日是星期几,但是维基百科中是从1582年10月4日开始分为两个部分，而题目是从1752年9月2日开始分为两个部分，需要做调整，但不明白的是虽然这两种方式中去掉的天数不一致（1582年10月4日之后是15日，少了10天，而1752年9月2日之后是14日，少了11天），但只要调整年份，而公式不变就可得到正确结果，不明白为什么

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int mday[13]={0,31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int lmday[13]={0,31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int isleap(int y)
{
    int flag=0;
    if(y>1582 && y!=1700)
    {
        if(y % 400 ==0 || (y%4==0 && y%100!=0))
            flag=1;
    }
    else if(y<1582)
    {
        if(y%4==0) flag=1;
    }
    return flag;
}
int getday(int year,int month,int day)
{
    int w=0;
    if(month==1 || month ==2)
    {
        year--;
        month+=12;
    }
    int c=year/100;
    if(year<1752 || (year==1752 && (month<9 || (month==9&&day<=2))))
       {
           year%=100;
            w=(year+year/4-c+(26*(month+1))/10+day+4);
            w=(w%7+7)%7; 
       }
       else
       {
           year%=100;
           w=(year+year/4+c/4-2*c+(26*(month+1))/10+day-1);
           w=(w%7+7)%7;
       }
       //cout<<year<<" "<<month<<" "<<day<<": "<<w<<endl;
       return w;
}
int main()
{
    int t;
    int luck,good;
    int ys,ms,ye,me;
    cin>>t;
    while(t--)
    {
        cin>>ys>>ms>>ye>>me;
        luck=0;good=0;
        if(ys==ye)
        {
            for(int j=ms;j<=me;j++)
            {
                int tmp=0;
                tmp=getday(ys,j,1);
                if(tmp==1 || tmp==0 || tmp==6) good++;

                if(isleap(ys) && j==2)
                {
                    tmp=getday(ys,j,29);
                }
                else tmp=getday(ys,j,mday[j]);
                if(tmp==5 || tmp==6 || tmp==0) luck++;
            }
            cout<<luck<<" "<<good<<endl;
            continue;
        }
        for(int j=ms;j<=12;j++)
        {
            int tmp=0;
            tmp=getday(ys,j,1);
            if(tmp==1 || tmp==0 || tmp==6) good++; 
            if(isleap(ys) && j==2)
            {
                tmp=getday(ys,j,29);
            }
            else tmp=getday(ys,j,mday[j]);
            if(tmp==5 || tmp==6 || tmp==0) luck++;
        }
        for(int i=ys+1;i<ye;i++)
        {
            for(int j=1;j<=12;j++)
            {
                int tmp=0;
                tmp=getday(i,j,1);
                if(tmp==1 || tmp==0 || tmp==6) good++; 
                if(isleap(i) && j==2)
                {
                    tmp=getday(i,j,29);
                }
                else tmp=getday(i,j,mday[j]);
                if(tmp==5 || tmp==6 || tmp==0) luck++;
            }
        }
        for(int j=1;j<=me;j++)
        {
            int tmp=0;
            tmp=getday(ye,j,1);
            if(tmp==1 || tmp==0 || tmp==6) good++;

            if(isleap(ye) && j==2)
            {
                tmp=getday(ye,j,29);
            }
            else tmp=getday(ye,j,mday[j]);
            if(tmp==5 || tmp==6 || tmp==0) luck++;
        }
    cout<<luck<<" "<<good<<endl;
    }
}