加载中...

POJ 3393 - Lucky and Good Months by Gregorian Calendar


0x00 POJ 原题

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:

Y_(s) M_(s) Y_(e) M_(e)

where two numbers are separated by a single blank, Y_(s) is an integer, 0 < Y_(s) < 10000, denoting the starting year in western style, M_(s) is an integer, 1 ≤ M_(s) ≤ 12, denoting the starting month, Y_(e) is an integer, 0 < Y_(e) < 10000, denoting the ending year in western style, M_(e) is an integer, 1 ≤ M_(e) ≤ 12, denoting the ending month.

Note that you can be sure the month indicated by M_(s), Y_(s) is never after the month indicated by M_(e), Y_(e).

Output

For each test case, output the number of lucky months and the number of good month in between the month M_(s) of the year Y_(s) (including this month) and the month M_(e) of the year Y_(e) (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

Source

Kaohsiung 2006

0x10 题目概述

科普文一篇,文章 80%都是无用信息,因为都是常识,但是又不得不看,因为有 20%是常人不知道的历史常识。

定义:

  • Goog month: 该月第一个工作日为星期一的月份
  • Luckly month: 该月最后一个工作日为星期五的月份

问: 给定一个 Gregorian Calendar 格里高公历的 时间闭区间(就是包括端点的年月了)

【开始年、月】 ~ 【结束年、月】

在这个时间区间内,有多少个 Goog month,有多少个 Luckly month

文章要点:

  • Gregorian Calendar 格里高公历 就是现在广泛使用公历(西历),下面简称 GC

  • GC 的起始日期为 1 年 1 月 1 号,该日为星期六

  • GC 平年有 365 天,闰年 366 天(2 月多 1 天)

  • GC 有 12 个月,各月的天数和现在的使用的西历一致

  • GC 在 1582 年之前(不包括 1582),若该年份能被 4 整除,则为闰年

  • GC 在 1582 年之后(包括 1582),判断闰年的标准(满足下面随便一个):

    (1)能被 4 整除,但不能被 100 整除;

    (2)能被 400 整除。

  • 由于历史原因,GC 规定 1700 年无条件为闰年

  • 由于历史原因,GC 规定 1752 年 9 月 3 日 ~ 13 日共 11 天不存在,即 1752 年 9 月只有 19 天

  • GC 一星期有 7 天,排序为 Sun,Mon,Tue,Wed,Thu,Fri,Sat,和现在的星期一致,其中 Mon 到 Fri 为工作日,Sun 和 Sat 为休息日

0x20 解题思路

直接模拟就 OK 了,水题。

0x21 判断闰年

输入时间区间的 起始年 sy 月 sm 和 终止年 ey 月 em 后,

先计算 1 年 1 月到 sy 年 sm-1 月(若 sm=1,则计算到 sy-1 年 12 月)的天数 day

注意此时 day 的天数刚好计算到 sm-1 月的最后一天

若 day+1,则恰好进入所输入的时间区间 【开始年、月】 ~ 【结束年、月】 的第一天

0x22 计算日期对应的天数

  • (1)1582 年前后闰年判断标准改变了
  • (2)1700 无条件闰年
  • (3)1752 年 9 月少了 11 天

0x23 判断星期

由于 1 年 1 月 1 号为星期六,一星期有 7 天,

因此 (day+5)%7 就能计算第 day 天是星期几。

不能直接 day%7,day% 就是默认 1 年 1 月 1 号为星期日,至于为什么要先+5,这个不难推导,读者自己想想就明白了

0x24 判断 Good month 和 Lucky month

计算天数 day 后,令 day++,进入 sm 的 1 号

此时判断 sm 的 1 号是不是为 Good month,使用上面给出计算第 day 天是星期几的方法,若

1 号为星期日(0)、星期六(6)或星期一(1),则该月为 Good month

从 sm 月开始,把天数 day 逐月递增,逐月判断该月是否为 Good month,判断方法都是一样的。

不难发现,若第 k 月为 Good month,则第 k-1 月必定为 Luckly month,因此两个计数器同时增加即可。

注意 3 点:

  • (1)边界:若 sm 为 Good month,计数器 good++,但计数器 luck 不变,因为 sm-1 月不在时间区间内。 若计算到 em 为 Good month,则计数器 luck++,good 不变,因为 day 一开始就+1 了,当 day 逐月递增到 em 时,实则 day 此时为第 em+1 月的 1 号,此时判断的是 em+1 月是否为 Good month,若是,则第 em 月为 Luckly month,但 em+1 月在时间区间内,不计入计数器
  • (2)逐月递增时,若到达 1752 年 9 月,要 减 11 天
  • (3)闰年平年的月份天数不同

0x30 AC 源码

//Memory Time 
//216K   0MS 

#include<iostream>
using namespace std;

int Month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};   //平年月
int Lmonth[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};  //闰年月
enum week{Sun,Mon,Tue,Wed,Thu,Fri,Sat};  //星期

bool leap(int year);  //判断year是否为闰年
int ComputeDay(int y,int m);  //计算从第1年1月1日到第y年m-1月的总天数+1 (即只包括第m个月的第一天)

int main(int i,int j,int* pm)
{
    int test;
    cin>>test;
    for(int t=0;t<test;t++)
    {
        int ys,ms,ye,me;
        cin>>ys>>ms>>ye>>me;

        int luck=0,good=0;
        int day=ComputeDay(ys,ms);

        if(((day+5)%7<=Mon) || ((day+5)%7==Sat))  //计算起始ys年ms月1号为星期几,判断是否为good month
            good++;                               //1年1月1号是星期六,而原本默认是星期日,因此+5调整

        /*计算从ys年ms+1开始 到ye-1年的月份是否为good month*/

        for(i=ys;i<ye;i++)
        {
            if(leap(i))
                pm=Lmonth;
            else
                pm=Month;

            if(i==ys)
                j=ms;
            else
                j=1;
            for(;j<=12;j++)
            {
                day+=*(pm+j);
                if(i==1752 && j==9)
                    day-=11;
                                                          //由于day开始时+1缘故,当j时,计算的是第j+1月是否为good month
                if(((day+5)%7<=Mon) || ((day+5)%7==Sat))  //计算j+1月1号为星期几,判断是否为good month
                {
                    good++;
                    luck++;  //当j+1月为good month,j月必为luck month
                }
            }
        }

        /*计算第ye年的good month*/

        if(leap(i))
            pm=Lmonth;
        else
            pm=Month;

        if(i==ys)   //若ye==ys
            j=ms;
        else
            j=1;

        for(;j<=me;j++)
        {
            day+=*(pm+j);
            if(i==1752 && j==9)
                day-=11;
                                                      //由于day开始时+1缘故,当j时,计算的是第j+1月是否为good month
            if(((day+5)%7<=Mon) || ((day+5)%7==Sat))  //计算j+1月1号为星期几,判断是否为good month
            {
                if(j!=me)
                    good++;

                luck++;  //当j+1月为good month,j月必为luck month
            }
        }

        cout<<luck<<' '<<good<<endl;
    }
    return 0;
}

bool leap(int year)  //判断year是否为闰年
{
    if(year<1582)
        return !(year%4);   //当year<1582时,只要能被4整除就是闰年
    else
    {
        if(year==1700) //当year=1700时,历史原因,无条件为闰年
            return true;

        if((!(year%4)&&(year%100)) || !(year%400))   //当year>=1582时,能被4整除且不被100整除为闰年
            return true;                             //或能被400整除时为闰年
    }
    return false;
}

int ComputeDay(int y,int m)  //计算从第1年1月1日到第y年m-1月的总天数+1 (即只包括第m个月的第一天)
{                            //"+1"是为了使从当月末变为下月初
    int i,j,day=1;
    for(i=1;i<y;i++)
        if(leap(i))
            day+=366;
        else
            day+=365;

    for(j=1;j<m;j++)
        if(leap(i))
            day+=Lmonth[j];
        else
            day+=Month[j];

    if(y>1752)
        day-=11;
    else if(y==1752 && m>9)
        day-=11;

    return day;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
赏
  目录