1999 Canadian Computing Competition, Stage 1

Problem 3: Divided Fractals

A fractal is a geometrical object with the property that subsections of the object appear identical to (but smaller than) the whole object. Here we consider a specific fractal, which we will approximate by iterating a construction process.

Start with a filled square whose side length is 1. For example:

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

Remove a square of side 1/3 from the middle:

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

Note that this figure is equivalent to 8 squares of size 1/3, as illustrated below. The spaces between squares are for illustration only and do not appear in the fractal.

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

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

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

We can apply this process again to each of the squares. Thus after 2 iterations of the construction process, we have:

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

Each of the eight squares is now a copy of the first iteration. Each of these contains eight filled squares, for a total of 64. The process is applied to each of these squares. After 3 iterations we have:

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

The actual fractal is what we get when this process is iterated infinitely many times. As one might expect, each of the 8 subsections of this fractal is an exact copy of the fractal, scaled by a factor of a third.

Write a program to compute the specified function after n iterations (n ≤ 5). To do this, represent the figure as a 3ⁿ by 3ⁿ grid, with '*' to indicate filled areas and ' ' to indicate unfilled areas. The figure will be too large to print on a single screen or sheet of paper so the input will specify a small rectangular portion of the figure to be printed.

Input

The first line of input contains a positive integer d, indicating the number of test data sets to follow.
Each data set consists of five lines containing:

• n, the number of iterations (0 ≤ n ≤ 5)
• b, the bottom row of the rectangle to be printed (1 ≤ b ≤ 3ⁿ)
• t, the top row of the rectangle to be printed (b ≤ t ≤ 3ⁿ )
• l, the left column of the rectangle to be printed (1 ≤ l ≤ 3ⁿ )
• r, the right column of the rectangle to be printed (l ≤ r ≤ 3ⁿ )

Note that rows are numbered from bottom to top and columns from left to right.

Output

Compute the figure and print the specified rectangular portion, with one line of output per row. Print the top row first, and the bottom row last. To make the output appear square, leave a single horizontal space between row elements (as is done in the examples above). Leave a blank line in the output after every test case.

Sample Input

1
3
2
10
5
27

Sample Output

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

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 01, 2008

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

Comments (Search)