Skip to content

11509: 【原1509】节日计算器

题目

题目描述

author: 金耀楠 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1509

Description

有一类节日的日期并不是固定的，而是以“a月的第b个星期c”的形式定下来的，比如说母亲节就定为每年的五月的第二个星期日。

现在，给你a，b，c和y1, y2(1850 ≤ y1, y2 ≤ 2050)，希望你输出从公元y1年到公元y2年间的每年的a月的第b个星期c的日期。

提示：关于闰年的规则：年份是400的整数倍时是闰年，否则年份是4的倍数并且不是100的倍数时是闰年，其他年份都不是闰年。例如1900年就不是闰年，而2000年是闰年。

为了方便你推算，已知1850年1月1日是星期二。

Input Format

输入包含恰好一行，有五个整数a, b, c, y1, y2。其中c=1, 2, ……, 6, 7分别表示星期一、二、……、六、日。

Output Format

对于y1和y2之间的每一个年份，包括y1和y2，按照年份从小到大的顺序输出一行。

如果该年的a月第b个星期c确实存在，则以"yyyy/mm/dd"的格式输出，即输出四位数的年份，两位数的月份，两位数的日期，中间用斜杠“/”分隔，位数不足时前补零。

如果该年的a月第b个星期c并不存在，则输出"none"（不包含双引号)。

Sample Input

5 2 7 2014 2015

Sample Output

2014/05/11
2015/05/10

Limits

所有评测用例都满足：1 ≤ a ≤ 12，1 ≤ b ≤ 5，1 ≤ c ≤ 7，1850 ≤ y1, y2 ≤ 2050。

FineArtz's solution 

/* 节日计算器 */
#include <iostream>
#include <string>
using namespace std;

inline int succ(int x) { return ((x + 1) % 7 == 0) ? 7 : ((x + 1) % 7); }
inline string f(int x) {
    string ret = "";
    if (x / 10){
        ret += char(x / 10 + '0');
    }
    else ret += "0";
    ret += char(x % 10 + '0');
    return ret;
}
int main(){
    int date[205][15][35] = {0};
    date[0][1][1] = 2;
    for (int yy = 0; yy <= 2050 - 1850; ++yy){
        int day = 0, lday = 0, year = yy + 1850;
        for (int mm = 1; mm <= 12; ++mm)
        {
            switch(mm){
            case 1: case 3: case 5: case 7: case 8: case 10: case 12:
                day = 31;
                break;
            case 4: case 6: case 9: case 11:
                day = 30;
                break;
            case 2:
                day = ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0)) ? 29 : 28;
                break;
            }
            if (mm > 1) date[yy][mm][1] = succ(date[yy][mm - 1][lday]);
            else if (yy != 0) date[yy][mm][1] = succ(date[yy - 1][12][31]);
            for (int dd = 2; dd <= day; ++dd)
                date[yy][mm][dd] = succ(date[yy][mm][dd - 1]);
            lday = day;
            day = 0;
        }
    }
    int a, b, c, y1, y2;
    cin >> a >> b >> c >> y1 >> y2;
    for (int yy = y1; yy <= y2; ++yy){
        int dd = 1, cnt = 0;
        while (date[yy - 1850][a][dd]){
            if (date[yy - 1850][a][dd] == c) ++cnt;
            if (cnt == b){
                cout << yy << "/" << f(a) << "/" << f(dd) << endl;
                break;
            }
            ++dd;
        }
        if (!date[yy - 1850][a][dd]) cout << "none" << endl;
    }
    return 0;
}

ligongzzz's solution 

#include "iostream"
#include "cstdio"
using namespace std;

int main() {
    int a, b, c, y1, y2;
    cin >> a >> b >> c >> y1 >> y2;
    --c;

    int months[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

    for (int year = 1850, weekday = 1; year <= y2; ++year) {
        //判断是否是闰年
        bool is_year = false;
        if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
            months[2] = 29;
            is_year = true;
        }
        else {
            months[2] = 28;
            is_year = false;
        }
        if(year<y1){
            if (is_year)
                weekday = (weekday + 2) % 7;
            else
                weekday = (weekday + 1) % 7;
            continue;
        }
        int cur_day = weekday;
        //计算月份
        for (int month = 1; month < a; ++month)
            cur_day = (cur_day + months[month] % 7) % 7;
        //计算第一个日期
        int first_date = (c + 7 - cur_day) % 7 + 1;
        int date = first_date + (b - 1) * 7;
        if (date <= months[a])
            printf("%d/%02d/%02d\n", year, a, date);
        else
            printf("none\n");

        //调整日期
        if (is_year)
            weekday = (weekday + 2) % 7;
        else
            weekday = (weekday + 1) % 7;
    }

    return 0;
}

q4x3's solution 

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    int mon, b, c, y1, y2;
    int t[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    cin >> mon >> b >> c >> y1 >> y2;
    int tmp = y1 - 1 - 1849;
    int one = 1 + tmp + tmp / 4;
    if (y1 - 1 >= 1901) -- one;
    one = one % 7;//y1 - 1年1.1的星期
    for (int i = y1;i <= y2;++ i) {
        bool flag = 0;
        if (i % 4 == 0 && i != 1900) t[1] = 29;
        one += 1;
        if ((i - 1) % 4 == 0 && i - 1 != 1900) ++ one;
        one %= 7;//i年1.1
        int monone = one;
        for (int j = 0;j < mon - 1;++ j) monone += t[j];
        monone %= 7;
        if (monone == 0) monone = 7;
        int b_c;
        if (c >= monone) {
            b_c = (b - 1) * 7 + 1 + c - monone;
        }
        if (c < monone) {
            int c1 = c + 7 - monone + 1;
            b_c = (b - 1) * 7 + c1;
        }
        if (b_c < 1 || b_c > t[mon - 1]) cout << "none" << endl;
        else {
            cout << i << '/';
            cout << setw(2) << setfill('0') << mon;
            cout << '/' << setw(2) << setfill('0') << b_c << endl;
        }
        t[1] = 28;
    }
}

skyzh's solution

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int a, b, c, y1, y2;
    cin >> a >> b >> c >> y1 >> y2;
    int y = 1850;
    int m = 1;
    int d = 0;
    int day = 1;
    int week = 1;
    int dom[] = {31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int _dcnt[8] = { 0 };
    bool found = false;
    while (true) {
        ++d;
        ++day;
        int _dom = dom[m - 1];
        if (m == 2) {
            _dom = 28;
            if (y % 400 == 0 || y % 100 != 0 && y % 4 == 0) {
                _dom = 29;
            }
        }
        if (day > 7) {
            day = 1;
            ++week;
        }
        if (d > _dom) {
            d = 1;
            ++m;
            for (int i = 1; i <= 7; i++) _dcnt[i] = 0;
            week = 1;
        }
        if (m > 12) {
            m = 1;
            if (y1 <= y && y <= y2 && found == false) printf("none\n");
            ++y;
            found = false;
        }
        ++_dcnt[day];
        if (y1 <= y && y <= y2 && m == a && _dcnt[c] == b && day == c) {
            printf("%d/%02d/%02d\n", y, m, d);
            found = true;
        }
        if (y > y2) break;
    }
    return 0;
}

WashSwang's solution 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char cmd1[10],cmd2[10],s[1010000],ans[1010000];
int t,n,top,stack[1050000],vis[1010000];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void inorderEncode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            top--;
            ans[i++]=s[now-1];
            if (rs(now)<=n) stack[top++]=rs(now);
        }
    }
}
inline void preorderEncode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            ans[i++]=s[now-1];
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            vis[now]++;
            if (rs(now)<=n) stack[top++]=rs(now);
        }
        else
            top--;
    }
}
inline void postorderEncode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            vis[now]++;
            if (rs(now)<=n) stack[top++]=rs(now);
        }
        else
        {
            ans[i++]=s[now-1];
            top--;
        }
    }
}
inline void inorderDecode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            top--;
            ans[now-1]=s[i++];
            if (rs(now)<=n) stack[top++]=rs(now);
        }
    }
}
inline void preorderDecode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            ans[now-1]=s[i++];
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            vis[now]++;
            if (rs(now)<=n) stack[top++]=rs(now);
        }
        else
            top--;
    }
}
inline void postorderDecode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            vis[now]++;
            if (rs(now)<=n) stack[top++]=rs(now);
        }
        else
        {
            ans[now-1]=s[i++];
            top--;
        }
    }
}
int main() {
    cin>>t;
    ios::sync_with_stdio(false);
    for (int i=0;i<t;++i){
        top=0;
        memset(ans,0,sizeof(ans));
        memset(vis,0,sizeof(vis));
        cin>>n>>cmd1>>cmd2>>s;
        if (strcmp(cmd1,"INORDER")==0){
            if (strcmp(cmd2,"ENCODE")==0)
                inorderEncode(s,n);
            else
                inorderDecode(s,n);
        }
        if (strcmp(cmd1,"PREORDER")==0){
            if (strcmp(cmd2,"ENCODE")==0)
                preorderEncode(s,n);
            else
                preorderDecode(s,n);
        }
        if (strcmp(cmd1,"POSTORDER")==0){
            if (strcmp(cmd2,"ENCODE")==0)
                postorderEncode(s,n);
            else
                postorderDecode(s,n);
        }
        cout<<ans<<endl;
    }
    return 0;
}

yyong119's solution 

#include <iostream>
#include <vector>
#include <map>
#include <iomanip>
using namespace std;

bool isLeapYear(int year) {

     int temp = year % 400;
     if (temp == 0) return true;
     else {
         temp = year % 4;
         int temp1 = year % 100;
         if (temp == 0 && temp1 != 0) return true;
         else return false;
    }
}

int days(bool leap, int month) {

    switch (month) {
         case 1:
             return 0;
         case 2:
             return 31;
         case 3:
             return leap ? 60 : 59;
         case 4:
             return leap ? 91 : 90;
         case 5:
             return leap ? 121 : 120;
         case 6:
             return leap ? 152 : 151;
         case 7:
             return leap ? 182 : 181;
         case 8:
             return leap ? 213 : 212;
         case 9:
             return leap ? 244 : 243;
         case 10:
             return leap ? 274 : 273;
         case 11:
             return leap ? 305 : 304;
         case 12:
             return leap ? 335 : 334;
    }
}

int monthDays(bool leap, int month) {

     switch (month) {
         case 1:
         case 3:
         case 5:
         case 7:
         case 8:
         case 10:
         case 12:
             return 31;
         case 4:
         case 6:
         case 9:
         case 11:
         return 30;
         case 2:
             return leap ? 29 : 28;
    }
}

int main() {
    int month, week, day, year1, year2, leapCount(0);
    cin >> month >> week >> day >> year1 >> year2;
    for (int i = 1850; i < year1; i++)
        if (isLeapYear(i)) leapCount++;
    for (int i = year1; i <= year2; i++) {
        bool leap = isLeapYear(i);
        int totalDays = (i - 1850) * 365 + leapCount + days(leap, month);
        int weekDay = totalDays % 7 + 2;
        int weekCount = day < weekDay ? 1 : 2;
        int ans = 8 - weekDay + (week - weekCount) * 7 + day;
        if (ans <= monthDays(leap, month)) {
            cout << i << "/";
            if (month < 10)
                cout << 0;
            cout << month << "/";
            if (ans < 10)
                cout << 0;
            cout << ans << endl;
        }
        else cout << "none" << endl;
        if (leap) leapCount++;
    }
    return 0;
}