Thread: May monthly contest

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    May monthly contest

    Hi everyone, time for the next monthly contest. The rules are the same as before. Due date for all of these problems is May 15th. Due to popular demand, the problem difficulty has been scaled down a bit, but there is still an easy, medium, and hard problem. If you have any questions, please post in this thread instead of PMing me, that way anyone else who might have had the same question can see the answer. PM me with your code. Have fun and good luck!

    Easy Problem

    You are a cook during rush hour at a fast food restaurant. To cook a hamburger thoroughly, you must fry each side for five minutes. These five minutes do not have to happen concurrently so you can fry one side, let it sit for awhile off to the burner, then cook the other side at your leisure.

    Now, given the maximum number of hamburgers you can fit on your frying pan and the total number of hamburgers to cook, what is the minimum amount of minutes to cook all of the hamburgers thoroughly?

    Your function will have this format:

    int fryBurgers(int panSize, int numHamburgers)

    Parameters:

    • Pan size will be the number of hamburgers the pan can fit and will be between 1 and 1000
    • Number of hamburgers will be between 0 and 1000


    Examples
    • fryHamburgers(2,3) will return 15

      Call the hamburgers 1, 2, and 3. Cook hamburger 1 and 2 for 5 minutes. Take hamburger 1 off the pan and add hamburger 3 and flip hamburger 2. Cook for 5 minutes. Flip hamburger 3 and replace hamburger 2 with flip side of hamburger 1. Cook for 5 minutes. 15 minutes total and all 3 are cooked.

    • fryHamburgers(100,1) will return 10

      Big pan but only need to cook one burger. Cook one side for 5 minutes then cook other side for 5 minutes.

    • fryHamburgers(303,919) will return 35

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Medium Problem

    An interesting property for most integers is that if you continually add its value to the same number but with reversed digits, you will eventually get a number that is a palindrome. A palindrome is a number that can be read the same backwards and forwards, like 531135 or 676. For example if we take the number 195:

    195+591=786
    786+687=1473
    1473+3741=5214
    5214+4125=9339

    So after only four additions, 195 becomes a palindrome.

    Your task is to to write a function that takes in an integer and prints out the the number of additions it takes to create a palindrome as well as the resulting palindrome it creates.

    Your function will have this format:

    void palindrome(int k)

    Parameters:

    • k will be between 10 and 1000.
    • If the number of additions is greater than 10, then stop and print “No Solution”


    Examples
    • palindrome(195) will print “4 9339”

      Example above

    • palindrome(265) will print “5 45254”

    • palindrome(750) will print “3 6666”
    Last edited by PJYelton; 05-03-2005 at 10:06 AM.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Hard Problem

    A binary search tree is a data structure holding nodes that fit the following criteria if we assume no duplicate numbers: The child of a node is less than the node and the right child is always greater than the node. Here is a good page describing them more in detail: Binary Search Trees.

    Your task is given the number of nodes in the tree, return the number of possible binary trees that can be created.

    For example, if the tree has 3 nodes, then there are 5 possible trees that can be created. Here are all 5:
    Code:
      2       1         1          3     3 
     / \       \         \        /     /
    1   3       2         3      2     1
                 \       /      /       \
                  3     2      1         2
    Your function will have this format:

    int howMany(int k)

    Parameters:

    • k will be between 1 and 19
    • Remember, the function must end within 10 seconds


    Examples
    • howMany(3) will return 5

      Example above

    • howMany(7) will return 429

    • howMany(15) will return 9694845
    Last edited by PJYelton; 05-02-2005 at 09:53 PM.

  4. #4
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    If the number of additions is greater than 100, then stop and print “No Solution”
    Isn't stopping at '100 additions' a bit of an overkill?

    Consider testing the number 187? hmm.


  5. #5
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    the provided function protypes are merely interfaces correct? i imagine we can create our own underlying functions, yes?

    EDIT: nevermind, i foudn the answer...for those who have the same question, the question is yes, you can create your own functions
    Last edited by misplaced; 05-03-2005 at 05:29 AM.
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  6. #6
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Submission for hard problem sent.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  7. #7
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    Quote Originally Posted by Sang-drax
    Submission for hard problem sent.
    Me too, now working on "medium".
    I think the "easy" problem will be the hardest for me. It requires reading and understanding 'n' stuff .

    [edit]
    Question on "medium": may I assume that no initial iteration is needed, So palindrome(11) will print “0 11” instead of "1 22"?
    Last edited by Togra; 05-03-2005 at 07:48 AM.

  8. #8
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Quote Originally Posted by Togra
    Me too, now working on "medium".
    I think the "easy" problem will be the hardest for me. It requires reading and understanding 'n' stuff .
    1.
    One.
    Ditto.
    Me, three.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  9. #9
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Question on "medium": may I assume that no initial iteration is needed, So palindrome(11) will print “0 11” instead of "1 22"?
    That is correct.

    Isn't stopping at '100 additions' a bit of an overkill?

    Consider testing the number 187? hmm.
    I know there are numbers that take over 100 additions, but I didn't want to have people worry about maxing out an integer and start using strings. If it makes you feel better, you can print out "Over 100 iterations needed" instead of "No solution"

    Heh, I think I'll be adding another medium/difficult question to the mix, I thought more people would be needing to manually calculate the answer to the hard question instead of knowing the secret "trick"
    Last edited by PJYelton; 05-03-2005 at 08:59 AM.

  10. #10
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    I know there are numbers that take over 100 additions, but I didn't want to have people worry about maxing out an integer and start using strings. If it makes you feel better, you can print out "Over 100 iterations needed" instead of "No solution"


    nup,

    I think my english is fubar (most likely) or you misunderstood me.
    As you can see the numbers generated soon become unweildly. In
    fact for some cases they start maxing out at 10. So to calculate the 100th additions, invariably you would be handling extremely large integers as you have mentioned.
    Last edited by treenef; 05-04-2005 at 02:26 AM.

  11. #11
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    Secondly, I have to agree with every one else, in regards to the solution for the hard problem, and easy problem.



    I definitely, think it would be a good idea to consider another problem, perhaps another 'difficult' one.

    Good show though.


  12. #12
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Ack, you're right, sorry, it was a typo in the problem statement and I didn't realize the number was wrong when I replied to you. Your program should stop at 10, not 100. I've updated the original problem statement.

    LOL, the first contest was too hard, now this one is too easy, I cant win

    You guys who want a challenge will definately get another problem tonight.

  13. #13
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Hard Problem ver 2

    Okay everyone here is a slight variation on the binary search tree problem above. If you used an algorithm to calculate the other hard problem, then you only need to make a couple small changes to figure out this one. If you used those special numbers that share the name of a certain Spanish language, then you have a little more work ahead of you

    The task is the same, figure out the number of binary search trees that exist given the amount of unique nodes. The only difference is we are going to use a variation of binary search trees. This variation of the BST states that no node can have a null child unless the other child is also null or is a leaf (node that has no children). This doesn't mean the tree is balanced, it can still be very unbalanced, ie the root can have one leaf to the left and 20 children to the right.

    For example, the regular BST above has 5 combinations of three nodes. This new variation only has one:
    Code:
       2
      / \
     1   3
    There are six combinations of 5 nodes:
    Code:
      2               3                3               3             3        4
     / \             / \              / \             / \           / \      / \
    1   4           2   4           2    5           1   4         1   5    2   5
       / \         /     \         /     /            \   \        \   /   / \
      3   5       1       5       1     4              2   5        2 4   1   3
    Create the following function:

    int howMany2(int k)

    Parameters:
    • k will be between 1 and 25


    Examples:
    • howMany2(5) will return 6
    • howMany2(10) will return 300
    • howMany2(20) will return 1843864
    Last edited by PJYelton; 05-03-2005 at 01:36 PM.

  14. #14
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    This may sound obvious or dumb, but I believe we should be clear about it.

    How about precomputing values? Like
    Code:
    int howMany2(int k)
    {
      static int precomputed[26] = {<insert correct values here>};
      return precomputed[k];
    }
    I consider this to be cheating, but I couldn't find a rule disallowing it.

    [edit]
    And how about a more obfuscated form, like some fancy generating polynomial...

  15. #15
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    >>How about precomputing values?<<

    No rule against it, in fact I already have one submission for version one that did this. Can't say you'll get any bonus points for it though At least say where you got the numbers from, although if you compute them yourself I don't see why you wouldn't just use that as your submission.

    >>And how about a more obfuscated form, like some fancy generating polynomial...<<

    Feel free to obfuscate as much as you want, just let me know how it works. I do have to warn though that this is an algorithm solving contest, not an obfuscated code contest, so a simpler slicker program will receive more points.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. May Monthly Contest Results
    By PJYelton in forum Contests Board
    Replies: 28
    Last Post: 05-27-2005, 01:43 AM
  2. Results of March Monthly Contest
    By PJYelton in forum Contests Board
    Replies: 23
    Last Post: 04-17-2005, 09:46 AM
  3. New Monthly Contest!
    By PJYelton in forum Contests Board
    Replies: 50
    Last Post: 03-22-2005, 08:27 PM
  4. WANTED: Contest Master
    By kermi3 in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-23-2003, 10:15 PM