![]() ( All of the input data is too large to place here, so please use the zip file. You can assume that there is at least one brick in the mosaic. Two bricks with the same letter representing it have the same color. Each character must either be '.' (representing a stud without any brick on top of it) or a capital letter (from 'A' to 'Z') representing a stud of a given color. The next R lines of input contain each exactly C characters detailing the mosaic to be built. ![]() The first line of input contains two integers R and C, indicating respectively the number of rows and columns of the mosaic to be built. ( You can download the zip file containing all of the input files here.) The bricks must be positioned in horizontal positions. Given the description of a lego mosaic, your task is to compute in how many different ways you can build that mosaic assuming you have an infinite pool of 1x1, 1x2, 1x3, 1x4, 1圆, 1x8, 1x10, 1x12 and 1x16 lego bricks, in any color. For example, the mosaic below has 16 different ways of using pieces to obtain the exact same image (with 'B' meaning a blue brick):įor a general case, can you tell in how many different ways you could build the desired mosaic? When you were starting the construction, you noticed that even with those constraints there were several different ways of building the mosaic. ![]() This means that when seen from the top, as in the textual representation above, the width of the bricks is varible, but the height is always 1. These are 1x1, 1x2, 1x3, 1x4, 1圆, 1x8, 1x10, 1x12 and 1x16 bricks, and are depicted in the figure below.įor aesthetical reasons, you only want to use the bricks in the horizontal positions, that is, parallel to the bottom of the plate. In particular, for the purposes of the mosaic, you can assume you have an infinite number of 9 different types of bricks (in any needed color). If we used text to represent a mosaic, with '.' representing a stud without a brick, 'R' for a red brick, 'Y' for a yellow brick and 'G' for a green brick, then the mosaic of the image below would be represented by:įor the construction of the mosaic you have available a very large set of 1xN bricks. Each lego stud is like a pixel in the image. The basic idea is to use a lego plate and on the top of it attach some lego bricks. You have been commissioned to build a large lego mosaic. Lego pieces are all about building things by assembling small pieces, and therefore they present the flexibility and versatility to create wonderful mosaics. You can download the original PDF file here.)īuilding mosaics is an art dedicated to the construction of images by assembling small pieces of some material. ( This problem was a part of the 2011 edition of the Portuguese Inter-University Programming Marathon. I'm sure the rest of the community will do their part. I won't be very active over the next few days, so I'm sorry if I can't help out as much as I'd like to. This one is either going to be really hard, or pretty accessible, depending on how comfortable you are with a certain Problem Solving method. I recommend reading the original PDF or at the gateway, as the problem is better formatted there. I used a problem from the Portuguese Inter-University Programming Marathon. Again, I was really busy this week, so I didn't have time to come up with a problem.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |