11661 - Burger Time?

[dubukuangye]

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]

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.

[Rashad]

I am getting WA. Please help.

[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]

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

Code: Select all

// Code removed after AC!

[brianfry713]

Input:

Code: Select all

3
RDZ
0

Output should be 0.

[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]

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]

Don't double post

[brianfry713]

Try keeping track of the last restaurant and the last drugstore.

[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]

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

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]

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

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.

[axelblaze]

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

[uDebug]

got ac...

Well done! Glad you figured it out!

Remember to remove the source code from your previous post since that's mostly AC code.