Problem 1287 : Stopped Watches

Problem C: Stopped Watches
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1287

• 問題概要

ある島で火山が噴火して、人々全滅。
時計もそのときとまった。
その時計は文字盤もはげてしまってるし、どれが秒針か分針かとかがわからない。
どちらが上かもわからない。
任意の場所を基準に、そこからの円を６０分割したうちの何個目をさしているかあたえられる。
それは、それらの時計が示す時間が、回転させたり、どれをどの針とするかによって、
複数あることを示している。
噴火によってとまったはずなので、その時間差はとても小さいはずである。
時計が示す時間をすべて含む一番小さい範囲の、その範囲の最初の最後を求めよ。

• 解法

すべての時間の候補をあげて、すべての時計の候補を含む範囲をもとめる。
この問題の時計は、１２分ごとに短針も動くので、短針の位置から分針に矛盾がないか調べる必要がある。
時間にどの時計からの候補なのかのidを持たせる必要がある。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

class Time{
public:
  int h, m, s, id;
  bool valid(){
    int tmp = h%5;
    return (tmp * 12 <= m && (tmp+1) * 12 > m);
  }
  void next(){
    s++;
    m++;
    h++;
    s%=60;
    m%=60;
    h%=60;
  }
  void output(){
    printf("%02d:%02d:%02d", h/5, m, s);
  }
  bool operator < (const Time &t) const{
    if( h/5 != t.h/5)return h/5 < t.h/5;
    if( m != t.m)return m < t.m;
    if( s != t.s)return s < t.s;
    return false;
  }
};

int dif(Time t2, Time t1){
  int sum = 0;
  sum += t1.h /5 * 60 * 60;
  sum += t1.m * 60;
  sum += t1.s;
  sum -= t2.h  /5 * 60 * 60;
  sum -= t2.m * 60;
  sum -= t2.s;
  if(sum < 0){
    t1.output();
    t2.output();
  }
  return sum;
}

main(){
  
  int n;
  while(cin >> n){
    if(n == 0)break;
    vector<Time> v;
    rep(i, n){
      Time t;
      t.id = i;
      int num[3];
      rep(j, 3)cin >> num[j];
      sort(num, num + 3);
      do{
	t.h = num[0];
	t.m = num[1];
	t.s = num[2];
	rep(j, 60){
	  if(t.valid())v.pb(t);
	  t.next();
	}
      }while(next_permutation(num, num + 3));
    }
    sort(ALL(v));
    int mini = 100000000;
    Time ans[2];
    for(int i=0; i<v.size(); i++){
      bool used[n];
      rep(j, n)used[j] = false;
      used[v[i].id] = true;
      for(int j = i+1; j<v.size(); j++){
	used[v[j].id] = true;
	bool find = false;
	rep(k, n){
	  if(!used[k])find = true;
	}
	if(!find){
	  if(mini > dif(v[i], v[j])){
	    mini = dif(v[i], v[j]);
	    ans[0] = v[i];
	    ans[1] = v[j];
	  }
	  break;
	}
      }
    }
    ans[0].output();
    cout << ' ';
    ans[1].output();
    cout << endl;
  }
}

楽しかったー。時間っていろいろややこしくてつかれた。。。
でも、たのしかったー。