Page 1 of 2

11067 - Little Red Riding Hood

Posted: Sat Aug 12, 2006 7:12 pm
by 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



Posted: Sat Aug 12, 2006 7:35 pm
by 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.

Posted: Sat Aug 12, 2006 7:42 pm
by 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.

Posted: Sat Aug 12, 2006 7:57 pm
by 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.)

Posted: Sat Aug 12, 2006 8:01 pm
by shanto86
well one more thing, u forgot to add '\n'

Posted: Sat Aug 12, 2006 8:03 pm
by mf
shanto86 wrote:well one more thing, u forgot to add '\n'
No, puts() does that automatically.

Posted: Sat Aug 12, 2006 8:04 pm
by 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?

Posted: Sat Aug 12, 2006 8:12 pm
by mf
Hmm, I've changed all %i -> %d, %lli -> %lld, np[101][128] -> np[128][128], and your source was accepted.

Posted: Sat Aug 12, 2006 8:15 pm
by 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...

Posted: Sat Aug 12, 2006 8:39 pm
by david
mf wrote: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.

Posted: Sun Aug 13, 2006 6:01 am
by 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] );
		}
	}
}

Posted: Sun Aug 13, 2006 6:08 am
by rimu
my code above shows long data type for number of paths
but i've tried long long also, but WA nevertheless!!!

Posted: Sun Aug 13, 2006 6:15 am
by 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.

11067 getting repeated WA help pls

Posted: Sun Aug 13, 2006 8:58 pm
by 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...

Posted: Sun Aug 13, 2006 9:20 pm
by 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