## 447 - Population Explosion

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

Moderator: Board moderators

gracia
New poster
Posts: 5
Joined: Mon Nov 25, 2002 9:04 am
Location: jakarta

### 447 - Population Explosion

if u look at sample input in 447
u can see that there is no condition to end the input
so how can i end the input????
or may be i have to use freopen()
but i have tried it and got restricted function
can u help me ?

off_algos
New poster
Posts: 29
Joined: Wed Nov 13, 2002 11:37 am
Location: india
the p447 is a multiple input problem with each input segment ending with a '\n' and the fianl input ending with the EOF
and never use any file opening or closing functions as u r not supposed to use them
try .. and good luck!!

yyjjee
New poster
Posts: 1
Joined: Fri Jul 18, 2003 9:32 am
Location: Taiwan

### 447 WA~~

This problem is look like a very simple simulated problem~~
But i always get WA
i noticed the mutiple input , but still get WA
can someone give me some hint or some tricky input ??

Thx in advance

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

### 447- WA Why..

This problem seems to be very simple. all i have to do is run the simulation of the game of life evolution.. But i got a WA.. ANy trick inputs that might make me get a WA.. I am also posting the code.. Plz help me out guys with my code .... Or tell me any approach u used....

Thx
Aakash

[cpp]

# include<stdio.h>

char s[100];
char a[20][20][2];

int flag;

int readline()
{
int p=0;
char ch;

ch=fgetc(stdin);
while(ch!='\n' && ch!='\r' && ch!=EOF)
{
s[p++]=ch;
ch=fgetc(stdin);
}
s[p]=0;
return p;
}

void starline()
{
for(int i=0;i<20;i++) printf("*");
printf("\n");
}

void calc()
{
int nc;

for(int i=0;i<20;i++)
{
for(int j=0;j<20;j++)
{
nc=0;
if(i>0 && j>0 && a[i-1][j-1][flag]=='O') nc++;
if(i>0 && j<20 && a[i-1][j+1][flag]=='O') nc++;
if(i>0 && a[i-1][j][flag]=='O') nc++;

if(i<20 && j<20 && a[i+1][j+1][flag]=='O') nc++;
if(i<20 && j>0 && a[i+1][j-1][flag]=='O') nc++;
if(i<20 && a[i+1][j][flag]=='O') nc++;

if(j>0 && a[j-1][flag]=='O') nc++;
if(j<20 && a[j+1][flag]=='O') nc++;

if(a[j][flag]==' ' && nc==3) a[j][!flag]='O';
else if(a[j][flag]=='O' && (nc==3 || nc==2) ) a[j][!flag]='O';
else a[j][!flag]=' ';
}
}
flag=!flag;
}

int main()
{
int i,j,x,y,n,nt;

scanf("%d",&nt);
while(nt--)
{
flag=0;
scanf("%d",&n);
for(i=0;i<20;i++) for(j=0;j<20;j++) a[j][flag]=' ';
fgetc(stdin);
while(readline())
{
sscanf(s,"%d%d",&x,&y);
a[x-1][y-1][flag]='O';
}

starline();
for(int ix=0;ix<n;ix++)
{

for(i=0;i<20;i++)
{
for(j=0;j<20;j++)
{
printf("%c",a[j][flag]);
}
printf("\n");
}
calc();
starline();
}
if(nt) printf("\n");
}
return 1;
}

[/cpp]
...I was born to code...

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Hi,

I've got the same problem - Wrong Answer.

I'm rather sure that the simulation itself is ok because I've tested it with
dozens of available configurations including 'eaters' and 'gliders'. so maybe the problem is the output format?

Right now my output format is as follows:

Code: Select all

``````********************                  <- start
20 lines                               <- city 1, generation 1
********************
20 lines                               <- city 1, generation 2
********************
20 lines                               <- city 1, generation 3
********************
20 lines                               <- city 1, generation 4
********************
20 lines                               <- city 1, generation 5
********************
20 lines                               <- city 1, generation 6
<- one empty line to separate cities
20 lines                               <- city 2, generation 1
********************
20 lines                               <- city 2, generation 2
********************
20 lines                               <- city 2, generation 3
********************                  <- end
``````
There's another item I'm not one hundred percent sure of. If the starting configuraton moves, what does happen at the borders? The original game behaves somewhat like a sphere. But here the problem statement mentions 'enclosed cities'.

So how do you handle moving configurations like

Code: Select all

``````  O
O
OOO
``````
?
Last edited by WR on Wed May 26, 2004 7:58 am, edited 1 time in total.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
WR:

[c]********************
20 lines <- city 1, generation 6
********************
<- one empty line to separate cities
********************
20 lines <- city 2, generation 1
******************** [/c]

aakash_mandhar:

I found this input:
[c]1

2
16 20
17 1
19 1[/c]

which should output:
[c]********************

O
O

O

********************

********************[/c]

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Thanks UFP2161 for the quick response!

Unfortunately it doesn't help as my program outputs the expected result.

I still think the problem isn't the simulation itself but rather the output format. Maybe you have an example with two cases or more??!!

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
[c]2

1
5 4
5 5
5 6
5 7

1
5 4
5 5
5 6
5 7[/c]

[c]********************

OOOO

******************** <-- here

******************** <-- and here

OOOO

********************[/c]

From your description of your output, you don't print the asterisks between the two test cases.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Thanks a lot,

that really helps.

You're right, I don't print a starred line between cases because the problem statement said to print starred lines at the beginning and the end of the input and between years and an empty line between cases. I took
that literally.

added later:

Ok, now my output looks like yours, but still WA. So I was too confident as to the simulation.

With an input file like

Code: Select all

``````2

90
1 4
1 5
1 6
2 6
3 5

20
5 5
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
6 5
6 6
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
7 5
7 6
7 7
7 8
7 9
7 10
7 11
7 12
7 13
7 14
8 5
8 6
8 7
8 8
8 9
8 10
8 11
8 12
8 13
8 14
9 5
9 6
9 7
9 8
9 9
9 10
9 11
9 12
9 13
9 14
10 5
10 6
10 7
10 8
10 9
10 10
10 11
10 12
10 13
10 14
11 5
11 6
11 7
11 8
11 9
11 10
11 11
11 12
11 13
11 14
12 5
12 6
12 7
12 8
12 9
12 10
12 11
12 12
12 13
12 14
13 5
13 6
13 7
13 8
13 9
13 10
13 11
13 12
13 13
13 14
14 5
14 6
14 7
14 8
14 9
14 10
14 11
14 12
14 13
14 14
``````
my program prints

(just the first and the last year for each case)

Code: Select all

``````********************
OOO
O
O

********************

O
OO
O O
********************

********************

OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO

********************

OO
O  O
O  O
OO

********************
``````
Could you verify this, please?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
For the first one, I got this after the 4th generation, which stays stable until forever:
[c]********************
OO
OO

********************[/c]

My second output matches yours (it goes into that stable state 3 generations before the last one).

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Thanks again,

I haven't changed my program yet, but now the reason for the Wrong Answer seems obvious. The second figure always remains within the 20x20 cells limit while the first one (a "glider") eventually disappears at the northern border and reappears at the southern border. In this problem it shouldn't do that as the borders are "closed".

Ok, accepted!

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

### 447 in C WA help need I/O --- samples many

I'm sure that the simulation is ok because I've tested it with configurations like 'eaters' and 'gliders'. so maybe the problem is the output or input format? i readed the posted before and the inputs are good
[c]
CUT

[/c]

P.S. i know that the code is too long but i only want to know how is the input and the ouput if i have to read all the cases an then print the solution for each case or read one case and show the solution and then untill get EOF
Last edited by Ghust_omega on Mon Sep 06, 2004 11:00 am, edited 1 time in total.

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Please help me I only need I/O this programs runs ok in my cpu, I/O help me

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
hm, i haven't taken the time to reason through your code because it is so long (why so complicated?). my ac code is only 51 lines (of which 3 are just method declarations and 15 others just have a }).

do you have email for me to send you I/O? or if you use AIM/MSN messenger i am MinilekDOC on AIM and minilekx@hotmail.com on MSN messenger. each year's report takes 20 lines to print, so printing on the board i think may take too much space. i would much rather just send you an .in and .out file.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
here's some shorter I/O. you can email/message me if you want more though. warning: I got PE on this problem so when you check your output against mine you should ignore extra whitespace (i'm not quite sure why i got PE. anyone see why?)

Input:

Code: Select all

``````2

5
1 1
1 2
2 1
20 19
20 20
19 20
18 20
5 4
5 6
4 5
10 10
10 11
10 12

5
13 10
3 10
9 16
12 2
18 11
17 8
4 13
16 19
16 20
20 13
3 1
11 3
17 14
7 14
4 11
15 19
4 3
8 15
11 7
19 10
15 12
10 2
3 7
19 6
8 8
20 7
1 19
19 11
2 4
17 20
15 6
12 9
2 15
19 2
3 15
15 5
7 20
20 15
13 9
4 12
18 2
5 13
9 12
18 9
17 9
4 4
9 3
2 2
4 15
13 3
16 8
15 7
17 19
10 19
7 3
15 9
2 16
8 11
10 9
8 4
10 7
19 16
7 4
19 7
16 11
6 4
15 16
1 16
7 12
1 8
16 14
14 19
1 1
18 16
6 19
7 10
8 3
3 2
7 11
8 17
8 13
1 20
11 11
1 2
3 8
2 13
17 12
19 17
4 10
17 5
9 1
1 9
20 2
14 20
2 14
9 4
2 18
10 1
1 7
2 5

``````
Output:

Code: Select all

``````********************
OO
O

O
O O

OOO

O
O
OO
********************
OO
OO

O
O

O
O
O

O
OO
********************
OO
OO

OOO

OO
OO
********************
OO
OO

O
O
O

OO
OO
********************
OO
OO

OOO

OO
OO
********************

********************
OO    OOO      O  OO
O OO       OOOO O
OO    OO O    O
OO     OOOO O
O
O              O
OO     OOO O     O
OO   O  O O O O
O OO       O   O
OO    O O         O
O   O   O
O      O
O     OO
OO
OOO O  O   O  O
O  O  O    OO
O  OO  O O    OO
O      O O    O
O   OO  OO    OO
O    O     O O
********************
OOO    O     O OO O
O       O OO O
OO  O   OO
OO     OOOOO
OO      O OO
OO      OOO
O    OOOOO
O    O  OOOO
O  O   O   O   O
O  O   O
O O      O
OO    OO
OO
O OOO        OO
OOO         O
O    OOO  O  O
OO OOO O   OO
OO O OO  OOO
OOO  OOO OOO  OOO
OO        O
********************
O             OO
O     O      OO
OOO     O  OO
O       O   OO
O
O O
O    O
OO   OO     O
OO   O   OO O
O OO    O
O OO   O
OO    O
O
O   O        O
OO O         O
O   O  OO   O
OOOO   O O OOO
O   O          OO
O  O   OO O
O   O O  O   OOO
********************
OO
O O            OO
O O    OOO OOO
O          O O
OO
O
OO  OO
O  OO    O
OO     O
OO
O      OO
OOO  OO
O
OO
OO  O        OO
OO
OO OO   O  O  O
OO   O     OO O
OOO OOO OOO      O
OOO    O
********************
OO
O   O OOO
O       O OO OO
O      O OO  O
OO
O
OO  OO
OOO
O
O  O
OO
OO   O O
OOO OO
O O
OO
OOO   OO   OO
OOO O   OOOOOO
O        O    OO O
O OO OO       O O
O   O OO O
********************

``````
or maybe this got you?

Input:

Code: Select all

``````1

4
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
3 19
3 20
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
4 20
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 17
5 18
5 19
5 20
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 19
6 20
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 16
7 17
7 18
7 19
7 20
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
8 11
8 12
8 13
8 14
8 15
8 16
8 17
8 18
8 19
8 20
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
9 18
9 19
9 20
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
10 11
10 12
10 13
10 14
10 15
10 16
10 17
10 18
10 19
10 20
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
11 11
11 12
11 13
11 14
11 15
11 16
11 17
11 18
11 19
11 20
12 1
12 2
12 3
12 4
12 5
12 6
12 7
12 8
12 9
12 10
12 11
12 12
12 13
12 14
12 15
12 16
12 17
12 18
12 19
12 20
13 1
13 2
13 3
13 4
13 5
13 6
13 7
13 8
13 9
13 10
13 11
13 12
13 13
13 14
13 15
13 16
13 17
13 18
13 19
13 20
14 1
14 2
14 3
14 4
14 5
14 6
14 7
14 8
14 9
14 10
14 11
14 12
14 13
14 14
14 15
14 16
14 17
14 18
14 19
14 20
15 1
15 2
15 3
15 4
15 5
15 6
15 7
15 8
15 9
15 10
15 11
15 12
15 13
15 14
15 15
15 16
15 17
15 18
15 19
15 20
16 1
16 2
16 3
16 4
16 5
16 6
16 7
16 8
16 9
16 10
16 11
16 12
16 13
16 14
16 15
16 16
16 17
16 18
16 19
16 20
17 1
17 2
17 3
17 4
17 5
17 6
17 7
17 8
17 9
17 10
17 11
17 12
17 13
17 14
17 15
17 16
17 17
17 18
17 19
17 20
18 1
18 2
18 3
18 4
18 5
18 6
18 7
18 8
18 9
18 10
18 11
18 12
18 13
18 14
18 15
18 16
18 17
18 18
18 19
18 20
19 1
19 2
19 3
19 4
19 5
19 6
19 7
19 8
19 9
19 10
19 11
19 12
19 13
19 14
19 15
19 16
19 17
19 18
19 19
19 20
20 1
20 2
20 3
20 4
20 5
20 6
20 7
20 8
20 9
20 10
20 11
20 12
20 13
20 14
20 15
20 16
20 17
20 18
20 19
20 20

``````
Output:

Code: Select all

``````********************
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOO
********************
O                  O

O                  O
********************

********************

********************

``````