Printable View
How would I be able to solve the problem given on this URL?
DWITE - October 2010 - Power Tiles
By the way dwite is a programming contest for middle/highschools, this was from the last contest and we had no clue what to do.
I know how to do the input/output files, and powers of 2. But I don't know how to determine the minimum number of tiles.
Interesting little problem.
Hint #1: the number of tiles required will be minimum when tiles are chosen with maximum possible area.
I've thought about that but I don't think it works.
In the example, for a 5 by 6 floor. One 4 by 4, two 2 by 2, and six 1 by 1 tiles are chosen. These add up to 9 tiles.
If I make a program that chooses tiles with the maximum possible area I will get this.
One 4 by 4, 16 out of 30 is filled, 14 possible spaces are left
three 2 by 2, (3 * 4) 12 out of 14, 2 spaces are left
and finally two 1 by 1. Mine will add up to 6 tiles.
These don't match because my tiles won't fit a 5 by 6 floor, however they will have the same area as a 5 by 6 floor.
Exactly! So we can conclude it is not just a numbers game, but we have to take into account the geometry, right?Quote:
Originally Posted by Neox
So, when we place the 4 x 4 tile on the 5 x 6 floor, we effectively subdivided the original square into a number of distinct regions (1 square occupied 4 x 4 tile, and 1 non-square region). Now the problem has shifted towards how to partition the non-square region, and we are left with the original problem we just solved (recursion/iteration anyone?).
ugh.. I just can't seem seem to figure out how to partition the non-square region
#
#
#
#
#####
#####
trust me I've tried... I'm getting nowhere
Instead of thinking of the tile as blotting out a rectangular area of the floor, imagine that the two of the sides of this rectangle, when extended to the boundaries of the floor, actually partition the floor in *four* *rectangular* regions.Quote:
Originally Posted by Neox