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

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

Re: 11060 - Beverages

Post by outsbook » Thu Nov 17, 2011 2:55 am

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 » Fri Oct 05, 2012 2:50 pm

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 » Fri Oct 05, 2012 7:25 pm

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 » Fri Jun 28, 2013 11:00 am

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 » Fri Jun 28, 2013 10:34 pm

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 » Tue Jul 15, 2014 7:07 am

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 » Tue Jul 15, 2014 7:39 pm

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

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

Post by lighted » Fri Jul 18, 2014 11:11 am

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 » Mon Jul 21, 2014 2:03 am

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11060 - Beverages

Post by lighted » Mon Jul 21, 2014 11:50 am

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 » Mon Jul 21, 2014 9:09 pm

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 » Thu Jul 31, 2014 7:00 pm

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 » Thu Jul 31, 2014 8:51 pm

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11060 - Beverages

Post by lighted » Fri Aug 01, 2014 5:19 am

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 » Tue Aug 05, 2014 2:07 pm

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)”