11661 - Burger Time?

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

Moderator: Board moderators

dubukuangye
New poster
Posts: 4
Joined: Wed Jul 14, 2010 12:54 pm

Re: 11661-Burger Time. ...Why WA?????

Post by dubukuangye »

naseef_07cuet wrote:I already got accepted before your post.
By the way thank you.
I keep record of every position of D and R. Then use sort algorithm and search for the minimun.
This taks O(NlgN),so i get WA. Can you guys tell me the AC algorithm?

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 11661 - Burger Time?

Post by sazzadcsedu »

I don't know why u used sorting.This problem has complexity O(n).Just follow the steps given below-

1. If you find z ,then output 0.
2. if you find D then proceed,if you found (.) then increment distance by 1,if find D then reset distance=0,if u find R then compare the distance with previous computed mindistance and update mindistance accordingly.
3. if you find R then proceed,if you found (.) then increment distance by 1,if find R then reset distance=0,if u find D then compare the distance with previous computed mindistance and update mindistance accordingly.
4. Be careful about flaging ,you must keep track from which, D or R you start counting.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

Rashad
New poster
Posts: 17
Joined: Tue Dec 22, 2009 4:20 pm

Re: 11661 - Burger Time?

Post by Rashad »

I am getting WA. Please help.

shakil ahmed
New poster
Posts: 3
Joined: Wed Oct 12, 2011 5:20 am

Re: 11661 - Burger ?Why WA in MY code

Post by shakil ahmed »

plz help me?why WA

#include <stdio.h>
char a[128],c,d;
int main()
{
a['D']='R';
a['R']='D';
long long int n,i,j;
while(scanf("%lld",&n)==1)
{if(n==0)
break;
long long int min=90000000;
for(i=0;i<n;i++)
{scanf("%c",&c);
if(c=='Z'||c=='D'||c=='R')
{ if(c=='Z')
min=0;
d=a[c];
break;}}
long long int k=0,l=0;
for(j=i;j<n;j++)
{
scanf("%c",&c);
k++;
if(c=='Z')
min=0;
else if(c=='D'|| c=='R')
{ if(c==d)
{
if(min>k)
{
min=k;
}
d=a[c];
k=0;}
else
k=0;
}
}

printf("%lld\n",min);


}
return 0;
}

jalil_cse
New poster
Posts: 8
Joined: Tue Dec 25, 2012 12:35 pm

Re: 11661 - Burger Time?

Post by jalil_cse »

I am getting WA.......please help me

Code: Select all

// Code removed after AC!

Last edited by jalil_cse on Thu Jul 04, 2013 1:58 pm, edited 1 time in total.

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

Re: 11661 - Burger Time?

Post by brianfry713 »

Input:

Code: Select all

3
RDZ
0
Output should be 0.
Check input and AC output for thousands of problems on uDebug!

Samleo
New poster
Posts: 11
Joined: Mon Dec 03, 2012 2:39 pm

Re: 11661 - Burger Time?

Post by Samleo »

Please help with my WA code :( Or at least post some testcases for me to use for debugging?

Code: Select all

#include<cstdio>
#include<cstring>
#include<string>

using namespace std;

#define MAX_N 2000000

int main(){
    int l,i;
    int dist,finalDist;
    char c;
    bool jackpot,rest;
    
    /*
    freopen("burger.in","r",stdin);
    freopen("burger.out","w",stdout);
    //*/
     
    while(scanf("%d\n",&l)!=EOF){
        if(!l) break;
        
        finalDist = l;
        dist = 0;
        rest = false;
        jackpot = false;
        
        for(i=0;i<l;i++){
            scanf("%c",&c);
            if(jackpot) continue;
            
            if(c=='Z'){
                finalDist = 0;
                jackpot = true;
                continue;
            }
            
            if(c=='R'){
                if(rest){
                    dist = 1; //reset
                }
                else{
                    rest = true;
                    if(dist) finalDist = min(finalDist,dist);
                    dist = 1;
                }
            }
            else if(c=='D'){
                if(rest){
                    rest = false;
                    finalDist = min(finalDist,dist);
                }
                else{
                    dist = 1; //reset
                }
            }
            else if(c=='.' && dist){
                dist++;
            }
        }
        
        scanf("\n");
        printf("%d\n",finalDist);

    }
    
    return 0;
}

Samleo
New poster
Posts: 11
Joined: Mon Dec 03, 2012 2:39 pm

Re: 11661 - Burger Time? why WA?

Post by Samleo »

Also WA, but code seems correct?

Code: Select all

#include<cstdio>
#include<cstring>
#include<string>

using namespace std;

#define MAX_N 2000000

int main(){
    int l,i;
    int dist,finalDist;
    char c;
    bool jackpot,rest;
    
    /*
    freopen("burger.in","r",stdin);
    freopen("burger.out","w",stdout);
    //*/
     
    while(scanf("%d\n",&l)!=EOF){
        if(!l) break;
        
        finalDist = l;
        dist = 0;
        rest = false;
        jackpot = false;
        
        for(i=0;i<l;i++){
            scanf("%c",&c);
            if(jackpot) continue;
            
            if(c=='Z'){
                finalDist = 0;
                jackpot = true;
                continue;
            }
            
            if(c=='R'){
                if(rest){
                    dist = 1; //reset
                }
                else{
                    rest = true;
                    if(dist) finalDist = min(finalDist,dist);
                    dist = 1;
                }
            }
            else if(c=='D'){
                if(rest){
                    rest = false;
                    finalDist = min(finalDist,dist);
                }
                else{
                    dist = 1; //reset
                }
            }
            else if(c=='.' && dist){
                dist++;
            }
        }
        scanf("\n");
        
        printf("%d\n",finalDist);
    }
    
    return 0;
}

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

Re: 11661 - Burger Time?

Post by brianfry713 »

Don't double post
Check input and AC output for thousands of problems on uDebug!

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

Re: 11661 - Burger Time? why WA?

Post by brianfry713 »

Try keeping track of the last restaurant and the last drugstore.
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11661 - Burger Time?

Post by uDebug »

I found these test cases useful while debugging / testing my code.

Input:

Code: Select all

2
RD
5
..Z..
10
.R......D.
10
.R..Z...D.
10
...D..R...
25
..D...R.RR...DD...D.R...R
3
RDZ
8
R.D...RD
5
RD...
5
DR...
6
DDDDDR
6
RRRRRD
12
DDDDRRRRZDRD
20
D..R...DR..D.......R
20
R..R...R..D....R..DR
20
D..R...R..D....R..RD
20
D..R...R..D....R..RZ
20
R..D...R.DD........R
0
AC Output:

Code: Select all

1
0
7
0
3
2
0
1
1
1
1
1
0
1
1
1
0
2

axelblaze
New poster
Posts: 34
Joined: Mon Jun 23, 2014 7:45 pm

Re: 11661 - Burger Time?

Post by axelblaze »

why my code is getting compile error..? :( :(
I pasted the conio.h header file on my system(kubuntu 14.04) to use getche(). is it because of that???
plz help.... :cry:

Code: Select all

#include<iostream>
#include<conio.h>
using namespace std;

int main()
{
    int t,temp;
    char a,flag;
    while(cin>>t,t)
    {
        cin.ignore();
        flag=0; temp=t;
        for(int i=0,j=0;i<t;i++)
        {
            a=getche();
            if(a=='Z'||flag==5){flag=5;temp=0;}
            else if(a=='R')
            {
                if(flag==0)
                {
                    flag='R';
                    j=i;
                }
                else if(flag=='R') j=i;
                else if(flag=='D')
                {
                    flag='R';
                    if(i-j<temp)temp=i-j;
                    j=i;
                }
            }
            else if(a=='D')
            {
                if(flag==0)
                {
                    flag='D';
                    j=i;
                }
                else if(flag=='D') j=i;
                else if(flag=='R')
                {
                    flag='D';
                    if(i-j<temp)temp=i-j;
                    j=i;
                }

            }
            if(i==t-1) cin.ignore();
        }
        if(flag==0)
            cout<<'0'<<endl;
        else cout<<temp<<endl;
    }
    return 0;
}

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11661 - Burger Time?

Post by uDebug »

axelblaze wrote:why my code is getting compile error..? :( :(
I pasted the conio.h header file on my system(kubuntu 14.04) to use getche(). is it because of that???
plz help.... :cry:
So, first: You can find what exactly your compile error is by clicking on "My submissions" when logged into UVa. This way at least you'll know what the issue is next time.

And, yes, it is indeed the "conio.h" header file that's causing the issue. So, get rid of that header file and change "getche" to "getchar()". Your program then compiles and runs OK.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

axelblaze
New poster
Posts: 34
Joined: Mon Jun 23, 2014 7:45 pm

Re: 11661 - Burger Time?

Post by axelblaze »

Thanks v1n1t. I did as you said and got ac... :D :D :D

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11661 - Burger Time?

Post by uDebug »

axelblaze wrote:got ac... :D :D :D
Well done! Glad you figured it out!

Remember to remove the source code from your previous post since that's mostly AC code.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 116 (11600-11699)”