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: Code: 7 1 3 10 1 5 2 6 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!
