352 - The Seasonal War

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

Moderator: Board moderators

Betovsky
New poster
Posts: 26
Joined: Wed Jun 05, 2002 7:30 pm
Location: Portugal

352 The Seasonal War

Post by Betovsky » Wed Jun 12, 2002 4:54 am

hmm in this prob
this case
101
010
101

are 5 planes or only 1 plane?

Betovsky
New poster
Posts: 26
Joined: Wed Jun 05, 2002 7:30 pm
Location: Portugal

Post by Betovsky » Wed Jun 12, 2002 6:14 am

dam to the samples it works great
but the judge keeps saying WA can some1 tell me whta wrong

[c]

#include <stdio.h>
#include <stdlib.h>

void init(void);
void check(int, int);

int a[27][27];

int main(){
int image=0;
int linha;
int n, k;
int i, j;

while(scanf("%d", &n) != EOF){
image++;
init();
k=0;

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


for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[j]==1){
k++;
a[j]=2;
check(i,j);
}

printf("Image number %d contains %d war eagles.\n", image, k);
}
return 0;
}

void init(){
int i,j;

for(i=0;i<27;i++)
for(j=0;j<27;j++)
a[j]=0;
}

void check(int is, int js){
int i,j;

for(i=is-1;i<=is+1;i++)
for(j=js-1;j<=js+1;j++)
if(a[j]==1){
a[j]=2;
check(i,j);
}
}

[/c]

thx... sorry for the trouble.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Wed Jun 12, 2002 7:34 pm

your only problem is the following code:
[c]
for(i=1;i<=n;i++){
scanf("%d", &linha);
for(j=1;j<=n;j++){
a[j]=linha%10;
linha=linha/10;
}
}
[/c]

use a char array, not an int, think about a 25 long string..... 111111111111111111 etc, it loses the precision you need.

Betovsky
New poster
Posts: 26
Joined: Wed Jun 05, 2002 7:30 pm
Location: Portugal

Post by Betovsky » Wed Jun 12, 2002 10:22 pm

Gracias , my head was starting to disintegrates...

i was starting to think of throwing my self over a bridge.

Derk
New poster
Posts: 23
Joined: Mon Mar 17, 2003 3:53 am
Location: Louisville, KY
Contact:

352 - The Seasonal War

Post by Derk » Thu Mar 20, 2003 12:40 am

For some reason, my 352 keeps getting WA. It's virtually identical to other problems I've solved such as 572 and 260. I've thrown every piece of test input I can think at it. Tested boundary conditions, etc. Here's the input I'm working with and corresponding output:

5
10001
00000
00000
00000
10001
6
100100
001010
000000
110000
111000
010100
8
01100101
01000001
00011000
00000010
11000011
10100010
10000001
01100000
2
01
10
2
11
11
1
1
1
0
3
101
010
101
4
0000
0100
0001
0000
4
1000
0010
1000
0010
0
0
0
5
10101
01010
10101
01010
10101
And the output:
Image number 1 contains 4 war eagles.
Image number 2 contains 3 war eagles.
Image number 3 contains 6 war eagles.
Image number 4 contains 1 war eagles.
Image number 5 contains 1 war eagles.
Image number 6 contains 1 war eagles.
Image number 7 contains 0 war eagles.
Image number 8 contains 1 war eagles.
Image number 9 contains 2 war eagles.
Image number 10 contains 4 war eagles.
Image number 11 contains 0 war eagles.
Image number 12 contains 0 war eagles.
Image number 13 contains 0 war eagles.
Image number 14 contains 1 war eagles.
Is there some weird case that I'm just not considering? My array is well within the input size limit (I made it 50x50 just to test for large cases, and I initialize all elements to NULL).

If some suggested input from you all holds up, I'll post my program so you can see the algorithm I'm using.

Thanks![/quote]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Mar 20, 2003 8:54 am

I got the same output as yours and got Acc.
I use DFS to find number of war eagles on board and I use 25x25 board.
Maybe you have a small mistake in your code ?

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Derk
New poster
Posts: 23
Joined: Mon Mar 17, 2003 3:53 am
Location: Louisville, KY
Contact:

Hm

Post by Derk » Thu Mar 20, 2003 10:37 am

What is DFS?

Anyway, here's my code:

[c]/* @JUDGE_ID: xxxxxxx 352 C*/
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>

#define BUFFERSIZE 27

char buffer[BUFFERSIZE][BUFFERSIZE];

void check(int i, int j)
{
buffer[j]='0';

if(i > 0 && j > 0 && buffer[i-1][j-1] == '1')
check(i-1,j-1);
if(i > 0 && buffer[i-1][j] == '1')
check(i-1,j);
if(i > 0 && buffer[i-1][j+1] == '1')
check(i-1,j+1);
if(j > 0 && buffer[j-1] == '1')
check(i,j-1);
if(buffer[j+1] == '1')
check(i,j+1);
if(j > 0 && buffer[i+1][j-1] == '1')
check(i+1,j-1);
if(buffer[i+1][j] == '1')
check(i+1, j);
if(buffer[i+1][j+1] == '1')
check(i+1,j+1);
}

main()
{
int a,cnt=1,i,j,war;

#ifndef ONLINE_JUDGE
close (0); open ("352.in", O_RDONLY);
close (1); open ("352.out", O_WRONLY | O_CREAT, 0600);
#endif

while(gets(buffer[0]))
{
a = atoi(buffer[0]);

war = 0;
if (a != 0)
{
for(i=0;i<BUFFERSIZE;i++)
for(j=0;j<BUFFERSIZE;j++)
buffer[j] = 0x00;

for(i=0;i<a;i++)
gets(buffer);

for(i=0;i<BUFFERSIZE;i++)
for(j=0;j<BUFFERSIZE;j++)
if(buffer[j] == '1')
{
war++;
check(i,j);
}
}

printf("Image number %d contains %d war eagles.\n", cnt++, war);
}

}

/* @END_OF_SOURCE_CODE */[/c]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Mar 20, 2003 12:34 pm

DFS - Depth First Search
Your algorithm looks good :) I use the same and I think, that I could say that it's kind of DFS...

Dominik

PS. Try to change

Code: Select all

                        for(i=0;i<BUFFERSIZE;i++)
                                for(j=0;j<BUFFERSIZE;j++)
                                        if(buffer[i][j] == '1')
                                        {
                                                war++;
                                                check(i,j);
                                        }
to

Code: Select all

                        for(i=0;i<BUFFERSIZE-1;i++)
                                for(j=0;j<BUFFERSIZE-1;j++)
                                        if(buffer[i][j] == '1')
                                        {
                                                war++;
                                                check(i,j);
                                        }
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Mar 20, 2003 1:04 pm

Use scanf instead of gets, then you will get Accepted.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Mar 20, 2003 1:23 pm

That means, that at end of line are some additional spaces ?
I don't like such traps .... But Adrian has right - I use scanf too ... :)

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Derk
New poster
Posts: 23
Joined: Mon Mar 17, 2003 3:53 am
Location: Louisville, KY
Contact:

Cool

Post by Derk » Thu Mar 20, 2003 8:14 pm

Made both changes, got accepted. Thanks a ton. But, can you explain why this happened? I mean, in the other problems I've solved I use fgets/gets almost exclusively. Sometimes I use scanf, when it's unnecessary to have a character buffer at all.

I should have known DFS... I just took a class on AI hehe. :oops:

Thanks once again!

User avatar
Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

You were right!!

Post by Carlos » Sat Jun 07, 2003 6:34 pm

Hi!
I'm one of the judge administrators...I've checked problem #352 and you were right! There was an extra empty line at the end of the input! That's not an impossible test case, and it's not there on purpose.
Whenever you notice something like that, please mail us to problemset@acm.uva.es! I can't read the whole topics in here...
I've changed the input, and I'm rejudging all submissions...
Sorry about the mistake.
Carlos.

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Fri Oct 17, 2003 11:35 am

is it correct ?? i'm still confused .... any body have another sample input ? i've tried sample input at this thread before, and its exactly the same, but it's still WA... help

Code: Select all

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

int jml,idx;
char d1[30][30];
int b,k;
int eagle;
int no=0;
void main()
{
	#ifndef ONLINE_JUDGE
		freopen ("352.in","r",stdin);
		freopen ("352.out","w",stdout);
	#endif

	while (scanf ("%d ",&jml)!=EOF)
	{
		no++;
		eagle=0;
		for (idx=0;idx<jml;idx++)
		{
			scanf ("%s ",&d1[idx]);
		}

		for (b=0;b<jml;b++)
		{
			for (k=0;k<jml;k++)
			{
				if (d1[b][k]=='1')
				{
					d1[b][k]='2';
					if ((b-1)>=0 && (k-1) >=0 && d1[b-1][k-1]=='2')
					{
					}
					else if ((b-1)>=0 && d1[b-1][k]=='2')
					{
					}
					else if ((b-1)>=0 && (k+1)<jml && d1[b-1][k+1]=='2')
					{
					}
					else if ((k-1)>=0 && d1[b][k-1]=='2')
					{
					}
					else if ((k+1)<jml && d1[b][k+1]=='2')
					{
					}
					else if ((b+1)<jml && (k-1)>=0 && d1[b+1][k-1]=='2')
					{
					}
					else if ((b+1)<jml && d1[b+1][k]=='2')
					{
					}
					else if ((b+1)<jml && (k+1)<jml && d1[b+1][k+1]=='2')
					{
					}
					else
					{
						eagle++;
					}


					if ((b-1)>=0 && (k-1) >=0 && d1[b-1][k-1]=='1')
					{
						d1[b-1][k-1]='2';
					}
					else if ((b-1)>=0 && d1[b-1][k]=='1')
					{
						d1[b-1][k]='2';
					}
					else if ((b-1)>=0 && (k+1)<jml && d1[b-1][k+1]=='1')
					{
						d1[b-1][k+1]='2';
					}
					else if ((k-1)>=0 && d1[b][k-1]=='1')
					{
						d1[b][k-1]='2';
					}
					else if ((k+1)<jml && d1[b][k+1]=='1')
					{
						d1[b][k+1]='2';
					}
					else if ((b+1)<jml && (k-1)>=0 && d1[b+1][k-1]=='1')
					{
						d1[b+1][k-1]='2';
					}
					else if ((b+1)<jml && d1[b+1][k]=='1')
					{
						d1[b+1][k]='2';
					}
					else if ((b+1)<jml && (k+1)<jml && d1[b+1][k+1]=='1')
					{
						d1[b+1][k+1]='2';
					}

				}
			}
		}
		printf ("Image number %d contains %d war eagles.\n",no,eagle);

	}
}
[/code]
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Mon Oct 20, 2003 2:04 am

sorry, my algorithm was wrong... i should've used recursive to solve this problem (but i didn't, cause i want to prove that i can solve this problem using iteration not recursive)...

to any body who still have WA , i suggest you to check with this sample input :

INPUT :

5
00000
01010
01010
01110
00000

OUTPUT :
Image number 1 contains 1 war eagles.



my code worked well except for this kind of input, but i've already got an AC for this problem ^_^ V (and also for 572 , its all the same)
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

duaxorms
New poster
Posts: 5
Joined: Sat Jul 05, 2003 7:53 am
Location: Korea
Contact:

352 - The Seasonal War

Post by duaxorms » Sat Jan 10, 2004 10:59 am

For some reason, my 352 keeps getting WA. I've thrown every piece of test input I can think at it. Tested boundary conditions, etc.
I don't know what is wrong......

here my code
[cpp]
#include <iostream.h>
#include <stdio.h>

int anal(int len);
void con(int i, int j);

int image[28][28];

int main()
{
int testnum=0;
int len;
while(scanf("%d", &len) != EOF)
{
int i, j, temp;
testnum++;

for(i=0; i<=28; i++)
for(int j=0; j<=28; j++)
image[j] = 0;

for(i=1; i<=len; i++)
{
scanf("%d", &temp);
for(j=len; j>=1; j--)
{
image[j] = temp % 10;
temp = temp / 10;
}
}
cout << "Image number " << testnum << " contains " << anal(len) << " war eagles." << endl;
}
return 0;
}

int anal(int len)
{
int i, j, count=0;

for(i=1; i<=len; i++)
for(j=1; j<=len; j++)
{
if(image[j]==1)
{
con(i, j);
count++;
}
}
return count;
}

void con(int i, int j)
{
image[j] = 0;

if(image[i-1][j-1] == 1)
con(i-1, j-1);
if(image[i-1][j] == 1)
con(i-1, j);
if(image[i-1][j+1] == 1)
con(i-1, j+1);
if(image[j-1] == 1)
con(i, j-1);
if(image[j+1] == 1)
con(i, j+1);
if(image[i+1][j-1] == 1)
con(i+1, j-1);
if(image[i+1][j] == 1)
con(i+1, j);
if(image[i+1][j+1] == 1)
con(i+1, j+1);
}
[/cpp][/cpp]

Post Reply

Return to “Volume 3 (300-399)”