11067 - Little Red Riding Hood

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

Moderator: Board moderators

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

11067 - Little Red Riding Hood

Post by david » Sat Aug 12, 2006 7:12 pm

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


Last edited by david on Tue Aug 15, 2006 12:57 pm, edited 1 time in total.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sat Aug 12, 2006 7:35 pm

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.
Self judging is the best judging!

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sat Aug 12, 2006 7:42 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Aug 12, 2006 7:57 pm

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sat Aug 12, 2006 8:01 pm

well one more thing, u forgot to add '\n'
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Aug 12, 2006 8:03 pm

shanto86 wrote:well one more thing, u forgot to add '\n'
No, puts() does that automatically.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sat Aug 12, 2006 8:04 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Aug 12, 2006 8:12 pm

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

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sat Aug 12, 2006 8:15 pm

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
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sat Aug 12, 2006 8:39 pm

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.

rimu
New poster
Posts: 9
Joined: Sat Feb 26, 2005 4:41 pm

Post by rimu » Sun Aug 13, 2006 6:01 am

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] );
		}
	}
}
i'll be back

rimu
New poster
Posts: 9
Joined: Sat Feb 26, 2005 4:41 pm

Post by rimu » Sun Aug 13, 2006 6:08 am

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Aug 13, 2006 6:15 am

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
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

11067 getting repeated WA help pls

Post by ayeshapakhi » Sun Aug 13, 2006 8:58 pm

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...
Last edited by ayeshapakhi on Tue Aug 15, 2006 6:38 am, edited 2 times in total.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun Aug 13, 2006 9:20 pm

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
Self judging is the best judging!

Post Reply

Return to “Volume 110 (11000-11099)”