• 103

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.



Given a W×H image, with W and H both even, we define its photo booth transformation as the image obtained after the following process:
- Divide the image into 2×2 blocks (which is possible as both dimensions are even);
- Build four W/2×H/2 images by gathering the top-left pixels of each block into one image (following the blocks ordering) and similarly the top-right / bottom-left / bottom-right pixels into three other images;
- Glue together these four images (following the inside-block ordering) to obtain a new W×H image.

Example: 6×4 image
┌──────┐      ┌──┬──┬──┐      ┌───┬───┐      ┌──────┐
│MNOPQR│ ~> ├──┼──┼──┤ ~> ├───┼───┤ ~> │GIKHJL│
└──────┘ │ST│UV│WX│ │SUW│TVX│ └──────┘
└──┴──┴──┘ └───┴───┘
This transformation results in an image which contains four reduced versions of the original image, though none of them have a single a pixel in common (each of them contains exactly 1/4 of the original pixels).


Iterating this transform from a given image always brings us back to the original image after a (positive) number of steps that we call a period of the image.

Given some even dimensions W and H, what is the minimum period common to all W×H images?

Back to the example: Assuming all pixel values are distinct, we have:
┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐
└──────┘ └──────┘ └──────┘ └──────┘ └──────┘
Hence the minimum period is 4.

Additional illustrations (and references in French):
Line 1: One single integer T for the number of testcases to follow.
Next T lines: Two space-separated integers Wi and Hi corresponding to the width and height of the image.
T lines: One single integer corresponding to the period of the photo booth map on Wi×Hi images.
1 ≤ T ≤ 10
2 ≤ W, H ≤ 2000
Both W and H are even.
6 4
4 6

A higher resolution is required to access the IDE