I have to write a program to solve the following problem:

A and B are playing. A thinks of a number between 1 and N. B has to find it out with using only this question: "Is it equal to or lesser than x?" where x is any number between 1 and N. To make things more difficult, a given value belongs to each of the numbers between 1 and N. Whenever B poses his question, he must pay as many dollars as the value that belongs to x.
For example, I get this in an input file:

Where the first line is N, and the numbers in the second line are the values that belong to 1, 2, 3 etc.

I have to find out how much does it cost at least to find out any number A can think of (between 1 and the given N of course).

There's an example that shows the optimal question sequence (that produces the minimal amount of dollars required to find out any number between 1 and 7). This minimal amount here is 14.


This picture shows the questions (the numbers in circles). The left child is selected when the answer's yes, and the right child when the answer's no. The small numbers outside the circles mean their value.

Now how do I create this optimal question sequence (this binary tree)? I only get the input shown above in the CODE box.

Thanks for your help!

you will need to post an attempt at this question, known as "good faith" code. We area community to help and encourage programming, but we will not do your homework for you.

You seem to understand the concept quite well, have you tried implementing a binary tree class? Is a specific extension supplied for you? Please show us what you have done so far.

I've made a Binary tree data structure implementation, here it is:

(originally it contains variable names and function names that make sense in Hungarian only, I just made a quick translation of all of those, so this code may or may not compile)


'E' will probably be exchanged with Integer.

I have no problem with reading the input (the 'values' will be put in a vector, the N will be put in an int). Once I've got the optimal tree, I will be able to find the most expensive route in it. I didn't start coding that yet, because I'm not 100% sure this concept is the best one. Maybe there is some way to calculate the optimal decision tree without actually constructing it, using a 2D array.
I don't need code, all I need is the algorithm (maybe a pseudo-code) that finds the optimal question sequence.

This post has been edited by Wo Hu: 11 Oct, 2007 - 06:47 AM