825 - Walking on the Safe Side

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

Moderator: Board moderators

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

825 ..... WA

Post by Wei-Ming Chen » Wed Dec 21, 2005 9:19 am

I got WA again.....
Please help me. Thanks.

#include <stdio.h>
bool a[101][101];
int b[101][101];
int main()
{
int c,d,e,f,h,i,j;
char g;
scanf("%d",&c);
for(d=1;d<=c;d++)
{
scanf("%d %d",&e,&f);
for(h=1;h<=e;h++)
{
for(i=1;i<=f;i++)
{
a[h][i]=0;
}
}
for(h=1;h<=100;h++)
{
b[0][h]=0;
b[h][0]=0;
}
for(h=1;h<=e;h++)
{
scanf("%d%c",&i,&g);
if(g=='\n')
{
continue;
}
for(;;)
{
scanf("%d%c",&i,&g);
a[h][i]=1;
if(g=='\n')
{
break;
}
}
}
b[1][1]=1;
Last edited by Wei-Ming Chen on Tue Jan 03, 2006 7:12 am, edited 1 time in total.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Fri Dec 23, 2005 11:26 pm

Hi,

INPUT:

Code: Select all

1

10 9
1 1 3 5 7 9
2 
3 1 3 5 7 9
4 
5 1 3 5 7 9
6 
7 1 3 5 7 9
8 
9 1 3 5 7 9
10
The output should be 70.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Thu Dec 29, 2005 2:28 pm

Yeah, my output is 70.
I don't know what is wrong.....

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Thu Dec 29, 2005 11:11 pm

Hi Wei-Ming,

Sorry, there was nothing wrong with your algorithm, it is correct.
The problem lies in your input. Here are the corrections to your code that I have made to get it AC.

Code: Select all

#include <stdio.h>
#include <string.h>

int a[1010][1010];
int b[1010][1010];
char line[1000];
char *pch;

int main()
{

int c,d,e,f,h,i,j;
char g;




gets(line);
sscanf(line,"%d",&c);
for(d=1;d<=c;d++)
{
gets(line);
gets(line);
sscanf(line,"%d %d",&e,&f);
for(h=1;h<=e;h++)
{
for(i=1;i<=f;i++)
{
a[h][i]=0;
}
}
for(h=1;h<=100;h++)
{
b[0][h]=0;
b[h][0]=0;
}





for(h=1;h<=e;h++)
{
    gets(line);
    pch=strtok(line," ");
    pch=strtok(NULL," ");
    while(pch!=NULL)
    {
    sscanf(pch,"%d",&i);
    a[h][i]=1;
    pch=strtok(NULL," ");
    }
}





b[1][1]=1;
...
...
...
If you are still getting WA, then I'll send you the corrected code.
Have fun. :wink:

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Tue Jan 03, 2006 7:14 am

To Daveon: Thanks very much, now I got AC.
The reason that I got WA maybe is there are some spaces after the input.

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

825 (walking in safe side) WA and severe heart attack

Post by Shuvra(CSE-BUET) » Sat Aug 12, 2006 6:36 am

I read all the previous posts but failed to find out the reason of WA. I used dp , tried best to take input properly , and checked all the inputs posted previously.
Now i have no way , but to post my code here. Help me pleeeease .
:o
................................................................................................
code deleted after AC.
Thanks to smile2ka10.

Friends , be careful to take input. I used isspace() , getc() ,ungetc() to get rid of space , tab etc .These are very smart to take complex input.
Last edited by Shuvra(CSE-BUET) on Sat Aug 12, 2006 7:18 pm, edited 1 time in total.
Life is a challenge.

smile2ka10
New poster
Posts: 13
Joined: Wed Oct 26, 2005 10:14 pm
Location: Iran
Contact:

Post by smile2ka10 » Sat Aug 12, 2006 11:12 am

There are two points about your code:

First, you set p[1][1] after reading input to 1 which is supposed to mean that there is one way to cell (1,1) but it is possible that this cell is blocked so that the answer would be zero paths to cell (r,c).

Second, there is an error in the reading inputs where you want to read the blocked cells, I suggest you to use sstream class and istringstream in order to read them.

After considering these two issues I got your code AC!.

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Post by Donotalo » Tue Jan 16, 2007 5:25 pm

i tried every sample input in previous posts and ended up with WA, though for those inputs my program correctly generates the output.

i assumed that if the intersection (1, 1) or (w, n) is blocked, the answer is 0. is there anything wrong? can anyone give me some critical sample input and output?
Image

User avatar
ferrizzi
New poster
Posts: 23
Joined: Thu Mar 30, 2006 5:42 pm
Location: Brazil

Post by ferrizzi » Tue Jul 24, 2007 6:21 am

My solution to this problem run in 0.000 s and I didn't use DP. I just use a matrix to represent the streets and traverse it recursevely, counting a way everytime that it reaches the extreme point.

Code: Select all

int ans=0;
int p[MAX][MAX];

void coutWays(int x, int y){  
    //if it reaches the station
    if(x==l && y==c){ ans++; return; }

    //right
    if(p[x][y+1]==0){ countWays(x, y+1); }    
    
    //down
    if(p[x+1][y]==0){ countWays(x+1, y); }
}
Regards,
[]'s
Andre

stimim
New poster
Posts: 1
Joined: Mon Sep 24, 2007 4:55 pm

I have problem!!!

Post by stimim » Tue Sep 25, 2007 3:12 pm

Code: Select all

#include<iostream>
#define UNSAFE -1

using namespace std;

long long map[101][101];
int i,j,I,J,k; //I=>>W J=>>N
char line[1000],*pch;

int main(){
    int N;
    gets(line);
    sscanf(line,"%d",&N);
    while(N--){
        
        gets(line);
        gets(line);
        sscanf(line,"%d %d",&I,&J);
        
        for(i=0;i<=I;i++)
            for(j=0;j<=J;j++)
                map[i][j]=0;
        
        for(i=1;i<=I;i++){
            gets(line);
            pch=strtok(line," \t");
            sscanf(pch,"%d",&k);
            pch=strtok(NULL," \t");
            while(pch!=NULL){
                sscanf(pch,"%d",&j);
                map[k][j] = UNSAFE;
                pch=strtok(NULL," \t");
            }
        }
        map[1][1]=1;
                
        for(i=1;i<=I;i++){
            for(j=1;j<=J;j++){
                if(map[i][j]==UNSAFE)
                    map[i][j]=0;
                else if(map[i][j]==0)
                    map[i][j]=map[i-1][j] + map[i][j-1];
            }
        }
        cout << map[I][J] << endl << endl;
    }

    return 0;
}
That's my code.
I've read many post about 825, I've tried considering if the west-north corner and east-south corner would be unsafe. But still WA.
And I've tried to add some space or Tab in input, but doesn't cause any problem on my computer.
Is there anything wrong?? :( :(

User avatar
Rupak
New poster
Posts: 8
Joined: Mon Jan 15, 2007 6:53 am
Location: Bangladesh

Post by Rupak » Wed Oct 17, 2007 8:04 am

daveon wrote:Hi,

INPUT:

Code: Select all

1

10 9
1 1 3 5 7 9
2 
3 1 3 5 7 9
4 
5 1 3 5 7 9
6 
7 1 3 5 7 9
8 
9 1 3 5 7 9
10
The output should be 70.

in that case mat[1][1] is forbidden. Is it possible to reach mat[W][N] ?
_______________________________________
http://acm.uva.es/problemset/usersnew.php?user=6114

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Re: 825 - Walking on the Safe Side

Post by smilitude » Wed Jun 25, 2008 9:03 am

my AC code prints 0 for that case.
i got a lots of WA for not using long long. int overflows.
and that input made me nuts for a while! :(
fahim
#include <smile.h>

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 825 - Walking on the Safe Side

Post by stcheung » Tue Sep 09, 2008 7:25 am

This problem is very lenient, no need for fancy algorithm. My simple Java program (using recursion) got AC after running 0.080. Also note that because of the minimal path requirement, you only need to move either down or right at each step.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

825 - Walking on the Safe Side

Post by saiful_sust » Fri Feb 05, 2010 9:31 pm

CUT AFTER ACCC...............
  • IMPOSSIBLE MEANS I M POSSIBLE
Last edited by saiful_sust on Fri Feb 05, 2010 9:35 pm, edited 1 time in total.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

825 - Walking on the Safe Side

Post by saiful_sust » Fri Feb 05, 2010 9:33 pm

Hi Shamim
Ur algorithm is Right..
Just a small error i found in ur code...
" The outputs of two consecutive cases will be separated by a blank line."
That means in last line there will be no new line But ur code give an extra new line

Correct it and :D

One more thing After ACC PLZ remove ur code.... :D
  • IMPOSSIBLE MEANS I M POSSIBLE

Post Reply

Return to “Volume 8 (800-899)”