CCC '11 S3 - Alice Through the Looking Glass - Olympiads Online Judge

CCC '11 S3 - Alice Through the Looking Glass

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2011 Stage 1, Senior #3

Alice is looking at a crystal through a microscope. Alice's microscope has the interesting feature that it can superimpose grid lines over the image that she is looking at.

At level 1 of magnification, Alice sees the image as follows:

Notice that at level 1, there is a $5 \times 5$ $5 \times 5$ grid superimposed over the image.

However, as Alice increases the magnification, the leaf pattern becomes more intricate.

At level 2 of the magnification, Alice sees the image with a $25 \times 25$ $25 \times 25$ grid, and notices that three of the four larger squares in the original image have the small four square pattern on top. In fact, for this particular crystal, this self-similarity repeats for each magnification level.

Given that Alice's microscope has up to 13 levels of magnification, she would like to try to quantify the detail of each grid cell at every one of these magnification levels.

Specifically, since there is a $5^m \times 5^m$ $5^{m} \times 5^{m}$ grid at magnification level $m$ $m$ , Alice will call the bottom-left corner grid cell $(0, 0)$ $(0, 0)$ , the bottom-right grid cell $(5^m - 1, 0)$ $(5^{m} - 1, 0)$ , the top-left grid cell $(0, 5^m - 1)$ $(0, 5^{m} - 1)$ , and the top-right grid cell $(5^m - 1, 5^m - 1)$ $(5^{m} - 1, 5^{m} - 1)$ .

Given an integer magnification level $m$ $m$ ( $1 \le m \le 13$ $1 \leq m \leq 13$ ) and a grid position $(x, y)$ $(x, y)$ (where $0 \le x < 5^m$ $0 \leq x < 5^{m}$ and $0 \le y < 5^m$ $0 \leq y < 5^{m}$ ), Alice would like to know if her crystal will fill that grid cell, or if that grid cell will be empty space.

Input Specification

The first line of input will be $T$ $T$ ( $0 < T \le 10$ $0 < T \leq 10$ ) which is the number of test cases. On each of the next $T$ $T$ lines there will be three integers: $m$ $m$ , the magnification level, followed by $x$ $x$ and $y$ $y$ , the position of the grid cell that Alice wishes to examine.

Output Specification

The output will be $T$ $T$ lines. Each line of output will either be empty, if the specified grid cell is empty, or crystal if that grid cell contains crystal.

Sample Input

Copy

Output for Sample Input

Copy

empty
crystal
crystal
crystal

Note: At least 40% of the test cases will have $m \le 4$ $m \leq 4$ .

Comments

1

Hiccup172 commented 74 days ago ← edited →

Fun fact! If ur really good at math you can create a formula to solve this problem (but not fully)! It also runs alot faster!

I just find this kinda fun...

-32

Moana commented on March 20, 2020, 3:22 a.m. ← edited →

(removed comment)

This comment is hidden due to too much negative feedback. Show it anyway.

1

ColonelBy_team10 commented on Oct. 30, 2021, 6:58 p.m.

it means you need to use recursion mate.

1

Tommy_Shan commented on Oct. 15, 2021, 7:36 p.m. ← edited →

Because you can use Recursion to solve it.

33

4fecta commented on June 18, 2019, 10:46 p.m. ← edited →

For $m = 3$ $m = 3$ , does the pattern recurse onto all of the non-encompassed squares on the top or only on the three local maximum squares?

7

ColonelBy_team10 commented on Oct. 30, 2021, 6:56 p.m.

Only on top of the three local maximum squares. If you don't implement that right, test 5 won't work.