1 /*
2 * File: F.cpp
3 * Author: GongZhi
4 *
5 * Created on 2009年7月27日, 下午12:19
6 */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <stdio.h>
11 /*
12 *
13 */
14 const int MAX = 6100000;
15 int uset[MAX];
16 int n;
17 int root(int k) {
18 int t = k;
19 while (uset[t] != t)
20 t = uset[t];
21 while (uset[k] != k) {
22 int p = uset[k];
23 uset[k] = t;
24 k = p;
25 }
26 return uset[k];
27 }
28
29 int init(int n) {
30 for (int i = 0; i <= n; ++i)
31 uset[i] = i;
32 return 0;
33 }
34
35 int query(int src, int dst, int ss, int ds, int nnn) {
36 int ans=0;
37 for (int i = 0; src<=n && dst<=n && i < nnn; ++i) {
38 int a = root(src);
39 int b = root(dst);
40 if (a == b)
41 ++ans;
42 src += ss;
43 dst += ds;
44 }
45 printf("%d - %d\n", ans, nnn - ans);
46 return 0;
47 }
48
49 int join(int src, int dst, int ss, int ds, int nnn) {
50 int ans = 0;
51 for (int i = 0; src<=n && dst<=n && i < nnn; ++i) {
52 int a = src;//root(src);
53 int b = root(dst);
54 uset[b] = a;
55 src += ss;
56 dst += ds;
57 }
58 return 0;
59 }
60
61 int get(char* s)
62 {
63 int i=0;
64 char c;
65 while(true)
66 {
67 c=getchar();
68 if(c==-1)return -1;
69 if(c=='\n')break;
70 s[i]=c;
71 ++i;
72 }
73 s[i]=0;
74 return 1;
75 }
76
77 int main(int argc, char** argv) {
78 char line[1024];
79 //freopen("in.txt","r",stdin);
80 while (gets(line)!=NULL) {
81 int src = 0, dst = 0;
82 int nnn = 1, ss = 0, ds = 1;
83 char tmp[100];
84 if (line[0] == 'D' || line[0] == 'd') {
85 sscanf(line, "%s%d", tmp, &n);
86 init(n);
87 } else {
88 int i;
89 sscanf(line,"%s%d%d%d%d%d",tmp,&src,&dst,&nnn,&ds,&ss);
90 if (line[0] == 'Q' || line[0] == 'q')
91 query(src, dst, ss, ds, nnn);
92 else
93 join(src, dst, ss, ds, nnn);
94 }
95 }
96 return (EXIT_SUCCESS);
97 }
98