首页 > 图论 > 最小生成树 > hdu 1459 Calendar-最小生成树-[解题报告]
2013
12-11

hdu 1459 Calendar-最小生成树-[解题报告]

Calendar

问题描述 :

Most of us have a calendar on which we scribble details of important events in our lives—visits to the dentist, the Regent 24 hour book sale, Programming Contests and so on. However there are also the fixed dates: partner’s birthdays, wedding anniversaries and the like; and we also need to keep track of these. Typically we need to be reminded of when these important dates are approaching—the more important the event, the further in advance we wish to have our memories jogged.

Write a program that will provide such a service. The input will specify the year for which the calendar is relevant (in the range 1901 to 1999). Bear in mind that, within the range specified, all years that are divisible by 4 are leap years and hence have an extra day (February 29th) added. The output will specify “today’s” date, a list of forthcoming events and an indication of their relative importance.

输入:

The first line of input will contain an integer representing the year (in the range 1901 to 1999). This will be followed by a series of lines representing anniversaries or days for which the service is requested. An anniversary line will consist of the letter `A’; three integer numbers (D, M, P) representing the date, the month and the importance of the event; and a string describing the event, all separated by one or more spaces. P will be a number between 1 and 7 (both inclusive) and represents the number of days before the event that the reminder service should start. The string describing the event will always be present and will start at the first non-blank character after the priority. It will never be longer than 50 characters including spaces. A date line will consist of the letter `D’ and the date and month as above. All anniversary lines will precede any date lines. No line will be longer than 255 characters in total. The file will be terminated by a line consisting of a single #.

输出:

Output will consist of a series of blocks of lines, one for each date line in the input. Each block will consist of the requested date followed by the list of events for that day and as many following days as necessary. The output should specify the date of the event (D and M), right justified in fields of width 3, and the relative importance of the event. Events that happen today should be flagged as shown below, events that happen tomorrow should have P stars, events that happen the day after tomorrow should have P-1 stars, and so on. If several events are scheduled for the same day, order them by relative importance (number of stars). If there is still a conflict, order them by their appearance in the input stream. Follow the format used in the example below. Leave 1 blank line between blocks.

样例输入:

1993
A 23 12 5 Partner's birthday
A 25 12 7    Christmas
A 20 12 1 Unspecified Anniversary
D 20 12
#

样例输出:

Today is: 20 12
 20 12 *TODAY* Unspecified Anniversary
 23 12 ***     Partner's birthday
 25 12 ***     Christmas

http://acm.hit.edu.cn/hoj/problem/view?id=1459

Every even number greater than 4 can be written as the sum of two odd primenumbers.

#include<stdio.h>
#include<math.h>

bool pri(int n);

int main()
{
    int n, i;
    bool flag;

    while (scanf("%d", &n) && n)
    {
        flag = 0;
        for (i = 2; i <= n/2; i++)
        {
            if(pri(i) && pri(n-i))
            {
                flag = 1;
                printf("%d = %d + %d\n", n, i, n-i);
                break;
            }
        }

        /*还没被证伪*/

        /*
        if (flag == 0)
            printf("Goldbach's conjecture is wrong.\n");
        */
    }

    return 0;
}

bool pri(int n)
{
    int i;
    for (i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

 

解题转自:http://blog.csdn.net/epk_lee/article/details/8232388


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧