A good one! - dont lose ur sleep over it :)

Write a small program to achieve the following:

Problem:
Aliens from the planet of Jupiter have an extremely well-developed language. Recently they have introduced a special alphabet which consists of only 2 symbols. Now, they would like to develop a way to write down all the words they have in their language using this alphabet. They want to be able to decode sequences of words without breaks between them, so they would like to retain the following property: no word is the proper prefix of any other word. Knowing know how many words they have, that each word occurs equally often in every-day use, and knowing the effort required to write down each of the two symbols of the alphabet (the complexity of the first symbol and the second symbol need not to be equal!) help them to develop an encoding which minimizes the mean effort required to write down a word of the language.
Input
First, 1≤t≤10000, the number of test cases. Each test case contains: 1≤a≤109, 1≤b≤109, 1≤n≤1012, meaning: the effort required for writing down the first symbol, the effort required for writing down the second symbol, and the number of words of the language, respectively.
Output
For each testcase, output the total effort required to obtain all words in the optimal encoding.
Example
Input:
2
2 1 3
1 1 16
Output:
7
64
Explanation
The optimal encoding for the first testcase is:
'0','10','11'.
The optimal encoding for the second testcase is:
'0000','0001',...,'1110','1111'.

It was up in a coding contest and my implementation took more time than permitted. I'm sure you guys can do better

By saying that the language consists of an alphabet comprising of 2 symbols do u mean to say that the language consists of 2 alphabets. As far as the examples are concerned, it seems that the language consists of 2 alphabets.

An alphabet is set of symbols/letters which can be used to build words which can then be used to build a language. So I guess the statement in the problem is right - the alphabet here consists of two symbols. Guys from comp sci background will always tend to imagine the symbols as 0 and 1
BTW, missed to mention, in both examples 0 is first symbol and 1 is second symbol.

Ravi Bhai (is this doc?),

I think that I have solved this, but I won't give out the whole solution as I feel it is great question for everybody. Here are some hints (Use them progressively).

The solution lies in understanding the problem and not actually trying to figure out the encodings.

For n = 2^k, immaterial of the value of a and b, the encoding is the trivial binary representation of numbers from 0 to n-1. Why? Lets solve the non trivial case where n= 2^k + l.

Let min = min(a,b) and max = max(a,b).

Also, let l<= 2^m where m is smallest possible positive integer (being formal ).

Now you can break up your encodings into two sets based on the starting alphabet. one set will have symbols which start with min for 2^k words and will be of length k. The other set will start with max and will have l symbols.

Can you figure out the cost for the 2^k words starting with min (It should be trivial and the answer is a simple equation which will come out to be f(k,min,max)?

Now think of the other l symbols? how many bits will they require?
hint: C(r,r) + C(r,r-1) + C(r,r-2) + ... + C(r,1) = 2^r.

what will be the cost of writing these l symbols.

Are you done yet? Think of one final optimization, one of the symbols in these l symbols, can be shortened to be of type 000..0 (I am taking that writing 0 is more expensive than writing 1 without loss of generality)! How many '0's will this symbol have? Decrement the cost of writing the l symbols by this saving!

Voila! you would have the answer! The cost of computation is O(m + 1 + 1) which should bot be much given that (log2 n)<=10

if(n==1)
return min(a,b);

else {
minHeap<int> h; // a min-heap which stores integers..
h.push(0);
for(int i=2; i <= n; ++i)
{
int x = h.pop();
h.push(x+a);
h.push(x+b);
}
print -> "minimized total effort" : h.sum();// sum of all the elements in the minheap...
}

TC : O(nlogn)
SC : O(n)