11060 - Beverages

[Darko]

Well, if you followed that link above, you would've seen the explanation by chunyi81. I agree that it is the same thing, but UVa compiler doesn't agree with us

[ivan.cu]

I see. Please, have you some method for read input more quick. I try to use BufferedReader and i got RF.

[ikkaro]

check this input

Code: Select all

3
vodka
wine
beer
3
wine vodka
wine vodka
beer wine

the corect output:

Code: Select all

Case #14: Dilbert should drink beverages in this order: beer wine vodka.

i hope help you..

[Chok]

Hello all,
I used simple topological sort. But i didnt get correct output for the test case #3 given in the problem statement. Please someone help me to find my mistake. Am i misunderstood the problem? ? Thanks in advance.

Here is the output that i got for the input #3 in the problem statement :-

Case #3: Dilbert should drink beverages in this order: apple-juice wine beer martini vodka rum whiskey tequila cachaca gin.

Here is my code:-

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<queue>

using namespace std;

#define MAX 100
#define MAX_S 55

char name[MAX][MAX_S];
list<int>edge[MAX];
int indeg[MAX];
int mat[MAX][MAX];
int n;

void top_sort()
{
	vector<int> res;
	queue<int> Q;
	int w,i,v,e;
	for(i=0;i<n;i++)
	{
		if(!indeg[i])
			Q.push(i);
	}
	while(!Q.empty())
	{
		v=Q.front();
		res.push_back(v);
		Q.pop();
		e=edge[v].size();
		for(i=0;i<e;i++)
		{
			w=edge[v].front();
			edge[v].pop_front();
			indeg[w]--;
			if(!indeg[w])
				Q.push(w);
		}
	}
	for(i=0;i<res.size();i++)
		printf(" %s",name[res[i]]);
}

int find_pos(char *num)
{
	int i;
	for(i=0;i<n;i++)
	{
		if(strcmp(num,name[i])==0)
			return i;
	}
	return -1;
}


int main()
{
//	freopen("11060.in", "r", stdin);
//	freopen("11060.out", "w", stdout);
	int i,s,d,m,set=1;
	char buf[MAX_S+MAX],src[MAX_S],dst[MAX_S];
	while(scanf("%d\n",&n)==1)
	{
		memset(name,0,sizeof(name));
		memset(mat,0,sizeof(mat));
		memset(indeg,0,sizeof(indeg));
		for(i=0;i<n;i++)
		{
			gets(name[i]);
			edge[i].clear();
		}
		scanf("%d\n",&m);
		for(i=0;i<m;i++)
		{
			gets(buf);
			sscanf(buf,"%s %s",src,dst);
			s=find_pos(src);
			d=find_pos(dst);
			if(!mat[s][d])
			{
				edge[s].push_back(d);
				indeg[d]++;
				mat[s][d]=1;
			}
		}
		for(i=0;i<n;i++)
			edge[i].sort();		
		printf("Case #%d: Dilbert should drink beverages in this order:",set++);
		top_sort();
		printf(".\n\n");
	}	
	return 0;
}

[Erik]

Hi,

In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input.

Cu, Erik

[ikkaro]

hi!, your problem is in the queue, use a priority_queue in inverse order

i hope that you can understand me, my english isn't good

[Chok]

Hi Erik & ikkaro,
Thanks to both of u. Now i'm changing and i'll submit. Thanks again.

[FAQ]

Passed all test on 4 pages of the board , but still WA :'(
Some more tricky tests please?

Code: Select all

ACed

[asif_rahman0]

May be the following two lines:

Code: Select all

.............
freopen("11060.in", "r", stdin);
freopen("11060.out", "w", stdout);
.............

bye

[FAQ]

when I submit I removed it

[Martin Macko]

Passed all test on 4 pages of the board , but still WA :'(
Some more tricky tests please?

Not working for the following:

Code: Select all

10
B
C
D
E
F
G
H
I
J
K
18
J G
B F
I C
D I
K E
F J
H F
D C
K B
E I
D E
C G
I B
H D
K E
F G
H B
D J

My AC's output:

Code: Select all

Case #1: Dilbert should drink beverages in this order: H D K E I B C F J G.

[FAQ]

thanks Martin, I got AC!!

[mcgeun]

Code: Select all

#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>

#define MAX 101

using namespace std;

int edge[MAX][MAX];
int color[MAX];
int f[MAX];
int n, m;
int t;
int floyd[MAX][MAX];

void dfsVisit(int u);
void dfs();

int main()
{	
	int i, j, k;
	int count;
	map <string, int> drinkMap;
	map <int, string> resMap;
	map <int, string>::reverse_iterator rit;
	vector <string> drinkVec;

	count = 0;
	while (cin >> n)
	{
		count++;
		for (i=0; i<MAX; i++)
		{
			for (j=0; j<MAX; j++)
			{
				edge[i][j] = 0;
				floyd[i][j] = 0;
			}
		}

		string strInput;
		for (i=0; i<n; i++)
		{
			cin >> strInput;
			drinkMap[strInput] = i;
			drinkVec.push_back(strInput);
		}

		cin >> m;
		string strInput2;
		for (i=0; i<m; i++)
		{
			cin >> strInput >> strInput2;
			edge[drinkMap[strInput]][drinkMap[strInput2]] = 1;
			floyd[drinkMap[strInput]][drinkMap[strInput2]] = 1;
		}

		dfs();

		for (k=0; k<n; k++)
		{
			for (i=0; i<n; i++)
			{
				for (j=0; j<n; j++)
				{
					if (!floyd[i][j] && i!=j)
						if (floyd[i][k] && floyd[k][j])
						{
							floyd[i][j] = 1;
						}
				}
			}
		}

		for (i=0; i<n; i++)
		{
			resMap[f[i]] = drinkVec[i];
		}

		string arrRes[MAX];
		int arrInt[MAX];
		i = 0;
		for (rit=resMap.rbegin(); rit!=resMap.rend(); rit++)
		{
			arrRes[i] = rit->second;
			arrInt[i] = drinkMap[arrRes[i]];
			i++;
		}

		for (i=1; i<n; i++)
		{
			if (floyd[arrInt[i-1]][arrInt[i]])
			{
				continue;
			}
			for (j=i; j>0; j--)
			{
				if (arrInt[j]<arrInt[j-1] && !floyd[arrInt[j-1]][arrInt[j]])
				{
					int iTemp;
					iTemp = arrInt[j];
					arrInt[j] = arrInt[j-1];
					arrInt[j-1] = iTemp;
					string sTemp;
					sTemp = arrRes[j];
					arrRes[j] = arrRes[j-1];
					arrRes[j-1] = sTemp;
				}
				else
					break;
			}
		}

		cout << "Case #";
		cout << count;
		cout << ": Dilbert should drink beverages in this order:";

		for (i=0; i<n; i++)
		{
			cout << " "<< arrRes[i];
		}
		cout << ".\n" << endl;

		drinkMap.clear();
		drinkVec.clear();
		resMap.clear();
	}

	return 0;
}

void dfs()
{
	int i;
	for (i=0; i<n; i++)
	{
		color[i] = 0;
	}
	t = 0;

	for (i=0; i<n; i++)
	{
		if (color[i] == 0)
			dfsVisit(i);
	}
}

void dfsVisit(int u)
{
	int i;
	color[u] = 1;
	t++;

	for (i=0; i<n; i++)
	{
		if (edge[u][i] == 1)
		{
			if (color[i] == 0)
			{
				dfsVisit(i);
			}
		}
	}
	color[u] = 2;
	t++;
	f[u] = t;
}

I test my program through all test cases here,
and I correct,
but I got WA.
Is there more test cases?
Help me.

[MinSu]

Code: Select all

import java.io.*; 
import java.util.*; 
class Main{ 
   static void begin(){ 
      String str  = ""; 
      String fst[],snd[]; 
      List bev_list[]=new List[255]; 
      List rst_list; 
      int count,actLoop=0;       
      while(true){ 
         rst_list=new List(); 
         fst=new String[255]; 
         snd=new String[255]; 
         str = Main.readLn(100).trim(); 
         int nBev=Integer.parseInt(str); 
         for(int i=0;i<nBev;i++){ 
            bev_list[i]=new List();             
            str=Main.readLn(100).trim(); 
            List temp=bev_list[i]; 
            temp.insert(str);          
         } 
         str = Main.readLn(100).trim(); 
         int nCmp=Integer.parseInt(str); 
         for(int i=0;i<nCmp;i++){ 
            str=Main.readLn(150).trim(); 
            StringTokenizer st=new StringTokenizer(str," "); 
            fst[i]=((String)st.nextToken()).trim(); 
            snd[i]=((String)st.nextToken()).trim(); 
            for(int j=0;j<nBev;j++){ 
               List temp=bev_list[j]; 
               String cmpstr=temp.basic_element(); 
               if(cmpstr.equals(fst[i])){ 
                  temp.insert(snd[i]);                   
               } 
               if(cmpstr.equals(snd[i])){ 
                  temp.setIndegree(1); 
               } 
            } 
         } 
         System.out.println(); 
         count=nBev; 
         while(count>0){ 
            for(int i=0;i<nBev;i++){ 
               List temp1=bev_list[i]; 
               if(!temp1.isExit()){ 
                  if(temp1.indegree()==0){ 
                     str=temp1.remove(); 
                     rst_list.insert(str); 
                     temp1.setExit(); 
                     while(!temp1.isEmpty()){ 
                        String removeLine=temp1.remove(); 
                        for(int j=0;j<nBev;j++){ 
                           List temp2=bev_list[j]; 
                           String temp=temp2.basic_element(); 
                           if(!temp2.isExit()){ 
                              if(temp.equals(removeLine)){ 
                                 temp2.setIndegree(-1); 
                                 break; 
                              } 
                           } 
                        } 
                     } 
                     count--; 
                     break; 
                  }                   
               } 
            } 
         } 
         rst_list.printAll(actLoop+1); 
         actLoop++; 
      }       
   } 
   public static void main (String args[]){ 
      begin(); 
   } 
    static String readLn (int maxLg) { 
       String a=""; 
       int i=0; 
       try{while(true){ 
          i = System.in.read(); 
          if ((i<0)||(i=='\n')) break; 
          a+=(char) i;}} 
       catch (IOException e){return (null);} 
       if (i<0) return (null); 
       return a; 
    } 
} 
class DNode{ 
   private String element; 
   private DNode prev,next; 
   public DNode(){ 
      element=null; 
      prev=null; 
      next=null; 
   } 
   public DNode(String o,DNode nprev,DNode nnext){ 
      element=o; 
      prev=nprev; 
      next=nnext; 
   } 
   public void setElement(String o){ 
      element=o; 
   } 
   public void setPrev(DNode v){ 
      prev=v; 
   } 
   public void setNext(DNode n){ 
      next=n; 
   } 
   public String element(){ 
      return element; 
   } 
   public DNode next(){ 
      return next; 
   } 
   public DNode prev(){ 
      return prev; 
   } 
} 
class List{ 
   private int indegree,size; 
   private boolean exit; 
   private DNode head,tail; 
   public List(){ 
      head=new DNode(null,null,null); 
      tail=new DNode(null,null,null); 
      head.setNext(tail); 
      tail.setPrev(head); 
      size=0; 
      indegree=0; 
      exit=false; 
   } 
   public void setExit(){ 
      exit=true; 
   } 
   public boolean isExit(){ 
      return exit; 
   } 
   public boolean isEmpty(){ 
      boolean temp=(size==0); 
      return temp; 
   } 
   public int indegree(){ 
      return indegree; 
   } 
   public void setIndegree(int i){ 
      indegree+=i; 
   } 
   public String basic_element(){ 
      String rst=head.next().element(); 
      return rst; 
   } 
   public String remove(){ 
      DNode removeTarget=head.next(); 
      DNode newFirst=removeTarget.next(); 
      String temp=removeTarget.element(); 
      newFirst.setPrev(head); 
      head.setNext(newFirst); 
      removeTarget.setPrev(null); 
      removeTarget.setNext(null); 
      size--; 
      return temp; 
   }    
   public void insert(String o){ 
      DNode v=new DNode(null,null,null); 
      DNode oldPrev=tail.prev(); 
      v.setElement(o); 
      v.setPrev(oldPrev); 
      v.setNext(tail); 
      oldPrev.setNext(v); 
      tail.setPrev(v); 
      size++; 
   } 
   public void printAll(int n){ 
      DNode temp=head.next(); 
      System.out.print("Case #"+n+": Dilbert should drink beverages in this order:"); 
      for(int i=0;i<size;i++){ 
         String prn=temp.element(); 
         System.out.print(" "+prn);          
         temp=temp.next(); 
      } 
      System.out.println("."); 
      System.out.println(); 
   } 
}

My code has passed all test cases of sample and this page.
But I got WA.. for 3 days, I can't see AC.
What's the problem that make WA?
Please let me know where is illegal.

[1559]

#pragma warning (disable:4786)
#include<cstdio>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
vector <int> adj[105];
int col[105];
char str[205][100];
map <string,int> M;
void topo(int u)
{
int i;
if(col==0)
{
for(i=0;i<adj.size();i++)
{
topo(adj);
}
col=1;printf(" %s",str);
}

}
int main()
{
int i,j,k,m,n,u,v,x=1,t,f;
char s[100],st[100];

while(scanf("%d",&n)==1)
{
for(i=0;i<n;i++)
{
scanf("%s",str);
if(M.find(str)==M.end())
M[str]=i;

}
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%s%s",s,st);
u=M[s];
v=M[st];
adj[v].push_back(u);
}
for(i=0;i<=n;i++)
col=0;

printf("Case #%d: Dilbert should drink beverages in this order:",x++);

for(i=0;i<n;i++)
{
if(col==0)
{
topo(i);
}

}
puts(".\n");


for(i=0;i<=n;i++)
{
adj.clear();
}
M.clear();

}
return 0;
}

I got WA . can anyone help???