1.1.3 USACO Friday the Thirteenth

﹏ヽ暗。殇╰゛Y 2023-07-07 12:41 5阅读 0赞

[https://train.usaco.org/usacoprob2?a=bJ2vRanSc7E&S=friday][https_train.usaco.org_usacoprob2_a_bJ2vRanSc7E_S_friday]

**Friday the Thirteenth**

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 positive and will not exceed 400.

**Note that the start year is NINETEEN HUNDRED, not NINETEEN NINETY.**

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.

### SAMPLE INPUT (file friday.in) ###

### 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 OUTPUT (file friday.out) ###

36 33 34 33 35 35 34

翻译：

[https://www.luogu.com.cn/problem/P1202][https_www.luogu.com.cn_problem_P1202]

## 题目描述 ##

1313 号又是一个星期五，那么 1313号在星期五比在其他日子少吗？

为了回答这个问题，写一个程序，要求计算每个月的十三号落在周一到周日的次数。给出 nn 年的一个周期，要求计算 19001900 年 11 月 11 日至 1900+n-11900+n−1 年 1212 月 3131 日中十三号落在周一到周日的次数。

这里有一些你要知道的:

1、19001900 年 11 月 11 日是星期一。

2、4,6,114,6,11 和 99 月有 3030 天，其他月份除了 22 月都有 3131 天，闰年 22 月有 2929 天，平年 22 月有 2828 天。

3、年份可以被 44 整除的为闰年 ( 1992=4\*4981992=4∗498 所以 19921992 年是闰年，但是 19901990 年不是闰年 )。

4、以上规则不适合于世纪年。可以被 400400 整除的世纪年为闰年，否则为平年。所以，1700,1800,1900,21001700,1800,1900,2100 年是平年，而 20002000 年是闰年。

## 输入格式 ##

一个正整数 nn。

## 输出格式 ##

依次输出周六、日、一、二、三、四、五在 1313 日出现的次数。

## 输入输出样例 ##

**输入 \#1**复制

**输出 \#1**复制

36 33 34 33 35 35 34

## 说明/提示 ##

【数据范围】  
对于 100\\%100% 的数据，1\\le n \\le 4001≤n≤400。

题目翻译来自NOCOW。

USACO Training Section 1.1

> 解法1： 使用公式计算出星期几，然后枚举每个月13号是星期几即可。

/*
 ID: L
 PROG: friday
 LANG: C++
 */
 #include<iostream>
 #include<cstdio>
 using namespace std;
 int a[10];
 int caculate_weekday(int y, int m, int d)//基姆拉尔森计算公式 
 {
 	if(m == 1 || m == 2)
 	{
 		m += 12;
 		y--;
 	}
 	int week = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;
 	switch(week)
 	{
 		case 0: return 1;//星期一 
 		case 1: return 2;//星期二 
 		case 2: return 3;
 		case 3: return 4;
 		case 4: return 5;
 		case 5: return 6;
 		case 6: return 7;//星期天 
 	}
 }
 
 int main()
 {
 	freopen("friday.in","r",stdin);
 	freopen("friday.out","w",stdout);
 //	ios::sync_with_stdio(false); 
 //	cin.tie(0);cout.tie(0);
 	int n;
 	cin >> n;
 	//cout << caculate_weekday(1900,1,1) << endl;
 	for(int y = 1900; y <= 1900+n-1; ++y)
 	{
 		for(int m = 1; m <= 12; ++m)
 		{
 			int k = caculate_weekday(y,m,13);
 		//	cout << k << endl;
 			if(k == 6) a[1]++;
 			else if(k == 7) a[2]++;
 			else if(k == 1) a[3]++;
 			else if(k == 2) a[4]++;
 			else if(k == 3) a[5]++;
 			else if(k == 4) a[6]++;
 			else if(k == 5) a[7]++;
 		}
 	}
 	for(int i = 1; i <= 6; ++i) cout << a[i] << " ";
 	cout << a[7] << endl;//需要注意最后一个输出是换行而不是空格 
 	return 0;
 }

> 解法2： 因为每7天为一个循环，如果已知总的天数sum和初始的日期y为星期x，可以根据公式(sum-y)%7+x,计算出第sum天是星期几。
> 
> 比如：
> 
> <table style="width:436pt;"> 
> <tbody> 
> <tr> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 星期天 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 星期一 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 星期二 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 星期三 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 星期四 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 星期五 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 星期六 </td> 
> </tr> 
> <tr> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> &nbsp; </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 1 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 2 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 3 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 4 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 5 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 6 </td> 
> </tr> 
> <tr> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 7 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 8 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 9 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 10 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 11 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 12 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 13 </td> 
> </tr> 
> <tr> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 14 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 15 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 16 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 17 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 18 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 19 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 20 </td> 
> </tr> 
> <tr> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 21 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 22 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 23 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 24 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 25 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 26 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 27 </td> 
> </tr> 
> <tr> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 28 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 29 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 30 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 31 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 32 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 33 </td> 
> <td style="border-color:#000000;text-align:center;vertical-align:top;width:62pt;"> 34 </td> 
> </tr> 
> </tbody> 
> </table>

> 假设已知1月1号是星期一。则15号即两个7天后同样为星期一。（15-1）%7+1=1。18号为星期四：（18-1）%7+1=4。
> 
> 假设已知1月3号为星期3，则26号为星期五。（26-3）%7+3=5
> 
> 假设已知1月26号为星期5，则17号为\[7-abs(17-26)\]%7+5.需要注意负数的问题。

/*
 ID: L
 PROG: friday
 LANG: C++
 */
 #include<iostream>
 #include<cstdio>
 using namespace std;
 int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
 int week[13];
 
 bool check(int y)
 {
 	if((y%400==0) || (y%4 == 0 && y % 100 != 0)) return 1;
 	else return 0;
 }
 
 int main()
 {
 	freopen("friday.in","r",stdin);
 	freopen("friday.out","w",stdout);
 //	ios::sync_with_stdio(false); 
 //	cin.tie(0);cout.tie(0);
 	int n;
 	cin >> n;
 	int sum_day = 0;//计算总天数 
 	//cout << caculate_weekday(1900,1,1) << endl;
 	for(int y = 1900; y <= 1900+n-1; ++y)//年 
 	{
 		for(int m = 1; m <= 12; ++m)//月 
 		{
 		 	if(m==2 && check(y)) month[2] = 29;
 		 	for(int k = 1; k <= month[m]; ++k)//日 
 		 	{
 		 		++sum_day;//总天数 
 		 		if(k == 13) week[(sum_day-1)%7 + 1]++; 
 			}
 			if(check(y)) month[2] = 28;//还原 
 		}
 	}
 	cout << week[6] << " " << week[7] << " ";
 	for(int i = 1; i <= 4; ++i) cout << week[i] << " ";
 	cout << week[5] << endl;
 	return 0;
 }

> 通过日期判断是星期几可以通过基姆拉尔森计算公式算出。

算法如下：

基姆拉尔森计算公式  
W= (d+2\*m+3\*(m+1)/5+y+y/4-y/100+y/400+1) mod 7  
在公式中d表示日期中的日数，m表示月份数，y表示年数。  
注意：在公式中有个与其他公式不同的地方：  
把一月和二月看成是上一年的十三月和十四月，例：如果是2004-1-10则换算成：2003-13-10来代入公式计算。

#include<iostream>
 using namespace std;
 
 void PrintfDay(int y,int m, int d); //声明PrintfDay函数
 
 void CaculateWeekDay(int y, int m, int d)
 {
 if(m==1||m==2) //把一月和二月换算成上一年的十三月和是四月
 {
 m+=12;
 y--;
 }
 int Week=(d+2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7;
 switch(Week)
 {
 case 0: PrintfDay(y,m,d); cout << "是星期一" << endl; break;
 case 1: PrintfDay(y,m,d); cout << "是星期二" << endl; break;
 case 2: PrintfDay(y,m,d); cout << "是星期三" << endl; break;
 case 3: PrintfDay(y,m,d); cout << "是星期四" << endl; break;
 case 4: PrintfDay(y,m,d); cout << "是星期五" << endl; break;
 case 5: PrintfDay(y,m,d); cout << "是星期六" << endl; break;
 case 6: PrintfDay(y,m,d); cout << "是星期日" << endl; break;
 }
 }
 
 void PrintfDay(int y,int m,int d)
 {
 cout << y << "年" << m << "月" << d << "日";
 }
 int main()
 {
 int year,month,day;
 cout << "请输入年 月 日" << endl;
 cin >> year >> month >> day ;
 CaculateWeekDay(year,month,day);
 return 0;
 }

> 蔡勒公式 蔡勒（Zeller）公式：是一个计算星期的公式。

随便给一个日期，就能用这个公式推算出是星期几。  
蔡勒公式如下：  
W = \[C/4\] - 2C + y + \[y/4\] + \[13 \* (M+1) / 5\] + d - 1  
或者是:w=y+\[y/4\]+\[c/4\]-2c+\[26(m+1)/10\]+d-1  
公式中的符号含义如下：  
w：星期； w对7取模得：0-星期日，1-星期一，2-星期二，3-星期三，4-星期四，5-星期五，6-星期六  
c：世纪-1（前两位数）  
y：年（后两位数）  
m：月（m大于等于3，小于等于14，即在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算）  
d：日 \[ \]代表取整，即只要整数部分。  
下面以中华人民共和国成立100周年纪念日那天（2049年10月1日）来计算是星期几，过程如下：  
w=y+\[y/4\]+\[c/4\]-2c+\[26(m+1)/10\]+d-1  
=49+\[49/4\]+\[20/4\]-2×20+\[26×(10+1)/10\]+1-1  
=49+\[12.25\]+5-40+\[28.6\]  
=49+12+5-40+28  
=54 (除以7余5)  
即2049年10月1日（100周年国庆）是星期五。  
再比如计算2013年3月7日，过程如下：  
w=y+\[y/4\]+\[c/4\]-2c+\[26(m+1)/10\]+d-1  
=13+\[13/4\]+\[20/4\]-2\*20+\[26\*(3+1)/10\]+7-1  
=-3 (除以7余4，注意对负数的取模运算！)

int ReturnWeekDay( unsigned int iYear, unsigned int iMonth, unsigned int iDay )
    {
    	int iWeek = 0;
    	unsigned int y = 0, c = 0, m = 0, d = 0;
     
    	if ( iMonth == 1 || iMonth == 2 )
    	{
    		c = ( iYear - 1 ) / 100;
    		y = ( iYear - 1 ) % 100;
    		m = iMonth + 12;
    		d = iDay;
    	}
    	else
    	{
    		c = iYear / 100;
    		y = iYear % 100;
    		m = iMonth;
    		d = iDay;
    	}
    	
    	iWeek = y + y / 4 + c / 4 - 2 * c + 26 * ( m + 1 ) / 10 + d - 1;    //蔡勒公式
    	iWeek = iWeek >= 0 ? ( iWeek % 7 ) : ( iWeek % 7 + 7 );    //iWeek为负时取模
    	if ( iWeek == 0 )    //星期日不作为一周的第一天
    	{
    		iWeek = 7;
    	}
     
    	return iWeek;
    }

[https_train.usaco.org_usacoprob2_a_bJ2vRanSc7E_S_friday]: https://train.usaco.org/usacoprob2?a=bJ2vRanSc7E&S=friday
[https_www.luogu.com.cn_problem_P1202]: https://www.luogu.com.cn/problem/P1202