题目描述

$\text{Microzot}$ 公司推出了名为 $\text{Doors MKB}$ 的革命性操作系统，同时引入了一套全新的日历系统。新历法将一年分为两个时期（$\text{Gill}$ 和 $\text{Bates}$），每个时期包含五个月份（$\text{Sun}$、$\text{Water}$、$\text{Forest}$、$\text{Mountains}$、$\text{Money}$），每月有 $36$ 天，由 $6$ 周（$\text{First}$ 至 $\text{Sixth}$）组成，每周 $6$ 天。此外，每年末尾还有 $5$ 天（平年）或 $6$ 天（闰年）的“庆典日”（$\text{Feast}$ $1$ 至 $\text{Feast}$ $5/6$），不属于任何时期、月份或星期。新历的第一天对应公历 $1998$ 年 $6$ 月 $25$ 日（即 $\text{Doors MKB}$ 发布日）。闰年规则与格里高利历相同。$1998$ 年 $6$ 月 $25$ 日之前的日期在新历中需附加 bd（意为“$\text{before Doors}$”）后缀。

本题要求编写一个转换器，将输入的日期（可能是旧历或新历）进行转换。若输入为旧历格式（YYYY-MM-DD），则输出对应的新历日期；若输入为新历格式（如 Gill-Sun-First-1-1），则输出 Enter date in old format。输入以单独一行 END 结束。

输入格式

多行输入，每行一个日期字符串。日期可能是旧历格式（YYYY-MM-DD，年范围为 $1600$ 到 $5000$）或新历格式（由 Gill、Bates、Feast 等关键词组成）。输入以行 END 结束。

输出格式

对于每个旧历日期，输出对应的新历日期字符串，格式为：

<Period>-<Month>-<Week>-<Day>-<Year>

或（若为 $\text{Feast}$ 日）：

Feast <N>-<Year>

若日期在 $1998$ 年 $6$ 月 $25$ 日之前，则在年份后附加 bd。对于每个新历日期，输出一行：

Enter date in old format

样例

输入

1998-06-25
Feast 2-12
1998-06-24
3476-06-21
2000-06-29
END

输出

Gill-Sun-First-1-1
Enter date in old format
Feast 5-1bd
Feast 3-1478
Gill-Sun-First-6-3

题目分析

本题的核心是日历系统之间的转换。两种日历都基于格里高利历的闰年规则，但新历将一年重新划分为固定长度的周期（$180$ 天 + $180$ 天 + $5/6$ 天），且以 $1998$ 年 $6$ 月 $25$ 日为纪元起点。

转换的关键步骤：

1. 将旧历日期转换为从公元 $1$ 年 $1$ 月 $1$ 日起的绝对天数（可用格里高利历的累积天数公式）。
2. 计算该日期与 $1998$ 年 $6$ 月 $25$ 日之间的天数差。
3. 根据差值在新历中定位：先确定年份（每 $365$ 或 $366$ 天递增一年），再确定该年中的第几天（从 $1$ 开始计数），然后根据第几天落入哪个区间确定时期、月份、周和日，或判断是否为 $\text{Feast}$ 日。
4. 若原日期早于 $1998$ 年 $6$ 月 $25$ 日，则在新历日期后附加 bd。

新历日期识别：若输入字符串包含 "Bates"、"Gill" 或 "Feast"，则认为属于新历格式，直接输出提示信息。

解题思路

绝对天数计算（toDays）

采用格里高利历的累积天数公式，将年份分解为 $400$ 年周期、$100$ 年周期、$4$ 年周期和余下平年，加上月、日偏移。该函数返回从公元 $1$ 年 $1$ 月 $1$ 日到给定日期的总天数（包含起始日期）。

新历日期生成（toDate）

输入两个绝对天数：基准点 dayOfStart（$1998$ 年 $6$ 月 $25$ 日）和待转换日期 dayOfCurrent。

1. 计算差值 dayDiff = abs(dayOfCurrent - dayOfStart)。
2. 若 dayOfCurrent >= dayOfStart，则从基准年开始向后推算年份和年内偏移；否则向前推算，且最终输出需加 bd 后缀。
3. 确定年份后，计算该日期在当年是第几天（从 $1$ 开始）。
4. 根据年内第几天判断：
   • 若 $>359$（即第 $360$ 天及以后），则为 $\text{Feast}$ 日，输出 Feast N，其中 $N$ 为天数减去 $359$（平年 $\text{Feast}$ $5$ 天，闰年 $\text{Feast}$ $6$ 天）。
   • 否则，前 $180$ 天属于 $\text{Gill}$ 时期，后 $180$ 天属于 $\text{Bates}$ 时期。每个时期内，按 $36$ 天为一个月份，$6$ 天为一周，分别计算出月份名、周名和日数。

输入处理

逐行读取，若行内容为 END 则终止。若行中包含 "Bates"、"Gill" 或 "Feast"，则视为新历格式，输出提示。否则按旧历格式解析年、月、日，调用 toDays 和 toDate 输出。

复杂度分析

• toDays 函数执行常数次算术运算，时间复杂度 $O(1)$。
• toDate 函数通过循环逐年减去天数，最多循环年份差值（约 $5000$ 年），但实际每次查询最多约 $5000$ 次迭代，可接受。可优化为周期跳跃，但本题数据量小，无需优化。
• 整体时间复杂度 $O(Y)$，其中 $Y$ 为日期所在年份与基准年份的差，常数级。
• 空间复杂度 $O(1)$。

代码实现

// Microzoft Calendar
// UVa ID: 631
// Verdict: Accepted
// Submission Date: 2017-06-03
// UVa Run Time: 0.000s
//
// 版权所有（C）2017，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

const int daysOfYear = 365;
const int daysOf4Years = daysOfYear * 4 + 1;
const int daysOf100Years = daysOf4Years * 25 - 1;
const int daysOf400Years = daysOf4Years * 100 - 3;
const int daysBeforeMonth[2][13] = {
    {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365},
    {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366}
};

bool isLeapYear(int yyyy) {
    return ((yyyy % 4 == 0 && yyyy % 100 != 0) || yyyy % 400 == 0);
}

// 以公元元年1月1日为基准日期，将公元元年以后的日期转换为天数。
int toDays(int yyyy, int mm, int dd) {
    int days = 0, year = yyyy - 1;
    days += (year / 400) * daysOf400Years, year %= 400;
    days += (year / 100) * daysOf100Years, year %= 100;
    days += (year / 4) * daysOf4Years, year %= 4;
    days += year * daysOfYear;
    days += daysBeforeMonth[isLeapYear(yyyy)][mm - 1] + dd;
    return days;
};

// 将天数转换为日期。
void toDate(int dayOfStart, int dayOfCurrent) {
    int yyyy = 1, dayDiff = abs(dayOfCurrent - dayOfStart);
    if (dayOfCurrent >= dayOfStart) dayDiff += 1;
    while (true) {
        int dayOfYear = isLeapYear(yyyy) ? 366 : 365;
        if (dayDiff > dayOfYear) {
            yyyy += 1;
            dayDiff -= dayOfYear;
        } else break;
    }
    if (dayOfCurrent >= dayOfStart) dayDiff -= 1;
    else {
        int dayOfYear = isLeapYear(yyyy) ? 366 : 365;
        dayDiff = dayOfYear - dayDiff;
    }
    int dayToYearStart = dayDiff;
    string monthNames[] = {"Sun", "Water", "Forest", "Mountains", "Money"};
    string weekNames[] = {"First", "Second", "Third", "Fourth", "Fifth", "Sixth"};
    if (dayToYearStart > 359) cout << "Feast " << (dayToYearStart - 359);
    else {
        if (dayToYearStart >= 180) cout << "Bates"; else cout << "Gill";
        dayToYearStart %= 180;
        cout << '-' << monthNames[dayToYearStart / 36];
        dayToYearStart %= 36;
        cout << '-' << weekNames[dayToYearStart / 6];
        dayToYearStart %= 6;
        cout << '-' << (dayToYearStart + 1);
    }
    cout << '-' << yyyy;
    if (dayOfCurrent < dayOfStart) cout << "bd";
    cout << '\n';
}

int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    string date;
    int dayOfStart = toDays(1998, 6, 25);
    while (getline(cin, date), date != "END") {
        if (date.find("Bates") != date.npos ||
            date.find("Gill") != date.npos ||
            date.find("Feast") != date.npos) {
            cout << "Enter date in old format\n";
            continue;
        }
        int year = stoi(date.substr(0, 4));
        int month = stoi(date.substr(5, 2));
        int day = stoi(date.substr(8, 2));
        int dayOfCurrent = toDays(year, month, day);
        toDate(dayOfStart, dayOfCurrent);
    }
    return 0;
}

总结

本题通过将日期转换为绝对天数，消除了闰年和月份差异带来的复杂性，从而在统一的数值空间内进行日历转换。核心技巧是：

• 使用格里高利历的累积天数公式快速计算绝对天数。
• 利用基准点（$1998$ 年 $6$ 月 $25$ 日）计算相对偏移，再按新历的固定周期（时期、月份、周）解析。
• 注意处理早于基准点的日期，附加 bd 后缀。
• 输入检测通过关键词识别新历格式，避免误转换。

该解法清晰且通用，适用于任何两种日历系统之间的转换，只需定义好基准点和周期划分即可。