首页 > ACM题库 > HDU-杭电 > HDU 2910-Stopped Watches[解题报告]HOJ
2014
02-21

HDU 2910-Stopped Watches[解题报告]HOJ

Stopped Watches

问题描述 :

In the middle of Tyrrhenian Sea, there is a small volcanic island called Chronus. The island is now uninhabited but it used to be a civilized island. Some historical records imply that the island was annihilated by an eruption of a volcano about 800 years ago and that most of the people in the island were killed by pyroclastic flows caused by the volcanic activity. In 2003, a European team of archaeologists launched an excavation project in Chronus Island. Since then, the project has provided many significant historic insights. In particular the discovery made in the summer of 2008 astonished the world: the project team excavated several mechanical watches worn by the victims of the disaster. This indicates that people in Chronus Island had such a highly advanced manufacturing technology. Shortly after the excavation of the watches, archaeologists in the team tried to identify what time of the day the disaster happened, but it was not successful due to several difficulties. First, the extraordinary heat of pyroclastic flows severely damaged the watches and took away the letters and numbers printed on them. Second, every watch has a perfect round form and one cannot tell where the top of the watch is. Lastly, though every watch has three hands, they have a completely identical look and therefore one cannot tell which is the hour, the minute, or the second.1 This means that we cannot decide the time indicated by a watch uniquely; there can be a number of candidates. We have to consider different rotations of the watch.

Furthermore, since there are several possible interpretations of hands, we have also to consider all the permutations of hands. You are an information archaeologist invited to the project team and are asked to induce the most plausible time interval within which the disaster happened, from the set of excavated watches.

In what follows, we express a time modulo 12 hours. We write a time by the notation hh:mm:ss, where hh, mm, and ss stand for the hour (hh = 00, 01, 02, … , 11), the minute (mm = 00, 01, 02, . . . , 59), and the second (ss = 00, 01, 02, . . . , 59), respectively. The time starts from
00:00:00 and counts up every second 00:00:00, 00:00:01, 00:00:02, ・ ・ ・ , but it reverts to 00:00:00
every 12 hours.

The watches in Chronus Island obey the following conventions of modern analog watches.

A watch has three hands, i.e. the hour hand, the minute hand, and the second hand,though they look identical as mentioned above.

1It is a mystery how the people in Chronus Island were distinguishing the three hands. Some archaeologistsguess that the hands might be painted with different colors, but this is only a hypothesis, as the paint was lost by the heat.

Every hand ticks 6 degrees clockwise in a discrete manner. That is, no hand stays between ticks, and each hand returns to the same position every 60 ticks.

The second hand ticks every second.

The minute hand ticks every 60 seconds.

The hour hand ticks every 12 minutes.

At the time 00:00:00, all the three hands are located at the same position. Because people in Chronus Island were reasonably keen to keep their watches correct and pyroclastic flows spread over the island quite rapidly, it can be assumed that all the watches were stopped in a short interval of time. Therefore it is highly expected that the time the disaster happened is in the shortest time interval within which all the excavated watches have at least one candidate time.

You must calculate the shortest time interval and report it to the project team.

输入:

The input consists of multiple datasets, each of which is formatted as follows.
n

s1 t1 u1

s2 t2 u2

sn tn un

The first line contains a single integer n (2 ≤ n ≤ 10), representing the number of the watches. The three numbers si, ti, ui in each line are integers such that 0 ≤ si; ti; ui ≤ 59 and they specify the positions of the three hands by the number of ticks relative to an arbitrarily chosen position.

Note that the positions of the hands of a watch can be expressed in many different ways. For example, if a watch was stopped at the time 11:55:03, the positions of hands can be expressed differently by rotating the watch arbitrarily (e.g. 59 55 3, 0 56 4, 1 57 5, etc.) and as well by permuting the hour, minute, and second hands arbitrarily (e.g. 55 59 3, 55 3 59, 3 55 59, etc.).

The end of the input is indicated by a line containing a single zero.

输出:

The input consists of multiple datasets, each of which is formatted as follows.
n

s1 t1 u1

s2 t2 u2

sn tn un

The first line contains a single integer n (2 ≤ n ≤ 10), representing the number of the watches. The three numbers si, ti, ui in each line are integers such that 0 ≤ si; ti; ui ≤ 59 and they specify the positions of the three hands by the number of ticks relative to an arbitrarily chosen position.

Note that the positions of the hands of a watch can be expressed in many different ways. For example, if a watch was stopped at the time 11:55:03, the positions of hands can be expressed differently by rotating the watch arbitrarily (e.g. 59 55 3, 0 56 4, 1 57 5, etc.) and as well by permuting the hour, minute, and second hands arbitrarily (e.g. 55 59 3, 55 3 59, 3 55 59, etc.).

The end of the input is indicated by a line containing a single zero.

样例输入:

3
8 8 18
32 32 32
57 2 57
5
49 3 49
7 30 44
27 21 21
33 56 56
21 46 4
3
45 52 28
36 26 36
20 55 50
10
33 8 39
50 57 43
35 21 12
21 17 11
16 21 58
45 40 53
45 30 53
39 1 8
55 48 30
7 48 15
0

样例输出:

00:00:00 00:00:10
06:14:56 06:32:09
07:27:37 07:32:02
05:17:40 05:21:03

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int st[20][50000];
int a[20][5];
int s[20];
int ans,ans1,ans2;
void work(int h,int m,int s,int x)
{
    int i,j,k,l;
    if(!(m>=(h%5)*12&&m<(h%5+1)*12)) return;
    st[x][h/5*3600+m*60+s]=1;
}
int main()
{
    int n,i,j,k,l,m,q,w,e,r,t,num;
    while (scanf("%d",&n)!=EOF)
    {
        memset(st,0,sizeof(st));
        if (n==0) break;
        for (i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a[i][1],&a[i][2],&a[i][3]);
            for (j=1;j<=60;j++)
            {
                work(a[i][1],a[i][2],a[i][3],i);
                work(a[i][1],a[i][3],a[i][2],i);
                work(a[i][2],a[i][1],a[i][3],i);
                work(a[i][2],a[i][3],a[i][1],i);
                work(a[i][3],a[i][2],a[i][1],i);
                work(a[i][3],a[i][1],a[i][2],i);
                a[i][1]=(a[i][1]+1)%60;
                a[i][2]=(a[i][2]+1)%60;
                a[i][3]=(a[i][3]+1)%60;
            }
        }
        num=0;
        j=0;
        i=0;
        memset(s,0,sizeof(s));
        while (1)
        {
            for (j=1;j<=n;j++)
            {
                if (st[j][i]==1)
                {
                    if (s[j]==0) num++;
                    s[j]++;
                }
            }
            i++;
            if (num==n) break;
        }
        i--;j=0;  //由i+1开始加入
        int flag=0;
        while (1)
        {
            for (k=1;k<=n;k++)
            {
                if (st[k][j]==1)
                {
                    if (s[k]==1)
                    {
                        flag=1;
                        num--;
                    }
                    s[k]--;
                }
            }
            if (flag) break;
            j++;
        }
        for (k=1;k<=n;k++)
        {
            if (st[k][j]==1)
            {
                if (s[k]==0)
                {
                    num++;
                }
                s[k]++;
            }
        }
        // 由j开始删去
        ans=i-j+1;
        ans1=j;
        ans2=i;
        while (1)
        {
            while (1)
            {
                for (k=1;k<=n;k++)
                {
                    if (st[k][j]==1)
                    {
                        if (s[k]==1)
                        {
                            num--;
                        }
                        s[k]--;
                    }
                }
                j++;
                if (num<n) break;
            }
            if (i-j+2<ans)
            {
                ans=i-j+2;
                ans1=j-1;
                ans2=i;
            }
            while (1)
            {
                i++;
                if (i>45000)break;
                for (k=1;k<=n;k++)
                {
                    if (st[k][i]==1)
                    {
                        if (s[k]==0)
                        {
                            num++;
                        }
                        s[k]++;
                    }
                }
                if (num==n)break;
            }
            if (i>45000)break;
        }
        int h1,m1,s1,h2,m2,s2;
        h1=ans1/3600;
        m1=ans1-h1*3600;
        m1=m1/60;
        s1=ans1-h1*3600-m1*60;
        h2=ans2/3600;
        m2=ans2-h2*3600;
        m2=m2/60;
        s2=ans2-h2*3600-m2*60;
        printf("%02d:%02d:%02d %02d:%02d:%02d\n",h1,m1,s1,h2,m2,s2);
    }
    return 0;
}

  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮