352 - The Seasonal War
Moderator: Board moderators
352 The Seasonal War
hmm in this prob
this case
101
010
101
are 5 planes or only 1 plane?
this case
101
010
101
are 5 planes or only 1 plane?
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.
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.
352 - The Seasonal War
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:
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]
And the 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
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).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.
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]
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
Hm
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]
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]
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
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
to
Your algorithm looks good
![:)](./images/smilies/icon_smile.gif)
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);
}
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)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
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 ...![:)](./images/smilies/icon_smile.gif)
Dominik
I don't like such traps .... But Adrian has right - I use scanf too ...
![:)](./images/smilies/icon_smile.gif)
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)
Born from ashes - restarting counter of problems (800+ solved problems)
Cool
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.
Thanks once again!
I should have known DFS... I just took a class on AI hehe.
![:oops:](./images/smilies/icon_redface.gif)
Thanks once again!
-
- System administrator
- Posts: 1286
- Joined: Sat Oct 13, 2001 2:00 am
- Location: Valladolid, Spain
- Contact:
You were right!!
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.
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.
-
- New poster
- Posts: 23
- Joined: Sat Oct 04, 2003 12:12 pm
- Location: in Your Heart ^^
- Contact:
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]
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);
}
}
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...
May every person helps each other and creates a world full of joy...
-
- New poster
- Posts: 23
- Joined: Sat Oct 04, 2003 12:12 pm
- Location: in Your Heart ^^
- Contact:
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)
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...
May every person helps each other and creates a world full of joy...
352 - The Seasonal War
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]
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]