825 - Walking on the Safe Side
Moderator: Board moderators
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
825 ..... WA
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;
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.
Hi,
INPUT:
The output should be 70.
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
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
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.
If you are still getting WA, then I'll send you the corrected code.
Have fun.![:wink:](./images/smilies/icon_wink.gif)
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;
...
...
...
Have fun.
![:wink:](./images/smilies/icon_wink.gif)
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
-
- New poster
- Posts: 19
- Joined: Wed Jan 11, 2006 9:57 am
- Location: Dhaka
825 (walking in safe side) WA and severe heart attack
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.
Now i have no way , but to post my code here. Help me pleeeease .
![:o](./images/smilies/icon_eek.gif)
................................................................................................
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.
-
- New poster
- Posts: 13
- Joined: Wed Oct 26, 2005 10:14 pm
- Location: Iran
- Contact:
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!.
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!.
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
[]'s
Andre
I have problem!!!
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;
}
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??
![:(](./images/smilies/icon_frown.gif)
![:(](./images/smilies/icon_frown.gif)
daveon wrote:Hi,
INPUT:The output should be 70.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
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
http://acm.uva.es/problemset/usersnew.php?user=6114
Re: 825 - Walking on the Safe Side
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!![:(](./images/smilies/icon_frown.gif)
i got a lots of WA for not using long long. int overflows.
and that input made me nuts for a while!
![:(](./images/smilies/icon_frown.gif)
fahim
#include <smile.h>
#include <smile.h>
Re: 825 - Walking on the Safe Side
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.
-
- Learning poster
- Posts: 97
- Joined: Fri Aug 22, 2008 10:18 pm
- Location: CSE.SUST.SYLHET
825 - Walking on the Safe Side
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.
-
- Learning poster
- Posts: 97
- Joined: Fri Aug 22, 2008 10:18 pm
- Location: CSE.SUST.SYLHET
825 - Walking on the Safe Side
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