POJ 1508 - Skyscraper Floors

http://poj.org/problem?id=1508

概要

0 階から F-1 階まである建物に E 個のエレベーターがある．

i 番目のエレベーターは Y[i] より上の階に，Y[i] から X[i] 間隔の階のみに止まることができる． 例えば X[i] = 3, Y[i] = 7 ならば，止まることができる階は 7, 10, 13, 16, ... である．

A 階から B 階までエレベーターのみを使って移動できるかどうかを答える．

制約

解法

i 番目のエレベーターから j 番目のエレベーターに乗り換えることができる，つまり同じ階に止まることがあるかどうかがわかれば， Union-Find でそれらをマージした後，A 階に止まるエレベーターと B 階に止まるエレベーターが同じ集合に含まれているかどうかで判定できる．

(X, Y) = (x0, y0) のエレベーターと (X, Y) = (x1, y1) のエレベーターが同じ階に止まるかどうかは，

a*x0 + y0 =  b*x1 + y1

を満たす非負整数 (a, b) が存在し，かつ a*x0 + y0 < F かどうかに等しい． このような (a, b) は拡張ユークリッド互除法を利用することで求めることができる．

拡張ユークリッド互除法は

a*x0 + b*x1 = gcd(x0, x1)

を満たす (a, b) を求めるアルゴリズム．

y0 - y1 が gcd(x0, x1) で割り切れないときに限り，エレベーターが同じ階に止まることがない． y0 - y1 が gcd(x0, x1) で割り切れるとき，上の拡張ユークリッド互除法の式を少し変形することで，エレベーターの式にもっていくことができる．

コーナーケースとして，A == B のときはどんなエレベーターがきても「可能」と答えることに注意．

  1 #include <cstdio>
  2 #include <vector>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 struct DisjointSet/*{{{*/
  7 {
  8   vector<int> parent;
  9 
 10   int root(int x)
 11   {
 12     if (parent[x] < 0) {
 13       return x;
 14     } else {
 15       parent[x] = root(parent[x]);
 16       return parent[x];
 17     }
 18   }
 19 
 20   explicit DisjointSet(int n) : parent(n, -1) {}
 21 
 22   bool unite(int x, int y)
 23   {
 24     const int a = root(x);
 25     const int b = root(y);
 26     if (a != b) {
 27       if (parent[a] < parent[b]) {
 28         parent[a] += parent[b];
 29         parent[b] = a;
 30       } else {
 31         parent[b] += parent[a];
 32         parent[a] = b;
 33       }
 34       return true;
 35     } else {
 36       return false;
 37     }
 38   }
 39 
 40   bool find(int x, int y) { return root(x) == root(y); }
 41   int size(int x) { return -parent[root(x)]; }
 42 };/*}}}*/
 43 
 44 int extgcd(int x, int y, int& a, int& b)
 45 {
 46   if (x < y) {
 47     return extgcd(y, x, b, a);
 48   }
 49   a = 1;
 50   int aa = 0;
 51   b = 0;
 52   int bb = 1;
 53   while (y > 0) {
 54     const int r = x % y;
 55     const int q = x / y;
 56     x = y; y = r;
 57     const int t = a - q*aa;
 58     const int u = b - q*bb;
 59     a = aa;  aa = t;
 60     b = bb;  bb = u;
 61   }
 62   return x;
 63 }
 64 
 65 int solve(int x0, int y0, int x1, int y1)
 66 {
 67   int a, b;
 68   const int g = extgcd(x0, x1, a, b);
 69   if (a < 0) {
 70     swap(a, b);
 71     swap(x0, x1);
 72     swap(y0, y1);
 73   }
 74   int y = y1 - y0;
 75   if (y % g != 0) {
 76     return -1;
 77   }
 78   if (y < 0) {
 79     y = -y;
 80     a -= x1;
 81     b += x0;
 82     a = -a;
 83   } else if (y > 0) {
 84     b = -b;
 85   }
 86   const long long q = y / g;
 87   const long long s = a*q;
 88   const long long t = b*q;
 89   const long long z = min(s/x1, t/x0);
 90   return x0 * (s-x1*z);
 91 }
 92 
 93 int main()
 94 {
 95   int T;
 96   scanf("%d", &T);
 97   while (T-- > 0) {
 98     long long F;
 99     int E, A, B;
100     scanf("%lld %d %d %d", &F, &E, &A, &B);
101     static pair<int,int> es[100];
102     for (int i = 0; i < E; i++) {
103       scanf("%d %d", &es[i].first, &es[i].second);
104     }
105 
106     if (A == B) {
107       puts("It is possible to move the furniture.");
108       continue;
109     }
110 
111     const int start = E, goal = E+1;
112     DisjointSet s(E+2);
113     for (int i = 0; i < E; i++) {
114       if (A >= es[i].second && (A-es[i].second) % es[i].first == 0) {
115         s.unite(start, i);
116       }
117       if (B >= es[i].second && (B-es[i].second) % es[i].first == 0) {
118         s.unite(i, goal);
119       }
120     }
121     for (int i = 0; i < E; i++) {
122       for (int j = i+1; j < E; j++) {
123         const long long f = solve(es[i].first, es[i].second, es[j].first, es[j].second);
124         if (0 <= f && f <= F) {
125           s.unite(i, j);
126         }
127       }
128     }
129     if (s.find(start, goal)) {
130       puts("It is possible to move the furniture.");
131     } else {
132       puts("The furniture cannot be moved.");
133     }
134   }
135   return 0;
136 }
poj/1508.cc