非常可乐

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3570 Accepted Submission(s): 1469

Problem Description

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

 

 

Input

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。

 

 

Output

如果能平分的话请输出最少要倒的次数，否则输出"NO"。

 

 

Sample Input

7 4 3 4 1 3 0 0 0

 

 

Sample Output

NO 3

 

 

 

 

import java.io.*;import java.util.*;class Node{	int max[];	int v[];	int count;	Node(){		max=new int[3];		v=new int[3];		count=0;	}	public Node getNode(){		Node node=new Node();		for(int i=0;i<3;i++){			node.max[i]=max[i];			node.v[i]=v[i];		}		node.count=count;		return node;	}}/* * @author denghuilong  *   * 2013-8-13下午4:14:49 **/public class Main {	public boolean boo[]=new boolean[100*100*100+100*100+100];	public Queue
    
      list=new LinkedList
     
      ();	public static void main(String[] args) {		new Main().work();	}	public void work(){		Scanner sc=new Scanner(new BufferedInputStream(System.in));		while(sc.hasNextInt()){			Arrays.fill(boo, false);			list.clear();			int s=sc.nextInt();			int m=sc.nextInt();			int n=sc.nextInt();			if(s==0&&m==0&&n==0)				System.exit(0);			Node node=new Node();			node.max[0]=s;			node.max[1]=m;			node.max[2]=n;			node.v[0]=node.max[0];			node.count=0;			list.add(node);			BFS();		}	}	public  void BFS(){		while(list.size()!=0){			Node node=list.poll();			for(int i=0;i<3;i++){				for(int j=0;j<3;j++){					if(i==j||node.max[j]==node.v[j])						continue;					Node t=node.getNode();					t.count++;					if(t.v[i]>=(t.max[j]-t.v[j])){						t.v[i]=t.v[i]-(t.max[j]-t.v[j]);						t.v[j]=t.max[j];					}					else{						t.v[j]=t.v[i]+t.v[j];						t.v[i]=0;					}					int step=getStep(t);					if(!boo[step]){						if(check(t)){							System.out.println(t.count);							return;						}						boo[step]=true;						list.add(t);					}				}			}		}		System.out.println("NO");	}	public  int getStep(Node node){		return node.v[0]*100*100+node.v[1]*100+node.v[2];	}	public boolean check(Node node){		int s=node.v[0];		int m=node.v[1];		int n=node.v[2];		if((s==m&&n==0)||(s==n&&m==0)||(s==0&&n==m))			return true;		return false;	}}