Mount Allison Programming Showdown 2019


2019-03-16 08:00 AKDT

Mount Allison Programming Showdown 2019


2019-03-16 13:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -552 days 17:01:53

Time elapsed


Time remaining


Problem F
Fractal Area

The Circle-Square Fractal, or CS Fractal (which also goes by other names), is a simple two-dimensional fractal constructed in an iterative fashion out of solid circles of decreasing radii. As the construction proceeds, certain square regions become noticeable (in particular, the entire fractal), hence the “Square” part of the name.

The $1^{\mathrm{st}}$ iteration in the construction of the CS Fractal consists of a single circle of radius $r > 0$. In the $2^{\mathrm{nd}}$ iteration, this “parent” circle spawns four “child” circles of radius $r/2$ that are tangent to the parent circle in each of the north, south, east, and west directions. Now let $n \geq 3$. In the $n^{\mathrm{th}}$ iteration, each circle $C$ added in the $(n-1)^{\mathrm{st}}$ iteration spawns three child circles whose radii are exactly half of $C$’s radius, and that are tangent to $C$ in each of the three compass directions other than the direction in which $C$ touches its parent circle (here the compass directions are relatively to $C$). For example, in the $3^{\mathrm{rd}}$ iteration, the circle $C$ of radius $r/2$ that is north of the $1^\mathrm {st}$-generation circle spawns three circles of radius $r/4$ that touch $C$ in its west, north, and east directions. The illustration accompanying this problem depicts the CS Fractal after $6$ iterations. (Technically, the fractal is the shape generated after infinitely many iterations, but we informally use “fractal” to refer to the partially constructed shape after a finite number of iterations.)

Given the radius of the starting ($1^{\mathrm{st}}$-iteration) circle and the number of iterations, determine the area of the partially constructed fractal.

Note: Other than the single-point intersection between any child circle and its parent, no two circles in the fractal intersect.


The first line of input contains an integer $T$, the number of test cases ($1 \leq T \leq 50$). This is followed by $T$ lines, one per test case, each of which contains two space-separated integers, $r$ and $n$ ($1 \leq r \leq 200$, $1 \leq n \leq 50$), where $r$ is the radius of the starting ($1^{\mathrm{st}}$-iteration) circle and $n$ is the number of iterations.


For each test case, output the area of the partially constructed fractal with starting radius $r$ after $n$ iterations. Each computed area will be considered correct if it is within $10^{-6}$ of the official answer.

Sample Input 1 Sample Output 1
1 1
8 3