All submissions for this problem are available.
Aliens from the planet of Zrxllrlv 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.
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.
For each testcase, output the sum of lengths of encodings of all words in the optimal encoding.
Input: 2 2 1 3 1 1 16 Output: 7 64
The optimal encoding for the first testcase is: '0','10','11'. The optimal encoding for the second testcase is: '0000','0001',...,'1110','1111'.
|Time Limit:||0.131744 - 0.65872 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, TCL, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.