added working NWERC11C
[the-user-spoj:the-user-spoj.git] / SCRAPER.cpp
1 /*
2  * Max-Height: F
3  * Two elevators: (X₀, Y₀) and (X₁, Y₁)
4  * WLOG: X₀ ≤ X₁
5  * d := X₁ - X₀
6  * Y₀·f ≡ d (Y₁)
7  * 
8  * a·Y₀ + b·Y₁ = gcd(Y₀, Y₁) = g
9  * Unless g|d: f does not exist
10  * Y₀/g·a ≡ 1 (Y₁)
11  * Y₀/g·a·d ≡ d
12  * f ≡ a·d/g
13  * 
14  * Result: X₁ ≤ X₀+Y₀·f+n·lcm(Y₀,Y₁) < F (X₁ ≤ F-1 - ((F-1 - (X₀+Y₀·f)) % lcm(Y₀,Y₁)))
15  */
16
17
18 #include <cstdio>
19 #include <cstdlib>
20 #include <stdint.h>
21 #include <cstring>
22 #include <string>
23 #include <iostream>
24 #include <unistd.h>
25 #include <cassert>
26 #include <sys/time.h>
27 #include <stack>
28 #include <vector>
29 #include <set>
30 #include <list>
31 #include <ctime>
32 #include <tr1/unordered_map>
33 using namespace std;
34 using namespace tr1;
35
36 namespace
37 {
38
39 typedef unsigned long long ull;
40 typedef int ll; // once it did not work with 32-bit ints, but now it works
41
42 inline FILE& operator>>(FILE& f, char*& d)
43 {
44     int s = 20;
45     d = (char*)malloc(s);
46     int chr;
47     int i = 0;
48     do
49     {
50         chr = fgetc(&f);
51         if(chr == EOF)
52             goto OPERATOR_RSHIFT_FILE_CHAR_PTR_end;
53     }
54     while(chr == '\n' || chr == '\r' || chr == '\t' || chr == ' ');
55     do
56     {
57         if(i == s)
58         {
59             s *= 2;
60             d = (char*)realloc(d, s);
61         }
62         d[i] = chr;
63         chr = fgetc(&f);
64         ++i;
65     }
66     while(chr != EOF && chr != '\n' && chr != '\r' && chr != '\t' && chr != ' ');
67     OPERATOR_RSHIFT_FILE_CHAR_PTR_end:;
68     d = (char*)realloc(d, i+1);
69     d[i] = '\0';
70     return f;
71 }
72 inline FILE& operator>>(FILE& f, char& chr)
73 {
74     int x;
75     do
76     {
77         x = fgetc(&f);
78         if(x == EOF)
79         {
80             chr = '\0';
81             return f;
82         }
83     }
84     while(x == '\n' || x == '\r' || x == '\t' || x == ' ');
85     chr = x;
86     return f;
87 }
88 inline FILE& operator>>(FILE& f, int& x)
89 {
90     char *d;
91     f >> d;
92     x = atoi(d);
93     free(d);
94     return f;
95 }
96 inline FILE& operator>>(FILE& f, ull& x)
97 {
98     fscanf(&f, "%llu", &x);
99     return f;
100 }
101 inline FILE& operator>>(FILE& f, double x)
102 {
103     char *d;
104     f >> d;
105     x = atof(d);
106     free(d);
107     return f;
108 }
109 inline FILE& operator>>(FILE& f, long double& x)
110 {
111     fscanf(&f, "%LE", &x);
112     return f;
113 }
114 inline FILE& operator>>(FILE& f, string& str)
115 {
116     char *d;
117     f >> d;
118     str.~string();
119     new (&str) string(d);
120     free(d);
121     return f;
122 }
123 inline FILE& operator<<(FILE& f, const char *str)
124 {
125     fputs(str, &f);
126     return f;
127 }
128 inline FILE& operator<<(FILE& f, int x)
129 {
130     fprintf(&f, "%d", x);
131     return f;
132 }
133 inline FILE& operator<<(FILE& f, ull x)
134 {
135     fprintf(&f, "%llu", x);
136     return f;
137 }
138 inline FILE& operator<<(FILE& f, long long x)
139 {
140     fprintf(&f, "%lld", x);
141     return f;
142 }
143 inline FILE& operator<<(FILE& f, double x)
144 {
145     fprintf(&f, "%E", x);
146     return f;
147 }
148 inline FILE& operator<<(FILE& f, long double x)
149 {
150     fprintf(&f, "%LE", x);
151     return f;
152 }
153 inline FILE& operator<<(FILE& f, const string& str)
154 {
155     f << str.c_str();
156     return f;
157 }
158 inline FILE& operator<<(FILE& f, char c)
159 {
160     fputc(c, &f);
161     return f;
162 }
163 struct _endofline
164 {
165 } eol;
166 struct _flush
167 {
168 } clearbuff;
169 inline FILE& operator<<(FILE& f, const __typeof__(eol)&)
170 {
171     fputc('\n', &f);
172     fflush(&f);
173     return f;
174 }
175 inline FILE& operator<<(FILE& f, const __typeof__(clearbuff)&)
176 {
177     fflush(&f);
178     return f;
179 }
180
181 FILE& lin(*stdin);  // low-level-in
182 FILE& lout(*stdout);    // low-level-out
183 FILE& lerr(*stderr);    // low-level-err
184
185 typedef pair<ll,ll> PII;
186 typedef pair<ll,PII > PIII;
187
188 template<typename T>
189 inline T pred(T t)
190 {
191     --t;
192     return t;
193 }
194 template<typename T>
195 inline T succ(T t)
196 {
197     ++t;
198     return t;
199 }
200
201 }
202
203 inline ll MOD(ll x, ll y)
204 {
205     ll m = x % y;
206     if(m < 0)
207         return y + m;
208     return m;
209 }
210
211 unordered_map<ll, unordered_map<ll, PIII> > eeavalue;
212
213 PIII eea(ll y0, ll y1)
214 {
215     if(eeavalue[y0].count(y1))
216         return eeavalue[y0][y1];
217     if(y1 == 1)
218         return eeavalue[y0][y1] = make_pair(1, make_pair(0, 1));
219     if(y0 == 1)
220         return eeavalue[y0][y1] = make_pair(1, make_pair(1, 0));
221     if(y0 == y1)
222         return eeavalue[y0][y1] = make_pair(y0, make_pair(1, 0));
223     if(y1 == 0)
224         return eeavalue[y0][y1] = make_pair(y0, make_pair(1, 0));
225     PIII x = eea(y1, y0 % y1);
226     return eeavalue[y0][y1] = make_pair(x.first, make_pair(x.second.second, x.second.first - (y0/y1) * x.second.second));
227 }
228
229 bool isConnected(ll F, ll x0, ll y0, ll x1, ll y1)
230 {
231     if(x0 > x1)
232         return isConnected(F, x1, y1, x0, y0);
233 #ifdef CONN_DEBUG
234     lerr << "F: " << F << " x0: " << x0 << " y0: " << y0 << " x1: " << x1 << " y1: " << y1 << eol;
235 #endif
236     ll d = x1 - x0;
237 #ifdef CONN_DEBUG
238     lerr << "d: " << d << eol;
239 #endif
240     PIII eeares = eea(y0, y1);
241     ll a = eeares.second.first, b = eeares.second.second, g = eeares.first;
242 #ifdef CONN_DEBUG
243     lerr << "a: " << a << " b: " << b << eol << "g: " << g << eol;
244 #endif
245     if(d % g != 0)
246     {
247 #ifdef CONN_DEBUG
248         lerr << "Not divisible: " << a*d << " (" << g << ")" << eol;
249 #endif
250         return false;
251     }
252     ll f = a*d/g;
253 #ifdef CONN_DEBUG
254     lerr << "f: " << f << eol;
255     lerr << (x0 + y0 * f) << eol;
256     lerr << "Final check: " << F-1 - MOD((F-1 - (x0 + y0 * f)), (y0 / g * y1)) << eol;
257 #endif
258     ll upper = F-1 - MOD((F-1 - (x0 + y0 * f)), (y0 / g * y1));
259     return upper >= x1;
260 }
261
262 bool visited[100];
263 int connected[100][100];
264 int x[100], y[100];
265
266
267 int main()
268 {
269 #ifdef RAND_CHECK
270     srand(143191);
271     for(int i = 0; i != 1000000; ++i)
272     {
273         int F = rand() % 100 + 1;
274         int x0 = rand() % (F), x1 = rand() % (F);
275         int y0 = rand() % (F/3+1)+1, y1 = rand() % (F/3+1)+1;
276         bool r = isConnected(F, x0, y0, x1, y1);
277         bool rr = false;
278         int s = x0, t = x1;
279         while(s < F && t < F)
280         {
281             if(s == t)
282             {
283                 rr = true;
284                 break;
285             }
286             if(s < t)
287                 s += y0;
288             else
289                 t += y1;
290         }
291         if(r != rr)
292         {
293             lerr << "Wrong result for: " << F << ": " << x0 << " " << y0 << ", " << x1 << " " << y1 << " (" << s << ")" << eol;
294         }
295     }
296 #endif
297
298 #ifdef TEST_INPUT
299     int F, x0, y0, x1, y1;
300     lin >> F >> x0 >> y0 >> x1 >> y1;
301     lout << isConnected(F, x0, y0, x1, y1) << eol;
302 #endif
303     int t;
304     scanf("%d", &t);
305     for(int _i = 0; _i != t; ++_i)
306     {
307         int F, E, A, B;
308         scanf("%d %d %d %d", &F, &E, &A, &B);
309         for(int i = 0; i != E; ++i)
310             scanf("%d %d", y+i, x+i);
311         if(A == B)
312             goto success;
313         {
314             memset(visited, 0, 100);
315             memset(connected, 0, 100*100*sizeof(int));
316             stack<int> search;
317             for(int i = 0; i != E; ++i)
318                 if(x[i] <= A && (A - x[i]) % y[i] == 0)
319                     search.push(i);
320             while(!search.empty())
321             {
322                 int c = search.top();
323                 search.pop();
324                 if(x[c] <= B && (B - x[c]) % y[c] == 0)
325                     goto success;
326                 visited[c] = true;
327                 for(int i = 0; i != E; ++i)
328                 {
329                     if(!visited[i])
330                     {
331                         bool conn;
332                         if(connected[c][i] == 1)
333                             conn = true;
334                         else if(connected[c][i] == -1)
335                             conn = false;
336                         else
337                         {
338                             conn = isConnected(F, x[c], y[c], x[i], y[i]);
339                             if(conn)
340                                 connected[c][i] = connected[i][c] = 1;
341                             else
342                                 connected[c][i] = connected[i][c] = -1;
343                         }
344                         if(conn)
345                             search.push(i);
346                     }
347                 }
348             }
349         }
350         puts("The furniture cannot be moved.\n");
351         continue;
352         success:
353         puts("It is possible to move the furniture.\n");
354     }
355 }
356