| Marbles in Three Baskets |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Total submit users: 15, Accepted users: 13 |
| Problem description |
| Each of three baskets contains a certain number of marbles. You may move from one basket into another basket as many marbles as are already there, thus doubling the quantity in the basket that received the marbles. You must find a sequence of moves that will yield the same number of marbles in the three baskets. Moreover, you must achieve the goal in the smallest possible number of moves. Your program must also recognize the case in which there is no such sequence of moves. |
| Input |
| Each line of the input file will contain data for one instance of the problem: three positive integers, with one blank space separating adjacent integers. The three integers represent the initial numbers of marbles in the three baskets. The sum of the three integers will be at most 60. |
| Output |
| The output will begin with the initial configuration from the input. Thereafter, on successive lines, the number of marbles in the respective baskets will be printed after each move, concluding with the line in which the three numbers are identical. As stated above, the goal must be achieved in the smallest possible number of moves. (The correct output is not unique, however. There may be different sequences of moves which achieve the goal correctly in the smallest possible number of steps.) If there is no sequence of moves to achieve the goal, only the initial configuration will be printed. Each integer in the output will be right-justified in a field of width 4. Each instance of the problem will be concluded by a line of 12 equal signs. |
| Sample Input |
6 7 11 15 18 3 5 6 7 |
| Sample Output |
6 7 11 6 14 4 12 8 4 8 8 8 ============ 15 18 3 12 18 6 12 12 12 ============ 5 6 7 ============ |
//// 题目思路很清楚，每个状态至多产生三个子状态，就是一般的广搜题，我用了STL速度很慢，勉强AC了，呵呵。简单说下： 用 set 检测状态是否重复出现，用 deque 存储待扩展 状态，用 stack 输出结果。STL用起来容易，但速度不是很好。
#include <iostream>
#include <deque>
#include <iomanip>
#include <stack>
#include <set>
using namespace std;
const int MAX = 2000;
class NODE{
public:
int a,b,c,i,f; // a,b,c 表示一个状态, i 表示当前节点的下标，f 父节点编号
NODE& operator=(const NODE& n){
a=n.a; b=n.b; c=n.c; i=n.i; f=n.f;
return *this;
}
void order(){ // 按 a,b ,c 升序排列以存入 set 中
if(a > b) swap(a,b);
if(b > c) swap(b,c);
if(a > b) swap(a,b);
}
// 下面是新状态的获取方法
void change12(NODE& tp,int& n)const{
tp.a=a*2; tp.b=b-a;
tp.c=c; tp.f=i;
tp.i=n++;
}
void change21(NODE& tp,int& n)const{
tp.a=a-b; tp.b=b*2;
tp.c=c; tp.f=i;
tp.i=n++;
}
void change23(NODE& tp,int& n)const{
tp.a=a; tp.b=b*2;
tp.c=c-b; tp.f=i;
tp.i=n++;
}
void change32(NODE& tp,int& n)const{
tp.a=a; tp.b=b-c;
tp.c=c*2; tp.f=i;
tp.i=n++;
}
void change13(NODE& tp,int& n)const{
tp.a=a*2; tp.b=b;
tp.c=c-a; tp.f=i;
tp.i=n++;
}
void change31(NODE& tp,int& n)const{
tp.a=a-c; tp.b=b;
tp.c=c*2; tp.f=i;
tp.i=n++;
}
};
class myCmp{ // set 排序的函数对象
public:
bool operator()(const NODE& a, const NODE& b){
return ( a.a<b.a || (a.a==b.a && a.b<b.b) ||
(a.a==b.a && a.b==b.b && a.c<b.c) );
}
};
bool isInclude(set<NODE,myCmp>& st, const NODE& tps){
NODE tp; // 检查 tps 在 set 中是否存在
tp = tps;
tp.order();
if(st.find(tp) == st.end()){
st.insert(tp);
return false;
}
return true;
}
NODE vt[MAX];
int main(){
deque<NODE> dq;
set<NODE,myCmp> st;
NODE tp,tps;
cout.setf(ios::right);
for(; cin>>tp.a>>tp.b>>tp.c; ){
if((tp.a+tp.b+tp.c)%3){
cout<<setw(4)<<tp.a<<setw(4)<<tp.b<<setw(4)<<tp.c<<endl;
cout<<"============"<<endl;
continue;
}
int vti=1;
tp.f = tp.i = 0;
tps = vt[0] = tp;
dq.push_back(tp);
tp.order();
st.insert(tp);
while(!dq.empty()){
tp = dq.front();
dq.pop_front();
if(tp.a > tp.b)
tp.change21(tps,vti);
else if(tp.a < tp.b)
tp.change12(tps,vti);
if(tp.a!=tp.b && !isInclude(st,tps)){
dq.push_back(tps);
vt[tps.i] = tps;
}
if(tps.a==tps.b && tps.a==tps.c)
break;
if(tp.a > tp.c)
tp.change31(tps,vti);
else if(tp.a < tp.c)
tp.change13(tps,vti);
if(tp.a!=tp.c && !isInclude(st,tps)){
dq.push_back(tps);
vt[tps.i] = tps;
}
if(tps.a==tps.b && tps.a==tps.c)
break;
if(tp.b > tp.c)
tp.change32(tps,vti);
else if(tp.b < tp.c)
tp.change23(tps,vti);
if(tp.b!=tp.c && !isInclude(st,tps)){
dq.push_back(tps);
vt[tps.i] = tps;
}
if(tps.a==tps.b && tps.a==tps.c)
break;
}
if(dq.empty())
cout<<setw(4)<<vt[0].a<<setw(4)<<vt[0].b<<setw(4)<<vt[0].c<<endl;
else{
stack<int> stk;
int j;
for(j=tps.i; j>0; j=vt[j].f)
stk.push(j);
stk.push(0);
for(; !stk.empty(); ){
j = stk.top();
stk.pop();
cout<<setw(4)<<vt[j].a<<setw(4)<<vt[j].b<<setw(4)<<vt[j].c<<endl;
}
}
cout<<"============"<<endl;
st.clear();
dq.clear();
}
return 0;
}
评论