CCC '04 J5 - Fractals

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 256M
Problem types
Canadian Computing Competition: 2004 Stage 1, Junior #5

A fractal is a geometric shape where the pattern of the whole shape is self-replicating at each subsection of the shape. A simple "block fractal" is shown below. At each stage of the fractal growth, every straight line in the fractal is divided into three equal parts. The first and last sections stay straight; the middle section contains a square "bump" which has the same height as the width of the middle section. (You will want to consider the four orientations of a line segment within the fractal. Depending upon which line segment is currently being generated, the bump may protrude up, down, left, or right.)

Suppose this fractal is drawn on a Cartesian plane, where (0, 0) is at the bottom left corner. Assume that in the example above, the bottom left point of the fractal is at (0, 1) and the bottom right point of the fractal is at (27, 1). For example the top of the Level 3 fractal is a line from (13, 14) to (14, 14).

Write a program that will keep track of the integer coordinate points of the lines in a similar "block fractal" with its bottom left corner at (0, 1). The program will accept three integers as input: the level of the fractal, the width of the fractal, and an x-coordinate. You may assume that the width of the fractal will be some power of three, and that it will be large enough so that every corner of the fractal will fall on an integer intersection in the Cartesian plane. The width will never be more than 81. The x-coordinate, x, will be in the range 0 – width (inclusive). Your program should output the y-coordinate value(s), y, where lines of the fractal intersect the point (x, y).

You may draw a graphic representation of the fractal for debugging (and interest). However, test cases may ask you to define fractals that are too large to fit on a single screen.

Sample Input 1

3 27 5

Sample Output 1

4 5 6

Sample Input 2

3 27 18

Sample Output 2

1 2 3 4 7 8 9 10

Sample Input 3

2 27 19

Sample Output 3

1 4 7

Sample Input 4

4 81 38

Sample Output 4

37 38 39

Comments


  • 0
    fireheartjerry  commented on Jan. 3, 2023, 6:40 p.m.

    Note that if X is the level, and W is the width, then 0\le X \le \sqrt[3]W.


  • 2
    Subway_Man  commented on March 21, 2020, 5:14 p.m.

    Should output be sorted in ascending order?


    • 2
      noYou  commented on July 24, 2020, 9:18 p.m.

      Yes.


  • 1
    TheWrinklyCheese  commented on Jan. 22, 2018, 11:25 p.m.

    Judging from what level 3 looks like, wouldn't level four have blocks small than 1 part of grid? How would level four look like?


    • 3
      injust  commented on Jan. 23, 2018, 12:27 a.m.

      You may assume that the width of the fractal will be some power of three, and that it will be large enough so that every corner of the fractal will fall on an integer intersection in the Cartesian plane.