注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zjushuiping

追求的只是心中的那一份宁静!

 
 
 

日志

 
 

POJ3414  

2010-08-17 10:53:56|  分类: ACM/ICPC |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Pots
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 4011
Accepted: 1689
Special Judge

Description

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

  1. FILL(i)        fill the pot i (1 ≤ i ≤ 2) from the tap;
  2. DROP(i)      empty the pot i to the drain;
  3. POUR(i,j)    pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3 5 4

Sample Output

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

Source

Northeastern Europe 2002, Western Subregion


#include <cstdlib>
#include <iostream>
#include <string.h>
using namespace std;
int a,b;
int A,B,C;
int tag=-1;
bool visited[101][101];
struct Node{
       int i;
       int father;
       int a,b;
       int num;
       };
Node queue[2000000];//队列
int front,rear;

int fill_1()
{if(a==A)
 return 0;
 else
 {a=A;
  if(visited[a][b])
  return 0;
  visited[a][b]=true;
 return 1;
 }
 
}

int fill_2()
{if(b==B)
 return 0;
 else
 {b=B;
 if(visited[a][b])
  return 0;
  visited[a][b]=true;
  return 1;
  }
}

int drop_1()
{if(a==0)
return 0;
else
{a=0;
 if(visited[a][b])
  return 0;
  visited[a][b]=true;
  return 1;
 }
}

int drop_2()
{if(b==0)
return 0;
else
{b=0;
if(visited[a][b])
  return 0;
  visited[a][b]=true;
  return 1;}
}

int pour_1to2()
{if(a==0)
 return 0;
 else
 {if(a<(B-b))
 {b+=a;a=0;}
 else
 {a-=(B-b);b=B;}
 if(visited[a][b])
  return 0;
  visited[a][b]=true;
 return 1;
 }
}

int pour_2to1()
{ if(b==0)
 return 0;
 else
 {
     if(b<(A-a))
     {a+=b;b=0;}
     else
     {b-=(A-a);a=A;}
     if(visited[a][b])
     return 0;
     visited[a][b]=true;
     return 1;
 }
}

int (*p[6])()={fill_1,fill_2,drop_1,drop_2,pour_1to2,pour_2to1};

    
      
int bfs()
{
   
    front=rear=0;
    int i,k,j;
   
    Node node;
    for(i=0;i<6;i++)
    {a=b=0;
     if(p[i]())
     {queue[rear].i=i;
     queue[rear].father=-1;
     queue[rear].a=a;
     queue[rear].b=b;
     queue[rear].num=1;
     rear++;
    
     if(a==C||b==C)
     {tag=rear-1;return 1;}
    }
    
    
    }
   
    while(front<rear)
    {node.i=queue[front].i;
     node.a=queue[front].a;
     node.b=queue[front].b;
     node.num=queue[front].num;
     for(i=0;i<6;i++)
     {a=node.a;b=node.b;
     if(p[i]())
     {queue[rear].i=i;
     queue[rear].father=front;
     queue[rear].a=a;
     queue[rear].b=b;
     queue[rear].num=node.num+1;
     rear++;
    
     if(a==C||b==C)
     {tag=rear-1;return node.num+1;}
     }
    
     }//for
     front++;
                    
                    
                    
    }//while
    return 0;
   
   
}
void output(int i)
{
    if( queue[i].father==-1)
     {switch(queue[i].i)
     {case 0:
           cout<<"FILL(1)"<<endl;
           break;
     case 1:cout<<"FILL(2)"<<endl;
           break;
     case 2:cout<<"DROP(1)"<<endl;
           break;
     case 3:cout<<"DROP(2)"<<endl;
           break;
     case 4:cout<<"POUR(1,2)"<<endl;
           break;
     case 5:cout<<"POUR(2,1)"<<endl;
           break;
     }
     return ;
    }
    output(queue[i].father);
    switch(queue[i].i)
     {case 0:
           cout<<"FILL(1)"<<endl;
           break;
     case 1:cout<<"FILL(2)"<<endl;
           break;
     case 2:cout<<"DROP(1)"<<endl;
           break;
     case 3:cout<<"DROP(2)"<<endl;
           break;
     case 4:cout<<"POUR(1,2)"<<endl;
           break;
     case 5:cout<<"POUR(2,1)"<<endl;
           break;
     }
}
   

     

int main(int argc, char *argv[])
{cin>>A>>B>>C;
int t;

 

 memset(visited,false,sizeof(visited));
 t=bfs();
 
 if(t==0)
 cout<<"impossible"<<endl;
 else
 {cout<<t<<endl;
  output(tag);
 }
 
    system("PAUSE");
    return EXIT_SUCCESS;
}

  评论这张
 
阅读(927)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017