Algoogle

Algorithm for Programming Contest

AOJ 1287 Stopped Watches

Category: AOJ Tag: brute-force, implementation

Stopped Watches

問題概要


どの針が秒, 分, 時を表しているか分からず, またどのメモリを基準にしているのかわからない3つの数がnセット与えられる.
n個の時刻をすべてカバーしうる最小の区間を求めよ.

解法


どう考えても読解が難しい.
全ての時計について針の種類と基準点を全て試して時刻を列挙する.
あとはソートして区間の始まりをすべて試せば良い.

コード


(1287.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
const int inf = 1e9;
typedef pair<int,int> pii;
int N, M, seq[16][4];
int a, b, d, cnt;
bool used[16];

void solve(){
    vector<pii> tims;
    rep(i,N){
        sort(seq[i], seq[i]+3);
        do{
            int s, m, h;
            rep(j, 60){
                s = (seq[i][0]-j+60)%60;
                m = (seq[i][1]-j+60)%60;
                h = (seq[i][2]-j+60)%60;
                if(h%5 != m/12) continue;
                h /= 5;
                tims.pb(pii(h*3600+m*60+s, i));
            }
        } while(next_permutation(seq[i],seq[i]+3));
    }
    M = tims.size();
    sort(all(tims));
    d = inf;
    rep(i,M){
        cnt = 1;
        memset(used, 0, sizeof(used));
        used[tims[i].second] = 1;
        int s = tims[i].first;
        rep(j,M-1){
            int id = tims[(i+j+1)%M].second, t = tims[(i+j+1)%M].first;
            if(!used[id]){
                used[id] = 1;
                cnt++;
            }
            if(cnt == N){
                int dif = (t-s+43200)%43200;
                if(dif < d) { a = s; b = t; d = dif;}
                break;
            }
        }
    }
    printf("%02d:%02d:%02d %02d:%02d:%02d\n", a/3600, a/60%60, a%60, b/3600, b/60%60, b%60);
}

bool input(){
    cin >> N;
    if(!N) return 0;
    rep(i,N) rep(j,3)
        cin >> seq[i][j];
    return 1;
}
signed main(){
    while(input()) solve();
    return 0;
}

Comments