11060 - Beverages

[outsbook]

try this

Code: Select all

Input:
3
a
b
c
4
a b
b c
a b
b c

output:
Case #1: Dilbert should drink beverages in this order: a b c.

[sanket_singhal]

i m getting WA in beverages... help me with some test cases....

Code: Select all

#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
int s[200];
int main()
{
    int n,er=1,k,i,j,cnt,fr;
    while(scanf("%d",&n)!=EOF)
    {int mat[n+1][n+1],deg[n+1],degin[n+1],minc[n+1][n+1],l[n+1],g[n+1],mark[n+1],ans[n+1];
    map<string,int> m;
    map<int,string> d;
    char c[52],st[52];
    for(i=0;i<=n;i++)
    {
        deg[i]=degin[i]=g[i]=ans[i]=mark[i]=l[i]=0;
    }
    for(i=1;i<=n;i++)
    {
        cin>>c;
        m[c]=i;
        d[i]=c;
    }
    int me,q;cin>>me;
    for(i=1;i<=me;i++)
    {
        cin>>c>>st;
        for(j=0;j<=deg[m[c]];j++)
        {q=0;
            if(mat[m[c]][j]==m[st]) {q=1;break;}
        }
        if(q==0)
        {mat[m[c]][deg[m[c]]++]=m[st];
        minc[m[st]][degin[m[st]]++]=m[c];
        g[m[st]]=1;
        }
    }k=0;
    for(i=1;i<=n;i++)
    {
        if(g[i]==0) {l[k]=i;k++;}
    }
    sort(l,l+k);int rear=k-1,front=0;
     for(i=0;i<k;i++)
        {
            s[i]=l[i];
            l[i]=0;
        }
        k=0;
    while(front<=rear)
    {
        fr=s[front];
        mark[fr]=1;
        ans[k]=fr;k++;
        front++;
        for(i=0;i<deg[fr];i++)
        {
                cnt=0;
                if(mark[mat[fr][i]]==0)
                {for(j=0;j<degin[mat[fr][i]];j++)
                {
                    if(mark[minc[mat[fr][i]][j]]==0)
                    {
                        cnt++;
                    }
                }
                if(cnt==0)
                {
                    s[++rear]=mat[fr][i];
                    //mark[mat[fr][i]]=1;
                }
                }
        }
                sort(s+front,s+rear+1);
    }
    cout<<"Case #"<<er<<": Dilbert should drink beverages in this order: ";
    for(i=0;i<k-1;i++)
    {
        cout<<d[ans[i]]<<" ";
    }cout<<d[ans[k-1]];cout<<".\n\n";er++;
    }
return 0;
}

[brianfry713]

Doesn't match the sample I/O.

[sun_kuet]

Code removed after Accepted

[brianfry713]

After each test case you must print a blank line, including the last one.

[LazyTym]

Code: Select all

#include<iostream>
#include<list>
#include<stack>
#include<cstdio>
#include<cstring>

using namespace std;

int n,m;
list<int>*adj;
string S[101];

void topologicalUtil(int k,bool visited[],stack<int>&stk)
{
    visited[k]=true;
    list<int>::iterator i;
    for (i=adj[k].begin(); i!=adj[k].end(); ++i)
        if (!visited[*i])
            topologicalUtil(*i, visited, stk);

    stk.push(k);
}


void topologicalSort()
{
    stack<int>stk;
    bool *visited=new bool[n];
    for(int i=0;i<n;i++) visited[i]=false;
    for(int i=0;i<n;i++)
    {
        if(!visited[i])
        {
            topologicalUtil(i,visited,stk);
        }
    }

    while(stk.empty()==false)
    {
        int i;
        i=stk.top();
        cout<<S[i]<<" ";
        stk.pop();
    }
    printf("\n");

}

int findIndex(string a)
{
    for(int i=0;i<n;i++)
        if(S[i]==a) return i;
   return -1;
}


int main()
{
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    string a,b;
    int x,y,cs=1;


    while (scanf("%d",&n)!=EOF)
    {
        adj=new list<int>[n];
        for(int i=0;i<n;i++)
        {
            cin>>a;
            S[i]=a;
        }
        cin>>m;
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            x=findIndex(a);
            y=findIndex(b);
            adj[x].push_back(y);
        }
        cout<<"Case #"<<cs<<": Dilbert should drink beverages in this order: ";
        topologicalSort();
        printf("\n");
        cs++;
    }
    return 0;
}
 :( 

[brianfry713]

Try running your code on the sample input. Don't put frowny faces in your code.

[lighted]

You must search topics about your problem first.
Insert problem number 11060 into search box and you will get many explanations why your code may get WA.
For example:
http://acm.uva.es/board/viewtopic.php?f ... 44a4f77506

The main reason why you get WA is following problem description:

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

I think you misunderstood the problem.
You will not get accepted here like in 10305 problem.
In 10305 problem there were many solutions and any of them were acceptable.
In this problem will be only one valid solution. That's why your code doesn't match sample output.

If there is no relation between several beverages, you must print the one which appears first in the input.

[milseg]

For the moderators: I created this thread continuation cause the other thread didn't covered the subject i gonna talk about here.

I would like to clearify this problem once one of its sample test cases seems mismatched with the problem specifications.
The problem states that In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input.
On the following sample input, and corresponding output i can't find a relationship between whiskey and vodka, what means that they order must be yield by its order in the input, which is whiskey before vodka. As you can see it doesn't happen in the output, where vodka appears before whiskey. Could someone tell me if am i missing something? Thank you for reading my questions.

Input:

10
cachaca
rum
apple-juice
tequila
whiskey
wine
vodka
beer
martini
gin
11
beer whiskey
apple-juice gin
rum cachaca
vodka tequila
apple-juice martini
rum gin
wine whiskey
apple-juice beer
beer rum
wine vodka
beer tequila

Output:

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

[lighted]

Yes, good analysis. I was so fed up with this problem, I didn't bother to look anymore after I got AC in my third attempt (although I knew my program wouldn't cover all possible cases). I guess the program should print "impossible" or "illegal" in such cases.

I guess the problemsetter meant to write that beverage A should be brunk before beverage B if A has less alcohol content than B or beverages A and B are independent and beverage A is earlier in the input, where two beverages A and B are independent if and only if there is no (even indirect) alcoholic relation between them in the input and there is no yet undrunk beverage C with less alcohol content than A or B.

I think the outputs for examples mentioned in the problem statement correspond to this definition. Also my AC assumed that.

The problem statement is not clear.

As i understand above comment the order of drinking beaverages is as follows:

-> He drinks the beaverage X which doesn't have predecessor (beaverages which must be drunk before X) and which appears earlier in input.

Sample input:

1st is apple-juice (it is first beaverage in input which doesn't have predecessor)
2nd is wine (it doesn't have predecessor and it appears after apple-juice)
3rd will be vodka (because he drank wine already, he can drink now vodka. Vodka comes after wine in input.
He can't drink whiskey now because it have 1 predecessor which he didn't drink => beer)
4th is beer (beer comes after vodka in input. After this it is possible to drink whiskey because beer had drunk)
5th is rum (he drank beer, he can drink rum. now rum is the earliest beaveage in input which doesn't have predecessor and which he didn't drink yet)
6th is cachaca (he drank rum, he can drink cachaca. now cachaca is the earliest beaveage in input which doesn't have predecessor and which he didn't drink yet)
and so on..

Hope it is not confusing..

[milseg]

I understood your explanation and i've got AC. Thank you very much. Tough i think this problem could be better explained to avoid confusion.

[cyberdragon]

http://ideone.com/dssLP8

My output for the 3rd test case is different from the sample output but It is correct. so why WA?

[brianfry713]

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

[lighted]

You must search threads about your problem first.
Insert problem number 11060 into search box and you will get many explanations why your code may get WA.

For detailed explanation why your output doesn't match sample see
http://online-judge.uva.es/board/viewto ... 60#p370165.

[flashion]

I've been struggling with this problem for 2 hours, checked on all your tests and still got WA. Was anybody in this situation and got AC?