Help with solving this problem

This is a discussion on Help with solving this problem within the C++ Programming forums, part of the General Programming Boards category; How would I be able to solve the problem given on this URL? DWITE - October 2010 - Power Tiles ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    3

    Question Help with solving this problem

    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.

  2. #2
    Registered User
    Join Date
    Oct 2006
    Posts
    250
    Interesting little problem.

    Hint #1: the number of tiles required will be minimum when tiles are chosen with maximum possible area.
    iMalc: Your compiler doesn't accept misspellings and bad syntax, so why should we?
    justin777: I have no idea what you are talking about sorry, I use a laptop and there is no ascii eject or something

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    3
    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.

  4. #4
    Registered User
    Join Date
    Oct 2006
    Posts
    250
    Quote Originally Posted by Neox View Post
    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?

    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?).
    iMalc: Your compiler doesn't accept misspellings and bad syntax, so why should we?
    justin777: I have no idea what you are talking about sorry, I use a laptop and there is no ascii eject or something

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    3
    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

  6. #6
    Registered User
    Join Date
    Oct 2006
    Posts
    250
    Quote Originally Posted by Neox View Post
    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.
    iMalc: Your compiler doesn't accept misspellings and bad syntax, so why should we?
    justin777: I have no idea what you are talking about sorry, I use a laptop and there is no ascii eject or something

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM
  2. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  3. JOB: C/C++ Developer with problem solving skills
    By VoltRecruiter in forum Projects and Job Recruitment
    Replies: 1
    Last Post: 01-26-2006, 12:25 AM
  4. Replies: 5
    Last Post: 11-07-2005, 11:34 PM
  5. Sign-up Thread: Problem Solving #1
    By ygfperson in forum Contests Board
    Replies: 15
    Last Post: 01-26-2003, 02:55 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21