447 - Population Explosion

[gracia]

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]

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]

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]

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]

[WR]

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

?

[UFP2161]

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]

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]

[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]

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]

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]

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]

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

[Ghust_omega]

Please help me I only need I/O this programs runs ok in my cpu, I/O help me

[Minilek]

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]

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
********************
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
********************
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
********************