2010 Canadian Computing Competition, Stage 1

Problem J1: What is n, Daddy?

Natalie is learning to count on her fingers. When her Daddy tells her a number n, she asks “What is n, Daddy?”, by which she means “How many fingers should I hold up on each hand so that the total is n?” To make matters simple, her Daddy gives her the correct finger representation according to the following rules:

• the number may be represented on one or two hands;
• if the number is represented on two hands, the larger number is given first.

For example, if Natalie asks “What is 4, Daddy?”, her Dad may reply:

• 4 is 4.
• 4 is 3 and 1.
• 4 is 2 and 2.

Your job is to make sure that Natalie’s Daddy gives the correct number of answers.

Input Format

A single integer n (1 ≤ n ≤ 10).

Output Format

The output is the number of ways of producing that number on two hands, subject to the rules outlined above.

Sample Input

4

Sample Output

3

All Submissions
Best Solutions

Point Value: 3
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 23, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Something is obviously wrong with my code... can you tell me what's wrong??



It would be much appreciated!!

You aren't printing the right answers. Remember that 4 on the left hand and 2 on the right is the same as 2 on the left hand and 4 on the right

Why is it marking me wrong when I say that you can only make 7  4 times? The combinations are clear! 0 and 7, 1, and 6, 2 and 5, 3 and 4!! Is there something wrong with the format that I am putting it in or something?

Thanks!

Do you have 7 fingers on your right hand? :^)

ohhhhhhhhhhhh.... ok.... thanks!!!

Can you give me a hint for problem ccc10j1.

Although the problem suggests using fingers to count I found that using my toes was more effective.

So to solve this question all you have to do is use your hands and do the math yourself and program the thing to output your pre-thought of answer? I was thinking of some complicated way involving loops and stuff.

There are ways to do this that do not involve precomputation or brute force. Now that you've solved the problem, you can see them.

See [url=http://wcipeg.com/submissions/src/45452]zhxl0903's solution[/url] for an example of a formula that works for human hands, or [url=http://wcipeg.com/submissions/src/53331]HelloMelloC's solution[/url] for an example of a more generalisable solution involving loops.

 I used two different ways and one of them is brute force. Both did not work. I have no idea why, its very easy and my answers were right but it said 'wrong answer'. Does it have to do with the peg servers?

Your output is wrong. This problem is quite simple since you can try it with your own hands. How many different ways can you represent 10 for example, with your hands?

 oh, now I get it... thanks for the help

Can this be solved without "Brute force"? 
(by putting the input into an equation)

Absolutely.

Would that method be faster or slower (runtime) compared to bruteforce ? 

Nothing can be slower than brute force.

[url]http://c2.com/cgi/wiki?MultiplyAndSurrender[/url]

though, admittedly, some problems must be solved with brute force, but efficiently implemented (cryptcow comes to mind); see also bogosort

What is cryptcow? I didn't get much out of a google search o.O

It's just a problem from the USACO Training Webpages (http://train.usaco.org).

how comes there no description? bug...

I'll put up problem descriptions eventually; for now I'm too lazy. You can find the [url=http://cemc.uwaterloo.ca/contests/computing/2010/index.html]original problem description[/url] at the CEMC website; just remember that input/output are not to be read from / written to files, and that you should not prompt.