【解題】Friday the Thirteenth

USACO Section 1.1 - Friday the Thirteenth


The Problem

Is Friday the 13th really an unusual event?

That is, does the 13th of the month land on a Friday less often than on any other day of the week? To answer this question, write a program that will compute the frequency that the 13th of each month lands on Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday over a given period of N years. The time period to test will be from January 1, 1900 to December 31, 1900+N-1 for a given number of years, N. N is non-negative and will not exceed 400.

There are few facts you need to know before you can solve this problem:

• January 1, 1900 was on a Monday.
• Thirty days has September, April, June, and November, all the rest have 31 except for February which has 28 except in leap years when it has 29.
• Every year evenly divisible by 4 is a leap year (1992 = 4*498 so 1992 will be a leap year, but the year 1990 is not a leap year)
• The rule above does not hold for century years. Century years divisible by 400 are leap years, all other are not. Thus, the century years 1700, 1800, 1900 and 2100 are not leap years, but 2000 is a leap year.

Do not use any built-in date functions in your computer language.

Don't just precompute the answers, either, please.


Program Name: friday


Input Format

One line with the integer N.


Output Format

Seven space separated integers on one line. These integers represent the number of times the 13th falls on Saturday, Sunday, Monday, Tuesday, ..., Friday.


Sample Input (file friday.in)

20


Sample Output (file friday.out)

36 33 34 33 35 35 34


解題思考

　　首先，既然我們已經知道，1900 年 1 月 1 日是星期一，那麼我們只需要求出：某日是從 1900 年 1 月 1 日開始的第幾天，將這個數字除以 7 所得到的餘數，就能夠知道那一天到底是星期幾(餘數 0 ~ 6 分別對應到星期天至星期一)。

　　所以，我利用迴圈，跑過從 1900 年到 1900 + n - 1 年中每一個月的 13 號(至於怎麼對應閏年，就照題目說的做吧)，分別利用上面的方式得出「這個 13 號」是星期幾，並紀錄下來。

　　最後，依照星期六、星期日、星期一、星期二、星期三、星期四、星期五的順序輸出紀錄的結果，就可以了。


參考解答(C++)

#include <fstream>

using namespace std;

inline bool isLeapYear(int year);

int main(void)
{
    ifstream in("friday.in", ios::in);
    ofstream out("friday.out", ios::out);

    int n;
    in >> n;
    in.close();

    int totalDay = 13, time[12];
    memset(time, 0, sizeof(time));
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j <= 12; j++)
        {
            time[totalDay % 7]++;

            // 計算從 1900 年 1 月 1 日到 (1900 + i) 年 j 月 13 日共有幾天
            int day;
            switch (j)
            {
                case 2:
                    day = (isLeapYear(1900 + i)) ? 29 : 28;
                    break;

                case 4:
                case 6:
                case 9:
                case 11:
                    day = 30;
                    break;

                default:
                    day = 31;
            }

            totalDay += day;
        }
    }

    out << time[6];
    for (int i = 0; i < 6; i++)
    {
        out << " " << time[i];
    }

    out << endl;
    out.close();

    return 0;
}

inline bool isLeapYear(int year)
{
    // 返回傳入的年份是否為閏年
    return (year % 100 != 0 && year % 4 == 0) || (year % 400 == 0);
}