Finding the day of the thirteenth of every month over a period of years

I am currently trying to solve some problems from the USACO training website in preparation for an unrelated C++ programming competition.

However, I am stuck on this problem:

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

The number N is provided in an input file and the output is to be a file with seven numbers in it, each representing the number of 13th's falling on a particular day of the week.

I was wondering how you guys would approach this problem. I am not looking for code or anything since that would just defeat the purpose of me doing this, instead just a starting point or an algorithm would be helpful.

So far the only thing I could think of is using the Doomsday Algorithm, however I am unsure about how I would implement that in code.

Any help would be greatly appreciated.

As Denny says, N is so small that you can easily iterate through the months using a table of days-in-a-month and a simple is-a-leap-year predicate to handle February. Just find out what day the 13th of Jan was in 1900 and then add up the elapsed days until 13th Feb, then 13th March etc.. Use a % operator to wrap the # of elapsed days back into a day-of-week value.

N is less than 400? well you just need to go over 365.25*400=146100 days at max. sounds easy to enumerate all of them, convert dates into year/month/date (with your favorite date conversion routine), testing for day of week is trivial.

I would precalculate the table though.

Just use brute force. Like this pseudocode example:

from datetime import date

day_names = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday',
             'Saturday', 'Sunday']
counts = [0] * 7
for year in range(1900, 2300):
    for month in range(1, 13):
        counts[date(year, month, 13).weekday()] += 1
for day, count in zip(day_names, counts):
    print('%s: %d' % (day, count))

The "hard" part is calculating the day of the week a date falls on. In C(++), you can use the mktime and localtime library functions if you know that your platform handles a large enough date range.