11067 - Little Red Riding Hood

[david]

I think the judge input for this problem doesn't meet the constraints (and neither did the input used during the contest).
First of all, there are cases when a wolf is located at (0, 0), contrary to the problem description. (I have checked this with assert). My program would then return 0 (which is the logical answer), but there should be no such cases (for those of you who got AC, what would your program return?).
Secondly, I am pretty sure my code is correct, but when I write an assert to make sure the result is smaller than 2^32, it fails. Should we truncate the answer to a 32-bit integer or what?

Here goes my code:

Code: Select all

[shanto86]

well... u may not worry about those. just go on as natural. u will get AC.

[use long long it is 64bit much higher than 32bit so no worry!]

ya for (0,0) wolf my code outputs 0.

[david]

I already use long longs (as you can see in the code above), and I get wrong answer even though my code is correct.
If you read what I wrote before, my point is that the judge input is flawed and I can't guess what I have to do in order to get accepted.

[mf]

Maybe you should increase size of array np[][], and use %d in scanf (%i treats integers with leading zeroes as octal, and that could hurt here.)

[shanto86]

well one more thing, u forgot to add '\n'

[mf]

well one more thing, u forgot to add '\n'

No, puts() does that automatically.

[david]

I have tried changing %i to %d, but to no avail. Increasing the size of np is unneccessary, although I have tried that as well, just in case.
As for \n, there is none missing. puts() always inserts \n at the end.
I really have no idea what is going on. Can someone check that the answer is sometimes >= 2^32? What to do in those cases?

[mf]

Hmm, I've changed all %i -> %d, %lli -> %lld, np[101][128] -> np[128][128], and your source was accepted.

[jan_holmes]

my source code just use integer as a data type to store the result and it is got Accepted.... I think it is not the problem...

[david]

Maybe you should increase size of array np[][], and use %d in scanf (%i treats integers with leading zeroes as octal, and that could hurt here.)

Many thanks for that, just increasing the array size to 128 (or to 102, for that matter) worked. The problem was that, the way I have written the calcdp function I might set np[ly + 1][something] to zero, which is out of bounds.

[rimu]

i am getting WA, i've tried to figure out what is
going wrong, but failed. can someone test some tricky
cases for which my code produces wrong answer?
thanks

Code: Select all

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

void main()
{
	int i, j, k, n, w, h;
	char a[110][110];
	long b[110][110];

	while ( scanf( "%d %d", &w, &h ) && ( w || h ) )
	{
		scanf( "%d", &n );

		memset( a, 0, sizeof( a ) );
		memset( b, 0, sizeof( b ) );

		for ( i = 0; i < n; ++i )
		{
			scanf( "%d %d", &j, &k );
			a[j][k] = 1;
		}

		b[0][0] = 1;

		for ( i = 0; i <= h; ++i )
		{
			for ( j = 0; j <= w; ++j )
			{
				if ( !a[i][j] )
				{
					if ( i - 1 > -1 && !a[i - 1][j] )
					{
						b[i][j] += b[i - 1][j];
					}

					if ( j - 1 > -1 && !a[i][j - 1] )
					{
						b[i][j] += b[i][j - 1];
					}
				}
			}
		}

		if ( b[w][h] == 0 )
		{
			printf( "There is no path.\n" );
		}
		else if( b[w][h] == 1 )
		{
			printf( "There is one path from Little Red Riding Hood's house to her grandmother's house.\n" );
		}
		else
		{
			printf( "There are %ld paths from Little Red Riding Hood's house to her grandmother's house.\n", b[w][h] );
		}
	}
}

[rimu]

my code above shows long data type for number of paths
but i've tried long long also, but WA nevertheless!!!

[mf]

Code: Select all

for ( i = 0; i <= h; ++i )
{
   for ( j = 0; j <= w; ++j ) 

I think, h and w are in the wrong order in this part of your code.

[ayeshapakhi]

i would be very greatful to u if u help me fixing bug.....
i'm getting fed up with continous WA....
here's the code.........

Code: Select all

////removed after AC

		for(i=0; i<=w; i++)
		{
			for(j=0; j<=h; j++)
			{
			}
		}		
		

thanks for any help...... it would be nice if u provide me some critical i/o...

[shanto86]

well... i am not sure, but u wrote: inf=-2^32

well, ^ it is XOR. but it might not be error....

look, u used sometimes a[j] and sometimes a[j] it might be problem