D: Clock Breaking
問題
7セグデジタル時計がある。4桁とコロンの2セルの計30箇所のセグの表示がある。
この時計は壊れている可能性があり、各セグは
- 正しく動作する
- 常に0を表示する
- 常に1を表示する
のどれかである。
連続したn分の表示が与えられるので各セグについて、
- 正しく動作する
- 常に0を表示する
- 常に1を表示する
- 上の2つ以上に当てはまる
を判定して出力せよ。
与えられるn個の表示がどの時刻にも当てはまらないならそれを指摘せよ。
入出力例を見れば大体問題が理解できる。
解法
全ての時刻に対して、その表示が可能かどうか調べる。
可能ならば各セグはどの動作が可能か調べる。
24h * 60m * n の時刻をマッチさせる。
最初の時刻を一つ選んで、「正しい表示」と「壊れた表示」を比べる。
各セグについてn分見て、「正しい表示が0/1」の時に「壊れた表示が0/1」を出した、というのをメモする。
- 正0壊0 and 正0壊1 => 矛盾
- 正1壊0 and 正1壊1 => 矛盾
- 正0壊1 and 正1壊0 => 矛盾
これらの条件を通り抜けたらその時刻は正当である。
- 0を表示しなかった => 常に1の可能性あり
- 1を表示しなかった => 常に0の可能性あり
- 正0壊1も正1壊0もなかった => 正しく動作している可能性あり
この結果は同時に2つ満たすこともある。
ビット演算で解いたが時間的には配列でも間に合いそう。ただし、配列のほうが実装が楽かと言われると。
コード
#include<cstdio> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(s...) fprintf(stderr, s) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } // .22. // 0..5 // 0..5 // .33. // 1..6 // 1..6 // .44. pair<int, int> pos(int i, bool b) { if (i < 28) { int k = i % 7; static int y0[] = { 1, 4, 0, 3, 6, 1, 4 }; static int x0[] = { 0, 0, 1, 1, 1, 3, 3 }; static int y1[] = { 2, 5, 0, 3, 6, 2, 5 }; static int x1[] = { 0, 0, 2, 2, 2, 3, 3 }; static int d[] = { 0, 5, 12, 17 }; if (b) return make_pair(y1[k], x1[k] + d[i / 7]); else return make_pair(y0[k], x0[k] + d[i / 7]); } else if (i == 28) { return make_pair(2, 10); } else { return make_pair(4, 10); } } int N; char buf[7][99]; int D[111]; const int B = (1<<30) - 1; int Z[10] = { 1| 2| 4| 16|32|64, 32|64, 2| 4| 8|16|32 , 4| 8|16|32|64, 1| 8| 32|64, 1| 4| 8|16| 64, 1| 2| 4| 8|16| 64, 4| 32|64, 1| 2| 4| 8|16|32|64, 1| 4| 8|16|32|64, }; int M[24][60]; int mask(int h, int m) { int r = 0; r |= Z[h%10] << 7; h /= 10; if (h) r |= Z[h]; r |= Z[m%10] << 21; m /= 10; r |= Z[m] << 14; r |= 1 << 28; r |= 1 << 29; return r; } void set(int mask, char c='X') { REP (i, 7) REP (j, 21) buf[i][j] = '.'; REP (i, 30) if (mask & (1<<i)) REP (b, 2) { pair<int, int> p = pos(i, b); buf[p.first][p.second] = c; } } void show() { REP (i, 7) eprintf("%s\n", buf[i]); } int main() { // REP (j, 7) REP (i, 21) buf[j][i] = '.'; // REP (i, 30) { // REP (b, 2) { // pair<int, int> p = pos(i, b); // buf[p.first][p.second] = 'x'; // } // } // REP (j, 7) puts(buf[j]); scanf("%d", &N); REP (i, N) { REP (j, 7) scanf("%s", buf[j]); REP (k, 30) { pair<int, int> p = pos(k, 0); if (buf[p.first][p.second] == 'X') D[i] |= 1 << k; buf[p.first][p.second] = ' '; } } REP (h, 24) { REP (m, 60) { M[h][m] = mask(h, m); // set(M[h][m]); show(); eprintf("\n"); } } int cnt = 0; int ans[3] = {}; REP (h_, 24) REP (m_, 60) { int W[2][2] = {}; int h = h_, m = m_; REP (i, N) { int mk = M[h][m]; W[0][0] |= ~mk & ~D[i]; W[0][1] |= ~mk & D[i]; W[1][0] |= mk & ~D[i]; W[1][1] |= mk & D[i]; m++; if (m == 60) { m = 0; h++; if (h == 24) h = 0; } } if ((B & W[0][0] & W[0][1]) || (B & W[1][0] & W[1][1]) || (B & W[0][1] & W[1][0])) { } else { cnt++; ans[0] |= B & ~W[0][1] & ~W[1][1]; ans[1] |= B & ~W[0][0] & ~W[1][0]; ans[2] |= B & ~W[0][1] & ~W[1][0]; } } if (cnt == 0) { puts("impossible"); } else { REP (i, 7) REP (j, 21) buf[i][j] = '.'; REP (i, 30) REP (b, 2) { pair<int,int> p = pos(i, b); VI v; REP (k, 3) if (ans[k] & (1<<i)) v.push_back(k); if (v.size() == 1u) { buf[p.first][p.second] = "01W"[v[0]]; } else if (v.size() == 0u) { buf[p.first][p.second] = ' '; } else { buf[p.first][p.second] = '?'; } } REP (i, 7) puts(buf[i]); } return 0; }
日記
7セグの定数を大量に埋め込む必要がある正直面倒。
ICPCらしいような気もする。
