Page 2 of 3
825 ..... WA
Posted: Wed Dec 21, 2005 9:19 am
by Wei-Ming Chen
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;
Posted: Fri Dec 23, 2005 11:26 pm
by daveon
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.
Posted: Thu Dec 29, 2005 2:28 pm
by Wei-Ming Chen
Yeah, my output is 70.
I don't know what is wrong.....
Posted: Thu Dec 29, 2005 11:11 pm
by daveon
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.
Posted: Tue Jan 03, 2006 7:14 am
by Wei-Ming Chen
To Daveon: Thanks very much, now I got AC.
The reason that I got WA maybe is there are some spaces after the input.
825 (walking in safe side) WA and severe heart attack
Posted: Sat Aug 12, 2006 6:36 am
by Shuvra(CSE-BUET)
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 .
................................................................................................
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.
Posted: Sat Aug 12, 2006 11:12 am
by smile2ka10
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!.
Posted: Tue Jan 16, 2007 5:25 pm
by Donotalo
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?
Posted: Tue Jul 24, 2007 6:21 am
by ferrizzi
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); }
}
I have problem!!!
Posted: Tue Sep 25, 2007 3:12 pm
by stimim
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??
Posted: Wed Oct 17, 2007 8:04 am
by Rupak
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] ?
Re: 825 - Walking on the Safe Side
Posted: Wed Jun 25, 2008 9:03 am
by smilitude
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!
Re: 825 - Walking on the Safe Side
Posted: Tue Sep 09, 2008 7:25 am
by stcheung
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.
825 - Walking on the Safe Side
Posted: Fri Feb 05, 2010 9:31 pm
by saiful_sust
CUT AFTER ACCC...............
- IMPOSSIBLE MEANS I M POSSIBLE
825 - Walking on the Safe Side
Posted: Fri Feb 05, 2010 9:33 pm
by saiful_sust
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
One more thing After ACC PLZ remove ur code....
- IMPOSSIBLE MEANS I M POSSIBLE