1999 Canadian Computing Competition, Stage 2

Day 1, Problem 3: Mandelzuma's Revenge

You may recall that in stage 1 of the CCC you were asked to calculate a region of a fractal obtained by starting with a square, dividing it into 9 sub-squares, then clearing the middle, like so:

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

This operation was then repeated for each of the 8 remaining sub-squares, and so on.

If we choose a different operation we get a different fractal; for example, we may clear the upper-left and lower-right corners instead of the middle. Or we may divide the square into a different number of sub-squares.

For this problem we will specify the fractal operation as an n by n grid of characters, where each character performs a particular substitution on the corresponding sub-square. The character . (period) indicates that the corresponding sub-square becomes completely empty. The character ! (exclamation mark) indicates that the corresponding sub-square becomes full and is not subject to further fractal operations. The character ? (question mark) indicates that the corresponding sub-square remains full and is subject to further fractal operations.

The fractal above would be represented by the 3 by 3 grid:

???
?.?
???

Four iterations of the fractal denoted by the 2 by 2 grid

.!
?.

would be:

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


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


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


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

Your mission, should you choose to accept it (like you have any choice!) is to print out a region of an arbitrary fractal specified by an n by n grid. Note that these fractals will get way too big to fit completely into memory, so some cleverness will be required to compute only the part to be printed. (Part marks can still be earned for programs that work only on small examples.)

Input

Output

Note: the checker for this problem is fairly strict. Make sure you have spaces in the right places and such...

Sample Input

2
.!
?.
3
2 8 1 7
-1

Sample Output

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

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 19, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Would anyone mind explaining the sample output for me? As I see it, it is showing columns 2-7 and rows 2-8, rather than columns 1-7 and rows 2-8. My program outputs

[code]
        * * *
        * * *
        * * *
        * * *
    * *
    * *
* *
[/code]

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

The sample output is correct. Note that though the problem statement alludes to four iterations in its example, the first one depicted is actually iteration 0. You are to output the result after executing k iterations, so your picture ignoring the output window should match the final figure.

Yeah, this is kind of sneaky. Pay close attention on contests, since this kind of clarification probably won't be given :P

Serves me right, I should actually read the problem statements next time >_<

Thanks!

I think there's an error in the spacing of the asterisks in the problem statement