首页 > ACM题库 > HDU-杭电 > HDU 4168-Citizenship Application[解题报告]HOJ
2015
05-23

HDU 4168-Citizenship Application[解题报告]HOJ

Citizenship Application

问题描述 :

In Canada, once you have landed as a permanent resident, you can apply for citizenship if you have lived in Canada for at least 1095 days (approximately 3 years) in the 1460 days (approximately 4 years) immediately prior to the application for citizenship (i.e. the date of application is not counted). Any time travelling outside Canada is not counted as a day living in Canada. Furthermore, if you are already residing in Canada (e.g. to study) before landing as a permanent resident during the 1460-day period, that time in Canada before the landing date (up to 730 days) can be counted as half rounded down (e.g. if the waiting time was 101 days, that can be counted as 50 days). Thus, the starting date of residence is counted as a half day if it occurs before the landing date (assuming that it is not more than 730 days before), or a full day if it coincides with the landing date.

In this problem, you will be determining the first day on which an application for citizenship can be made.

输入:

The input consists of a number of cases. The first line of each case gives the starting date of residence in the country, and the second line gives the landing date as a permanent resident. The third line gives an integer N (0 <= N <= 100) indicating the number of travels outside of Canada. Each of the next N lines contains two dates separated by a space, indicating the start and end date (inclusive) of travel outside of Canada. That is, you are considered to be outside of Canada from the start date through the end date.

You may assume that the starting date of residence is no later than the landing date. You may also assume that the start date of each travel is no later than the end date, and no travel outside of Canada will be longer than 200 days. Of course, you can assume that your trips do not include the starting date of residence and the landing date, and no two trips overlap. No trips take place before the starting date of residence. All dates are given in the form Month/Day/Year and are valid dates, and no dates in the input will be before January 1, 1980 or after December 31, 2020.

输出:

The input consists of a number of cases. The first line of each case gives the starting date of residence in the country, and the second line gives the landing date as a permanent resident. The third line gives an integer N (0 <= N <= 100) indicating the number of travels outside of Canada. Each of the next N lines contains two dates separated by a space, indicating the start and end date (inclusive) of travel outside of Canada. That is, you are considered to be outside of Canada from the start date through the end date.

You may assume that the starting date of residence is no later than the landing date. You may also assume that the start date of each travel is no later than the end date, and no travel outside of Canada will be longer than 200 days. Of course, you can assume that your trips do not include the starting date of residence and the landing date, and no two trips overlap. No trips take place before the starting date of residence. All dates are given in the form Month/Day/Year and are valid dates, and no dates in the input will be before January 1, 1980 or after December 31, 2020.

样例输入:

1/1/2011
9/1/2011
0
1/1/2011
9/1/2011
1
10/1/2011 10/10/2011
1/1/2011
9/1/2011
2
2/1/2011 3/28/2011
10/1/2011 10/10/2011
1/1/2009
1/1/2011
0
12/31/2020
12/31/2020
0

样例输出:

5/2/2014
5/12/2014
6/9/2014
12/31/2012
12/31/2023

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
#define dMax  1000010

int sum[dMax],a[dMax],Mon[3],Dat[3],Yea[3];
bool is_1[dMax];
int tot=1;
int St[3];
struct Triple{
    int M,D,Y;
    Triple(int _M=0,int _D=0,int _Y=0):M(_M),D(_D),Y(_Y){};
    bool operator<(const Triple & T)const{
        if(M!=T.M)  return M<T.M;
        if(D!=T.D)  return D<T.D;
        return Y<T.Y;
    }
}Find[dMax];

map<Triple,int>mp;

void init()
{
    int i,j,k;
    for(i=1900;i<=3000;i++)
        for(j=1;j<=12;j++){
            if(j==1 || j==3 || j==5|| j==7 || j==8 || j==10 || j==12){
                for(k=1;k<=31;k++){
                    mp[Triple(j,k,i)]=tot;
                    Find[tot]=Triple(j,k,i);
                    tot++;
                }
            }else if( j==4 || j==6 || j==9 || j==11 ){
                for(k=1;k<=30;k++){
                    mp[Triple(j,k,i)]=tot;
                    Find[tot]=Triple(j,k,i);
                    tot++;
                }
            }else{
                if((i%400==0) || (  i%100!=0 && i%4==0) ){
                    for(k=1;k<=29;k++){
                        mp[Triple(j,k,i)]=tot;
                        Find[tot]=Triple(j,k,i);
                        tot++;
                    }
                }else{
                    for(k=1;k<=28;k++){
                        mp[Triple(j,k,i)]=tot;
                        Find[tot]=Triple(j,k,i);
                        tot++;
                    }
                }
            }
        }
}

void Deal()
{
    int he = St[0] , ta , i , j , End = St[1]+100000 , m ;
    memset(a,0,sizeof(a));
    for( i = St[0]; i<St[1]; i++)   a[i]=1;
    for( i = St[1]; i<End; i++)   a[i]=2;
    scanf("%d",&m);
    while(m--){
        scanf("%d/%d/%d%d/%d/%d",Mon,Dat,Yea,Mon+1,Dat+1,Yea+1);
        he = mp[Triple(Mon[0],Dat[0],Yea[0])];
        ta = mp[Triple(Mon[1],Dat[1],Yea[1])];
        for(i=he; i<=ta; i++)    a[i] = 0;
    }
    sum[St[1]-1460-1]=0;
    for(i=St[1]-1460;i<End;i++)    sum[i] = sum[i-1] + a[i];
    for(i=St[1]-1460;;i++){
        if((sum[i+1460-1]-sum[i-1])/2>= 1095) break;
    }
    Triple ans = Find[i+1460];
    printf("%d/%d/%d\n",ans.M,ans.D,ans.Y);
}



int main()
{
    init();
    //printf("tot=%d\n",tot);
    while(scanf("%d/%d/%d",Mon,Dat,Yea)!=EOF){
        scanf("%d/%d/%d",Mon+1,Dat+1,Yea+1);
        St[0] = mp[Triple(Mon[0],Dat[0],Yea[0])];
        St[1] = mp[Triple(Mon[1],Dat[1],Yea[1])];
        Deal();
    }
	return 0;
}