1. ## 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. 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”

3. 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

4. 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. 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

6. Submission for hard problem sent.

7. 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 .

Question on "medium": may I assume that no initial iteration is needed, So palindrome(11) will print “0 11” instead of "1 22"?

8. 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.

9. 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"

10. 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.

11. 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. 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. 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

14. This may sound obvious or dumb, but I believe we should be clear about it.

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.

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