Posted on 2008-05-19 15:53
superman 阅读(414)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1190 C++ 00:00.48 28620K */
2 #include <iostream>
3
4 using namespace std;
5
6 enum { ADD = 1, DIV = 2, DUP = 3, MUL = 4, SUB = 5, maxStackSize = 11 };
7
8 inline int abs(int n)
9 {
10 return n > 0 ? n : -n;
11 }
12
13 template <class T>
14 class stack
15 {
16 public:
17 T x[maxStackSize]; char p;
18
19 stack() { p = -1; }
20 int size() { return p + 1;}
21 bool empty() { return p == -1; }
22 void push(const T & item) { x[++p] = item; }
23 void pop() { p--; }
24 void clear() { p = -1; }
25 T & top() { return x[p]; }
26
27 void operator = (const stack & st)
28 {
29 memcpy(x, st.x, sizeof(st.x));
30 p = st.p;
31 }
32 };
33
34 struct QUEUE
35 {
36 int last;
37 char cnt, op;
38 stack <short> st;
39 }queue[888888];
40
41 string opSeq;
42 int n, x[10], y[10];
43
44 void getPath(int i)
45 {
46 if(queue[i].last)
47 getPath(queue[i].last);
48 opSeq += queue[i].op;
49 }
50
51 bool checkOthers()
52 {
53 for(int i = 1; i < n; i++)
54 {
55 stack <short> st;
56 st.push(x[i]);
57 int a, b;
58 for(int k = 0; k < opSeq.size(); k++)
59 switch(opSeq[k])
60 {
61 case 1 : //ADD
62 a = st.top(); st.pop();
63 b = st.top(); st.pop();
64 if(abs(int(a) + int(b)) > 30000)
65 return false;
66 st.push(a + b);
67 break;
68 case 2 : //DIV
69 a = st.top(); st.pop();
70 b = st.top(); st.pop();
71 if(a == 0) return false;
72 st.push(b / a);
73 break;
74 case 3 : //DUP
75 st.push(st.top()); break;
76 case 4 : //MUL
77 a = st.top(); st.pop();
78 b = st.top(); st.pop();
79 if(abs(int(a) * int(b)) > 30000)
80 return false;
81 st.push(a * b);
82 break;
83 case 5 : //SUB
84 a = st.top(); st.pop();
85 b = st.top(); st.pop();
86 if(abs(int(b) - int(a)) > 30000)
87 return false;
88 st.push(b - a);
89 break;
90 }
91 if(st.top() != y[i])
92 return false;
93 }
94 return true;
95 }
96
97 int main()
98 {
99 int program = 0;
100 while((cin >> n) && n)
101 {
102
103 for(int i = 0; i < n; i++)
104 cin >> x[i];
105 for(int i = 0; i < n; i++)
106 cin >> y[i];
107
108 program++;
109 cout << "Program " << program << endl;
110
111 bool empty_sequence = true;
112 for(int i = 0; i < n; i++)
113 if(x[i] != y[i])
114 {
115 empty_sequence = false; break;
116 }
117 if(empty_sequence)
118 {
119 cout << "Empty sequence" << endl << endl; continue;
120 }
121
122 int front = -1, rear = 0;
123 int best = INT_MAX; string bestSeq(10, 255);
124 bool found = false;
125
126 queue[0].st.push(x[0]);
127 queue[0].last = 0;
128 queue[0].cnt = 0;
129 queue[0].op = 0;
130 while(front < rear)
131 {
132 front++;
133
134 if(queue[front].cnt > best)
135 continue;
136
137 stack <short> st = queue[front].st;
138
139 if(st.size() == 1 && st.top() == y[0])
140 {
141 opSeq.clear();
142 getPath(front);
143 if(checkOthers())
144 {
145 if(queue[front].cnt == best)
146 if(opSeq < bestSeq)
147 bestSeq = opSeq;
148 if(queue[front].cnt < best)
149 {
150 best = queue[front].cnt;
151 bestSeq = opSeq;
152 }
153 found = true;
154 }
155 }
156
157 int a, b;
158 if(queue[front].cnt < 10)
159 {
160 //ADD
161 if(st.size() > 1)
162 {
163 rear++;
164 queue[rear].st = st;
165 queue[rear].op = ADD;
166 queue[rear].cnt = queue[front].cnt + 1;
167 queue[rear].last = front;
168 a = queue[rear].st.top(); queue[rear].st.pop();
169 b = queue[rear].st.top(); queue[rear].st.pop();
170 queue[rear].st.push(a + b);
171 if(abs(int(a) + int(b)) > 30000)
172 rear--;
173 }
174
175 //DIV
176 if(st.size() > 1 && st.top() != 0)
177 {
178 rear++;
179 queue[rear].st = st;
180 queue[rear].op = DIV;
181 queue[rear].cnt = queue[front].cnt + 1;
182 queue[rear].last = front;
183 a = queue[rear].st.top(); queue[rear].st.pop();
184 b = queue[rear].st.top(); queue[rear].st.pop();
185 queue[rear].st.push(b / a);
186 }
187
188 //DUP
189 rear++;
190 queue[rear].st = st;
191 queue[rear].op = DUP;
192 queue[rear].cnt = queue[front].cnt + 1;
193 queue[rear].last = front;
194 queue[rear].st.push(st.top());
195
196 //MUL
197 if(st.size() > 1)
198 {
199 rear++;
200 queue[rear].st = st;
201 queue[rear].op = MUL;
202 queue[rear].cnt = queue[front].cnt + 1;
203 queue[rear].last = front;
204 a = queue[rear].st.top(); queue[rear].st.pop();
205 b = queue[rear].st.top(); queue[rear].st.pop();
206 queue[rear].st.push(a * b);
207 if(abs(int(a) * int(b)) > 30000)
208 rear--;
209 }
210
211 //SUB
212 if(st.size() > 1)
213 {
214 rear++;
215 queue[rear].st = st;
216 queue[rear].op = SUB;
217 queue[rear].cnt = queue[front].cnt + 1;
218 queue[rear].last = front;
219 a = queue[rear].st.top(); queue[rear].st.pop();
220 b = queue[rear].st.top(); queue[rear].st.pop();
221 queue[rear].st.push(b - a);
222 if(abs(int(b) - int(a)) > 30000)
223 rear--;
224 }
225 }
226 }
227
228 if(found == false)
229 cout << "Impossible" << endl;
230 else
231 for(int i = 0; i < bestSeq.size(); i++)
232 {
233 switch(bestSeq[i])
234 {
235 case 1 : cout << "ADD"; break;
236 case 2 : cout << "DIV"; break;
237 case 3 : cout << "DUP"; break;
238 case 4 : cout << "MUL"; break;
239 case 5 : cout << "SUB"; break;
240 }
241 cout << (i == bestSeq.size() - 1 ? '\n': ' ');
242 }
243 cout << endl;
244
245 for(int i = 0; i <= rear; i++)
246 queue[i].st.clear();
247 }
248
249 return 0;
250 }
251