11060 - Beverages

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

Re: 11060 - Beverages

Post by 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.

Last edited by outsbook on Sat Nov 19, 2011 5:14 pm, edited 1 time in total.
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

sanket_singhal
New poster
Posts: 1
Joined: Fri Oct 05, 2012 2:44 pm

WA in 11060 - Beverages

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: WA in 11060 - Beverages

Post by brianfry713 »

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

sun_kuet
New poster
Posts: 12
Joined: Wed Mar 27, 2013 4:28 pm

11060-Beverage getting WA.help

Post by sun_kuet »

Code removed after Accepted
Last edited by sun_kuet on Fri Jun 28, 2013 11:13 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11060-Beverage getting WA.help

Post by brianfry713 »

After each test case you must print a blank line, including the last one.
Check input and AC output for thousands of problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

11060 - Beverages!!!!!!!!!!!!why getting WA?

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11060 - Beverages!!!!!!!!!!!!why getting WA?

Post by brianfry713 »

Try running your code on the sample input. Don't put frowny faces in your code.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11060 - Beverages!!!!!!!!!!!!why getting WA?

Post by 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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

milseg
New poster
Posts: 4
Joined: Mon Jul 07, 2014 8:05 pm

11060 - Beverages

Post by 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
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11060 - Beverages

Post by lighted »

Martin Macko wrote:
little joey wrote: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..
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

milseg
New poster
Posts: 4
Joined: Mon Jul 07, 2014 8:05 pm

Re: 11060 - Beverages

Post by 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
New poster
Posts: 20
Joined: Fri Aug 30, 2013 5:42 am

11060 - Beverages

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11060 - Beverages

Post by brianfry713 »

In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11060 - Beverages

Post by 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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

flashion
New poster
Posts: 17
Joined: Thu Jul 24, 2014 10:29 pm

Re: 11060 - Beverages

Post by 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?

Post Reply

Return to “Volume 110 (11000-11099)”