[UVa] 13275 - Leap Birthdays

題目

Link: UVa 13275 - Leap Birthdays

13275 Leap Birthdays

Do you know anyone, whose birthday is on 29- th February? I don’t. But I was thinking about such a person and it made me sad. A person like that would be so unlucky, don’t you think? Unlike others, they will have a birthday every four years. And sometimes, not even in four years. Because we know 29-th February only occurs in leap years. And a year will be a leap year if and only if the following function returns true.

bool isLeapYear(int year)
{
    if (year % 400 == 0) return true;
    else if(year % 100 == 0) return false;
    else if(year % 4 == 0) return true;
    else return false;
}

The above function means, a year that is divisible by 4 and not divisible by 100 are leap years but with the exception that years that are divisible by 400 are also leap years (although that is also divisible by 100).
But it’s just so unfair. Take for instance a person who is born on 29-th February, 1888. He will have another birthday on 29- th February, 1892. Then in 1896. And then in 1900 he won’t have one. Because it’s a year which is not divisible by 400 but is divisible by 100. What a pity! He will have to wait 8 years for his next birthday in 1904.
So if you are given the birthday of a person and a query year QY , you can’t easily say how many birthdays he had till 31-st December of the year QY . There are complex mathematics involved. And it can make you very sad. So these are very dangerous problems for a human to solve. Honestly speaking, I myself got a bit sad and depressed while writing this problem thinking about those very unfortunate persons. I don’t want to think of them anymore, so please solve the problem for me. Given a year QY , I was wondering how many birthdays a person has celebrated by the end of the year QY . You will also be given the person’s birthday.
For example, given a person whose birthday is on 29-th February, 1888, how many birthdays does he celebrate if QY = 1910 ? The answer is 4 (1892, 1896, 1904 and 1908). Similarly a person having birthday on 31-st December, 1987 celebrated 3 birthdays if QY = 1990 . Note, a person just being born, can’t celebrate his birthday. That’s why we didn’t count the birth year as a birthday.

Input

First line will contain an integer, T (T ≤ 100) , the number of test cases. Each case will contain four integers per line: D , M (1 ≤ M ≤ 12) , Y (1850 ≤ Y ≤ 2016) and QY (Y ≤ QY ≤ 3000) . Together, D , M and Y will form a person’s birthday where D denotes day ( D will always be a valid day based on M and Y ), M denotes month and Y denotes year. You can assume, that it will always be a valid date. QY (as described above), means the year upto which you need to calculate (inclusive).

Output

Output one line per case: ‘Case C: X’, where C is the case number and X is the answer.
See the sample for clarification.

Sample Input

4
29 2 1888 1910
29 2 1988 2010
1 1 1988 2010
31 12 1988 2010

Sample Output

Case 1: 4
Case 2: 5
Case 3: 22
Case 4: 22

程式碼

C++

#include <iostream>

int answer(int day, int month, int birth_year, int query_year);

int main()
{
  int day, month, birth_year, query_year;
  int test_cases, current_test_case;

  std::ios::sync_with_stdio(false);

  std::cin >> test_cases;

  for (current_test_case = 1; current_test_case <= test_cases; ++current_test_case)
  {
    std::cin >> day >> month >> birth_year >> query_year;
    std::cout << "Case " << current_test_case << ": "
              << answer(day, month, birth_year, query_year) << std::endl;
  }

  return 0;
}

inline int birthdays(int year) { return year / 400 - year / 100 + year / 4; }

int answer(int day, int month, int birth_year, int query_year)
{
  if (day == 29 and month == 2)
    return birthdays(query_year) - birthdays(birth_year);
  else return query_year - birth_year;
}

C++

#include <iostream>
#include <vector>

static std::vector<int> leap_years;

void init();

int answer(int day, int month, int birth_year, int query_year);

int main()
{
  int day, month, birth_year, query_year;
  int test_cases, current_test_case;

  std::ios::sync_with_stdio(false);

  init();

  std::cin >> test_cases;

  for (current_test_case = 1; current_test_case <= test_cases; ++current_test_case)
  {
    std::cin >> day >> month >> birth_year >> query_year;
    std::cout << "Case " << current_test_case << ": "
              << answer(day, month, birth_year, query_year) << std::endl;
  }

  return 0;
}

inline bool is_leap_year(int year)
{ return year % 400 == 0 or (year % 100 != 0 and year % 4 == 0); }

void init()
{
  constexpr int start_year = 1852, end_year = 2996;
  for (int current = start_year; current <= end_year; current += 4)
    if (is_leap_year(current)) leap_years.push_back(current);
}

int answer(int day, int month, int birth_year, int query_year)
{
  if (day == 29 and month == 2)
  {
    int start = 0, end = 0;
    for (auto leap_year : leap_years)
    {
      if (birth_year >= leap_year) ++start;
      if (query_year >= leap_year) ++end;
      else break;
    }
    return end - start;
  }
  else return query_year - birth_year;
}

Show Comments