解題區/解題區 - UVa

UVa 1557 - Calendar Game

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一個起始日期，兩名玩家輪流操作，操作方式有兩種，將日期往後延一天，將月份往後延一個月，抵達 November 4, 2001 的人獲勝，如果發生移動到不合法的日期則視為無效。

必須考慮閏年變化。

Sample Input

1
2
3
4
3
2001 11 3
2001 11 2
2001 10 3

Sample Output

1
2
3
YES
NO
NO

Solution

由於年份差最多 100，可以直接根據年月日做狀態搜索。要處理移動時，發生跨年、跨月，這方面會稍微麻煩一點。閏年要額外處理對 2/29 的日期判斷，並且移動時不可超出指定的日期之後。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
const int mday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int dp[128][16][32], used[128][16][32], dcases = 0;
int validDate(int yyyy, int mm, int dd) {
    if (mm < 1 || mm > 12)	
        return 0;
    if ((yyyy%4 == 0 && yyyy%100 != 0) || (yyyy%400) == 0) {
        if (mm == 2) {
            if (dd < 1 || dd > 29)	
                return 0;
        } else {
            if (dd < 1 || dd > mday[mm])
                return 0;
        }			
    } else {
        if (dd < 1 || dd > mday[mm])
            return 0;
    }
    return 1;
}
int complete(int yyyy, int mm, int dd) {
    return yyyy == 2001 && mm == 11 && dd == 4;
}
int fail(int yyyy, int mm, int dd) {
    if (!validDate(yyyy, mm, dd))
        return 1;
    if (yyyy > 2001)	return 1;
    if (yyyy < 2001)	return 0;
    if (mm > 11)		return 1;
    if (mm < 11)		return 0;
    if (dd > 4)			return 1;
    if (dd < 4)			return 0;
    return 0;
}
void nextMonth(int &yyyy, int &mm, int &dd) {
    mm++;
    if (mm == 13)	yyyy++, mm = 1;
}
void nextDay(int &yyyy, int &mm, int &dd) {
    int mday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if ((yyyy%4 == 0 && yyyy%100 != 0) || (yyyy%400) == 0)
        mday[2] = 29;
    dd++;
    if (dd > mday[mm])
        mm++, dd = 1;
    if (mm == 13)	yyyy++, mm = 1;
}
int dfs(int yyyy, int mm, int dd) {
    if (fail(yyyy, mm, dd))
        return 0;
    if (complete(yyyy, mm, dd))
        return 1;
    if (used[yyyy-1900][mm][dd] == dcases)
        return dp[yyyy-1900][mm][dd];
    int &ret = dp[yyyy-1900][mm][dd];
    int y, m ,d;	
    ret = 0, used[yyyy-1900][mm][dd] = dcases;
    
    y = yyyy, m = mm, d = dd;
    nextMonth(y, m, d);
    if (complete(y, m, d))
        ret = 1;
    if (!fail(y, m, d))
        ret |= !dfs(y, m, d);
    
    y = yyyy, m = mm, d = dd;
    nextDay(y, m, d);
    if (complete(y, m, d))
        ret = 1;
    if (!fail(y, m, d))
        ret |= !dfs(y, m, d);
    return ret;
}
int main() {
    int testcase;
    int yyyy, mm, dd;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &yyyy, &mm, &dd);
        dcases ++;
        printf("%s\n", dfs(yyyy, mm, dd) ? "YES" : "NO");
    }
    return 0;
}
/*
3
2001 11 3
2001 11 2
2001 10 3
*/