code logic: Friday the Thirteenth (USACO)

Question

I am a newbie to coding and I am trying to code for the "Friday the Thirteenth" problem posted in USACO, which requires us to 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.

It was given that Jan 1, 1900 was on a Monday. We are not supposed to use any in-built functions.

I tried to solve this problem with a different approach (which I think isn't the best approach). My code (in C) is given below:

#include<stdio.h>
int daysInMonth (int month, int year) 
{

/*
   30 should be returned if the months are Apr, June, Sept and Nov.
   31 should be returned in all other cases.
   29 should be returned if the month is Feb and the year is a leap year
 */ 

if (month == 1)     //Feb
    {
    if (year % 4 == 0 || (year % 100 != 0 && year % 400 == 0))  //leap year
        return 29;
    else
        return 28;

    }
switch (month)
    {
    case 3:
    case 5:
    case 8:
    case 10: return 30;
    default: return 31;

    }

}


void main () 
{
int month, year, n, i, noOfDays, start = 0, result[] = { 0, 0, 0, 0, 0, 0, 0 }, day = 0, daycheck = 1;
scanf ("%d", &n);
for (year = 1900; year <= 1900 + n - 1; ++year)
{
    for (month = 0; month < 12; ++month)
    {
        if (month == 0 && year == 1900) // to identify the first 13th and the day it falls on
        {
            while (daycheck != 13)
            {
                ++daycheck;
                day = (day + 1) % 7;

            }

            ++result[day];
        }

        else
        {
            if (month == 0) //If January, add the noOfDays of the prev. month i.e. December
                noOfDays = 31;

            else
              noOfDays = daysInMonth (month - 1, year);

            day += (noOfDays - 28); // Adding a multiple of 7 (here, 28) does not change the day
            day %= 7;

            ++result[day];

        }

    }

}

for (i = 0; i < 7; ++i)
    printf("%d ", result[(i + 5) % 7]); //Sat, Sun, Mon, Tue, Wed, Thu, Fri

}

For an input of 20, the expected output is 36 33 34 33 35 35 34. However, my output turns out to be 35 35 33 35 32 35 35.

Even though my answer is within the range of the expected output, there's something wrong with my logic that makes it erroneous.

I would appreciate if someone could point out the error. I would also be happy if you could suggest a better way to approach this problem. I am a student of Computer Science and am yet to learn about algorithms in detail.

Note that `void main()` is only valid on Windows. Everywhere else, `int main(void)` is preferable when command line arguments are ignored. See [What should `main()` return in C and C++?](https://stackoverflow.com/questions/204476/). — Jonathan Leffler, Dec 30 '17 at 01:44

score 4 · Accepted Answer · answered Dec 28 '17 at 18:05

4

Your leap year condition is wrong.

Change the Leap year condition as follows.

 int daysInMonth (int month, int year) 
    {
    if (month == 1)     //Feb
        {
    if (( year%400 == 0)|| (( year%4 == 0 ) &&( year%100 != 0)))
            return 29;
        else
            return 28;
        }

answered Dec 28 '17 at 18:05

Santhosh

335
1
4
23

The diagnosis is correct and the solution works. However, most of the time (for the next 381 years or so), the first term will divide by 400 pointlessly. It is better to avoid that. For example: `if (year % 4 != 0) return 28; if (year % 100 != 0) return 29; if (year % 400 == 0) return 29; return 28;`. Most of the time, the modulo 4 operation does not yield 0 so the code returns. A lot of the rest of the time, the modulo 100 operation doesn't return 0 so the code returns. That leaves only the century years to undergo the modulo 400 operation. – Jonathan Leffler Dec 30 '17 at 01:42

code logic: Friday the Thirteenth (USACO)

1 Answers1