11797 - Drutojan Express

[naseef_07cuet]

I got accepted on the onsite contest. But getting WA now
plz someone help.
here is my code:

Code: Select all

// code removed after AC!

[yan yan]

try this

Code: Select all

1
10 11 Ja
5 Tan Sid Sam Sha Tan
1 Ja
1 Ja
1 Ja
1 Ja

output should be:

Code: Select all

Case 1:
Ja 10
Sam 0
Sha 0
Sid 0
Tan 0

good luck!

[naseef_07cuet]

got it AC.
Thnx ....

[sachin_midha]

Hi, I tried to solve this problem on the judge but it gave me a run time error during the contest although it ran perfectly in my Dev-CPP...

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
int t,n,m,cost[5]={0},k[5],i,j,c=1;
string ar[5][20],name,save;
map<string,int> mymap;
map<string,int>::iterator it;
mymap["Ja"]=0;
mymap["Sam"]=1;
mymap["Sha"]=2;
mymap["Sid"]=3;
mymap["Tan"]=4;
//cout<<mymap["Ja"];
cin>>t;
while(t--){
cin>>m>>n>>name;
for(i=0;i<5;i++){
cin>>k;
for(j=0;j<k;j++){
cin>>ar[j];
}
}
cost[mymap[name]]+=m;
j=m+2;
while(j+m<n)
{
cost[mymap[ar[mymap[name]][0]]]+=m;

save=ar[mymap[name]][0]; //save next man

for(i=0;i<k[mymap[name]]-1;i++)
ar[mymap[name]]=ar[mymap[name]][i+1];

ar[mymap[name]][i+1]=save;
name=save; // Now he is to be analyzed next
j+=m;
n-=2;
} //end of while

cost[mymap[ar[mymap[name]][0]]]+=n-j;
cout<<"Case "<<c++<<": "<<endl;
for ( i=0,it=mymap.begin() ; it != mymap.end(); it++,i++ )
cout<<(*it).first<<" "<<cost<<endl;

}
return 0;
}

Could any one plz help me out, why am I getting this run time error??

Thanks,

[yan yan]

Dear sachin_midha...
i have not known why you got RE but firstly , your code was wrong!!! . Try my case above.....
hope it's helpful!

[sachin_midha]

Oh ya, there was a problem with the first statement after the while loop, I was adding n-j without checking if n was less than j or not. Thanx for pointing this out, but Im still getting a run time error. It has happened on quite a lot of other problems as well , specially when im using maps. Plz help me find out my mistake.
Heres the code after correction:

Code: Select all

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{   
    int t,n,m,cost[5]={0},k[5],i,j,c=1;
    string ar[5][20],name,save;
    map<string,int> mymap;
    map<string,int>::iterator it;
    //Setting up mymap
    mymap["Ja"]=0;
    mymap["Sam"]=1;
    mymap["Sha"]=2;
    mymap["Sid"]=3;
    mymap["Tan"]=4;
    cin>>t;
    while(t--){
               for(i=0;i<5;i++) cost[i]=0;
               cin>>m>>n>>name;           
               for(i=0;i<5;i++){
                   cin>>k[i];
                   for(j=0;j<k[i];j++){
                       cin>>ar[i][j];
                   }                 
               }
               cost[mymap[name]]+=m;
               j=m+2;
               while(j+m<n)
               {
               cost[mymap[ar[mymap[name]][0]]]+=m;
               
               save=ar[mymap[name]][0]; //save first man
               
               // Loop to shift first man to the last of the list
               for(i=0;i<k[mymap[name]]-1;i++)
                    ar[mymap[name]][i]=ar[mymap[name]][i+1];
                    
               ar[mymap[name]][i+1]=save;
               name=save; // Now he is to be analyzed next
               j+=m;
               n-=2; //reduce total time further by 2(swap time)
               } 
               
               //add the remaining time if any to the last man's cost
               if(n>=j)
               cost[mymap[ar[mymap[name]][0]]]+=n-j;
               
               //Output
               cout<<"Case "<<c++<<": "<<endl;
               for ( i=0,it=mymap.begin() ; it != mymap.end(); it++,i++ )
                   cout<<(*it).first<<" "<<cost[i]<<endl;

    }
    return 0;
}

[mak(cse_DU)]

for(i=0;i<k[mymap[name]]-1;i++)
ar[mymap[name]]=ar[mymap[name]][i+1];

ar[mymap[name]][i+1]=save;

Check these above lines carefully.
when k[mymap[name]]==20,

After the loop i will be 19.
Then "ar[mymap[name]][19+1]=save;" which is wrong And also it will create RE .
Because ar[5][20] allow ar[0-4][0-19].

So replace "ar[mymap[name]][i+1]=save" with ar[mymap[name]]=save.

[sachin_midha]

Hey mak thanks a lot for pointing out this mistake.
I made this correction but this code still returned a wrong answer after 0.072 sec.
Have I missed out of some corner case??

[mak(cse_DU)]

@Sachin

Actually I tried to figure out the Runtime error ignoring the wrong answer.
Anyway try below multiple cases input:

Code: Select all

    2
    3 11 Ja
    5 Tan Sid Sam Sha Tan
    1 Ja
    1 Ja
    1 Ja
    1 Ja

    3 11 Ja
    5 Tan Sid Sam Sha Tan
    1 Ja
    1 Ja
    1 Ja
    1 Ja

Compare two output and think how big mistake you have done.

[sachin_midha]

OMG...i forgot to reinitialize my cost array...
Thnx a lot for finding out such a foolish mistake. (i've edited the code above)
But the problem still continues...Wrong Answer again
I've read the code again & again but cant find out any other (such foolish ) mistake...

[Bella Swan]

Array size was the trouble.

Code: Select all

AC

[mak(cse_DU)]

OMG...i forgot to reinitialize my cost array...
Thnx a lot for finding out such a foolish mistake. (i've edited the code above)
But the problem still continues...Wrong Answer again
I've read the code again & again but cant find out any other (such foolish ) mistake...

Try this:
Input:

Code: Select all

    1
    3 2 Ja
    5 Tan Sid Sam Sha Tan
    1 Ja
    1 Ja
    1 Ja
    1 Ja

AC Output:

Code: Select all

Case 1:
Ja 2
Sam 0
Sha 0
Sid 0
Tan 0

Your code will give wrong output for the above case.
Read your code carefully to find out boundary case.

ar[mymap[name]][i+1]=save;

What about i+1??

[matrix]

bug found
code removed

[uDebug]

Here's some input / output that I found useful during testing / debugging.

Input:

Code: Select all

7
22 10 Sid
5 Tan Sid Sam Sha Tan
1 Ja
1 Ja
1 Ja
1 Ja
11 11 Ja
5 Tan Sid Sam Sha Tan
1 Ja
1 Ja
1 Ja
1 Ja
11 12 Sha
5 Tan Sid Sam Sha Tan
1 Ja
1 Ja
1 Ja
1 Ja
11 13 Sam
5 Tan Sid Sam Sha Tan
1 Ja
1 Ja
1 Ja
1 Ja
3 50 Sam
6 Sam Sha Tan Tan Tan Sid
5 Sha Sha Sid Tan Sha
2 Sam Ja
10 Ja Sam Ja Sam Ja Sam Ja Sam Sam Ja
4 Sid Sha Sam Ja
3 35 Sam
2 Sam Sha 
2 Sha Sha 
2 Sam Ja
1 Ja 
2 Sid Sha
3 1000 Sam
6 Sam Sha Tan Tan Tan Sid
5 Sha Sha Sid Tan Sha
2 Sam Ja
10 Ja Sam Ja Sam Ja Sam Ja Sam Sam Ja
4 Sid Sha Sam Ja

AC Output:

Code: Select all

Case 1:
Ja 0
Sam 0
Sha 0
Sid 10
Tan 0
Case 2:
Ja 11
Sam 0
Sha 0
Sid 0
Tan 0
Case 3:
Ja 0
Sam 0
Sha 11
Sid 0
Tan 0
Case 4:
Ja 0
Sam 11
Sha 0
Sid 0
Tan 0
Case 5:
Ja 6
Sam 12
Sha 9
Sid 3
Tan 0
Case 6:
Ja 3
Sam 9
Sha 9
Sid 0
Tan 0
Case 7:
Ja 129
Sam 159
Sha 141
Sid 78
Tan 93

[Shahidul.CSE]

I am getting WA.

Here's some input / output that I found useful during testing / debugging.

Input:

Code: Select all

7
22 10 Sid
5 Tan Sid Sam Sha Tan
1 Ja
1 Ja
1 Ja
1 Ja
11 11 Ja
5 Tan Sid Sam Sha Tan
1 Ja
1 Ja
1 Ja
1 Ja
11 12 Sha
5 Tan Sid Sam Sha Tan
1 Ja
1 Ja
1 Ja
1 Ja
11 13 Sam
5 Tan Sid Sam Sha Tan
1 Ja
1 Ja
1 Ja
1 Ja
3 50 Sam
6 Sam Sha Tan Tan Tan Sid
5 Sha Sha Sid Tan Sha
2 Sam Ja
10 Ja Sam Ja Sam Ja Sam Ja Sam Sam Ja
4 Sid Sha Sam Ja
3 35 Sam
2 Sam Sha 
2 Sha Sha 
2 Sam Ja
1 Ja 
2 Sid Sha
3 1000 Sam
6 Sam Sha Tan Tan Tan Sid
5 Sha Sha Sid Tan Sha
2 Sam Ja
10 Ja Sam Ja Sam Ja Sam Ja Sam Sam Ja
4 Sid Sha Sam Ja

AC Output:

Code: Select all

Case 1:
Ja 0
Sam 0
Sha 0
Sid 10
Tan 0
Case 2:
Ja 11
Sam 0
Sha 0
Sid 0
Tan 0
Case 3:
Ja 0
Sam 0
Sha 11
Sid 0
Tan 0
Case 4:
Ja 0
Sam 11
Sha 0
Sid 0
Tan 0
Case 5:
Ja 6
Sam 12
Sha 9
Sid 3
Tan 0
Case 6:
Ja 3
Sam 9
Sha 9
Sid 0
Tan 0
Case 7:
Ja 129
Sam 159
Sha 141
Sid 78
Tan 93

My program gives same output for case 1,2,3,4,6. But for case 5 and 7 my program gives wrong output. Its giving:

Code: Select all

Case 5:
Ja 9
Sam 9
Sha 9
Sid 3
Tan 0
Case 7:
Ja 192
Sam 87
Sha 126
Sid 60
Tan 135

But i can't find where is wrong in my code?
My code:

Code: Select all

#include <stdio.h>
#include <string.h>
struct lst
{
    int listLen, time, serial[30];
    char name[5];
    char listname[25][5];
}SL[7];
int main()
{
    int start, t, c, M, N, i, k, j, tmp;
    char first[5];
    strcpy(SL[1].name, "Ja");
    strcpy(SL[2].name, "Sam");
    strcpy(SL[3].name, "Sha");
    strcpy(SL[4].name, "Sid");
    strcpy(SL[5].name, "Tan");

    scanf("%d",&t);
    for(c=1;c<=t;c++)
    {
        scanf("%d %d %s", &M, &N, first);

        for(i=1;i<=5;i++)
        {
            if(strcmp(first, SL[i].name)==0)
            {
                start=i;
                break;
            }
        }

        for(i=1;i<=5;i++)
            SL[i].time=0;

        for(i=1;i<=5;i++)
        {
            scanf("%d",&SL[i].listLen);
            for(j=1;j<=SL[i].listLen;j++)
            {
                scanf("%s",SL[i].listname[j]);
                for(k=1;k<=5;k++)
                {
                    if(strcmp(SL[i].listname[j], SL[k].name)==0)
                    {
                        SL[i].serial[j]=k;
                        break;
                    }
                }
            }
        }
        i=start;
        while(N>0)
        {
            if(N<=M)
            {
                SL[i].time+=N;
                N=0;
            }
            else
            {
                SL[i].time+=M;
                N-=(M+2);
                start=SL[i].serial[1];
                for(j=1;j<SL[i].listLen;j++)
                {
                    SL[i].serial[j]=SL[i].serial[j+1];

                }
                SL[i].serial[j]=SL[i].serial[1];
                i=start;
            }
        }
        printf("Case %d:\n",c);
        for(i=1;i<=5;i++)
            printf("%s %d\n",SL[i].name, SL[i].time);
    }

    return 0;
}