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 » Wed Jul 14, 2010 1:04 pm

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 » Fri Aug 13, 2010 7:26 am

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 » Fri Dec 17, 2010 6:52 pm

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 » Sat Oct 22, 2011 5:08 am

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 » Sun Jun 30, 2013 8:25 pm

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 » Tue Jul 02, 2013 1:14 am

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 » Sun Nov 03, 2013 10:05 am

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 » Sun Nov 03, 2013 4:15 pm

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 » Tue Nov 05, 2013 12:29 am

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 » Tue Nov 05, 2013 1:58 am

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

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

Re: 11661 - Burger Time?

Post by uDebug » Fri Dec 20, 2013 11:55 am

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 » Fri Jul 04, 2014 11:37 pm

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;
}

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

Re: 11661 - Burger Time?

Post by uDebug » Sat Jul 05, 2014 8:30 am

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 » Sat Jul 05, 2014 9:45 am

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

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

Re: 11661 - Burger Time?

Post by uDebug » Sat Jul 05, 2014 12:27 pm

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