emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
1000分模拟题CraneWork

Problem Statement

     There are three stacks of crates - two of them outside of the warehouse, and one inside the warehouse. We have a crane that can move one crate at a time, and we would like to move all of the crates to the stack inside the warehouse. A heavier crate can never be stacked on top of a lighter crate, and all three initial stacks obey that rule.

Create a class CraneWork that contains a method moves that is given int[]s stack1, stack2, and warehouse containing the initial three stacks, and returns the minimum number of moves required to move all the crates into the warehouse stack. The elements of stack1, stack2, and warehouse represent the weights of the crates and are given from top to bottom (and thus in non-decreasing order of weight).

Definition

    
Class: CraneWork
Method: moves
Parameters: int[], int[], int[]
Returns: int
Method signature: int moves(int[] stack1, int[] stack2, int[] warehouse)
(be sure your method is public)
    

Constraints

- stack1, stack2, and warehouse will each contain between 0 and 20 elements, inclusive.
- The total number of elements in the three stacks will be between 1 and 20, inclusive.
- Each element in the three stacks will be between 1 and 200, inclusive.
- stack1, stack2, and warehouse will each be in non-decreasing order.

Examples

0)
     
{3,50}
 
{}
 
{1,2,50,50,50}
 
Returns: 12
Move 3 to stack2, 1 to stack1, 2 to stack2, 1 to stack2, 50 to warehouse, 1 to warehouse, 2 to stack1, 1 to stack1, 3 to warehouse, 1 to stack2, 2 to warehouse, 1 to warehouse.
1)
     
{50}
 
{50}
 
{10,20,30}
 
Returns: 17
Start by moving 50 from stack2 to stack1. It then takes 7 moves to transfer the 10,20,30 to stack 2, 2 moves to transfer the 2 50's to the warehouse, and 7 more to transfer the 10,20,30 to the warehouse.
2)
     
{}
 
{}
 
{2,5,6,7}
 
Returns: 0
All the crates are already in the warehouse.
3)
     
{1,2,3}
 
{}
 
{}
 
Returns: 7
Move 1 from stack1 to warehouse, 2 from stack1 to stack2, 1 from warehouse to stack2, 3 from stack1 to warehouse, 1 from stack2 to stack1, 2 from stack2 to warehouse, 1 from stack1 to warehouse.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted on 2006-09-05 10:21 emu 阅读(6592) 评论(7)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# re: 1000分模拟题CraneWork 2007-06-09 11:02 匿名
#include <iostream>
using namespace std;


class CStack{
public:
CStack(){
memset(data,0,100*sizeof(int));
index=0;
}
virtual~CStack(){}
int Pop() { sum++; return data[index--];}
void Push(int D) { data[++index]=D; }
int Find(int D,int I)
{
for(int i=I;i<=index;i++)
if(data[i]<D)
return i;
return index+1;
}
int Show(int I)
{
if(index==0) return 0;
if(I>index||I<1)
return 0;
return data[I];
}
bool Istop(int T)
{
if(T==index) return true;
else return false;
}
void Show()
{
if(index==0)
{
cout<<"空"<<endl;
return;
}

for(int i=index;i>0;i--)
cout<<data[i]<<" ";
cout<<endl;
}
public:
static int sum;
private:
int data[100];
int index;
};
int CStack::sum=0;

CStack stack[3];


void show()
{
cout<<"////////////////"<<endl;
for(int i=0;i<3;i++)
stack[i].Show();
cout<<"////////////////"<<endl;
}
void CraneWork(int a,int k1,int b,int k2,int c,int k3)
{
int x=stack[a].Show(k1);
int y=stack[b].Show(k2);
int z=stack[c].Show(k3);
if(x==0&&y==0) return;

if(z>=x&&z>=y)
{
if(x>=y)
{
int k=stack[c].Find(x,k3);
CraneWork(a,k1+1,c,k,b,k2);
stack[c].Push(stack[a].Pop());
show();
CraneWork(b,k2,a,k1,c,k+1);
}
else
{
int k=stack[c].Find(y,k3);
CraneWork(b,k2+1,c,k,a,k1);
stack[c].Push(stack[b].Pop());
CraneWork(a,k1,b,k2,c,k+1);
}
}
if(x>z&&x>=y)
{
if(x==y)
{
if(stack[a].Istop(k1)&&stack[b].Istop(k2))
{
stack[a].Push(stack[b].Pop());
CraneWork(a,k1+2,c,k3,b,k2);
stack[c].Push(stack[a].Pop());
stack[c].Push(stack[a].Pop());
CraneWork(a,k1,b,k2,c,k3+2);
return;
}
}
CraneWork(a,k1+1,c,k3,b,k2);
stack[c].Push(stack[a].Pop());
show();
CraneWork(a,k1,b,k2,c,k3+1);

}
if(y>z&&y>x)
{
CraneWork(b,k2+1,c,k3,a,k1);
stack[c].Push(stack[b].Pop());
show();
CraneWork(a,k1,b,k2,c,k3+1);
}
}



int _tmain(int argc, _TCHAR* argv[])
{
/*stack[0].Push(50);
stack[0].Push(3);
stack[2].Push(50);
stack[2].Push(50);
stack[2].Push(50);
stack[2].Push(2);
stack[2].Push(1);*/
/*stack[0].Push(3);
stack[0].Push(2);
stack[0].Push(1);*/
stack[0].Push(50);
stack[1].Push(50);
stack[2].Push(30);
stack[2].Push(20);
stack[2].Push(10);


show();
CraneWork(0,1,1,1,2,1);
show();
cout<<"次数为:"<<CStack::sum<<endl;
return 0;
}
  回复  更多评论
  

# re: 1000分模拟题CraneWork [未登录] 2007-08-06 18:52 zero
very easy!  回复  更多评论
  

# re: 1000分模拟题CraneWork [未登录] 2007-11-11 22:23 y
g sdfg  回复  更多评论
  

# re: 1000分模拟题CraneWork 2008-09-19 09:26 热
比赛题目都是英文么  回复  更多评论
  

# re: 1000分模拟题CraneWork 2008-09-22 11:21 hejian
这是一道汉诺塔的变种题，不知使用进位迭代的方式还有没有效，有时间可以试一下。  回复  更多评论
  

# re: 1000分模拟题CraneWork 2008-11-27 17:59 诚人
一直对google技术佩服！我也要研究一番。  回复  更多评论
  

# re: 1000分模拟题CraneWork [未登录] 2010-10-03 23:54 无名
鉴定完毕，此程序有问题。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: