Alien languageProblem code: G4 |
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.
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'.
| Author: | admin |
| Date Added: | 15-08-2009 |
| Time Limit: | 1 - 5 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Shouldn't the output for the
Shouldn't the output for the first test case be 5, based on the explanation?
No, the sum of the values is
No, the sum of the values is 7 and not 5.
Does the empty string count
Does the empty string count as a word (ie is the answer 0 when n=1)?
The o\p of 1st case sud be
The op of 1st case sud be '00','10','11' instead of 0','10','11' due to absence of seperator in d alien`s language.
No, the explanation is
No, the explanation is correct as is.
@Stephen No.
@Stephen No.
No, it means that your code
No, it means that your code is producing the wrong answer for the test input.
I want to write my code in
I want to write my code in C#. Can I read input from Console & write output to Console?
Either the answer for the
@Abhijeet Yes. @Josh Fixed.
@Abhijeet Yes.
@Josh Fixed.
Shouldn't the optimal
Shouldn't the optimal encoding for the first test case be '00','10','11' ?
/slightly confused.
Can you please explain the
Can you please explain the output of the first testcase?
For the first test case, it
For the first test case, it is the sum of the efforts for writing down the words mentioned in the explanation.
@Michael No
The largest output for this
The largest output for this problem exceeds a 64-bit integer. (a=b=1e9;n=1e12; since every word requires atleast one symbol to be output and 1e9*1e12 exceeds 64-bits);
I just want to ask here, if the judge expects the outputs to exceed 64-bits. Just a 'yes' would be good. Thanks.
Yes :)
Yes :)
I apologize for leaving some
I apologize for leaving some doubts what is actual problem task, but sample test should leave no doubts...
i am new in here can someone
i am new in here can someone tell me what should be the input file name?
input.txt?
Read from standard input, not
Read from standard input, not from a file.
so if i use php..i need to
so if i use php..i need to create a form to sbmit data?
If yes the for should be one text box only?
Thanks
See this.
See this.
My code solves the problem in
My code solves the problem in 2.5 seconds for the n of the order of 10^12 in my computer. I know there are quite a few correct submissions, but I'm still at a total loss because I cant see any reason why the code should time out on the judge.
The online judge is likely to
The online judge is likely to be slower than your computer due to the setup. See the FAQ for the full specs.
Other than that, don't forget there can be 10000 tests.. I presume your 2.5 seconds is the total for 10000 inputs of size 10^12?
Yes. I create 10000 tests
Yes. I create 10000 tests where n <= 10^12.
For Smart Frog, the code that runs in 6 seconds on my computer gets accepted. Which means it took less than 3 seconds on the judge. Thats half the time!
Why should this one take more than double the time!
Anyways, I'll try and check
Anyways, I'll try and check once more trough it, if there is a mistake on my side. Or if I can optimize a little more.
No idea why your smart frog
No idea why your smart frog solution runs slower on your computer; the judge here is always roughly twice the time it takes on my computer, so I use that as a guide.
would it be possible to get
would it be possible to get the test case and correct result for this problem.
thanks Admin
@earyoyo The test cases will
@earyoyo The test cases will be uploaded soon.
hi, i ma new here... just
hi,
i ma new here...
just wanted to know how to submit code.
regards,
nandan
Choose any of the problems
Choose any of the problems from the practice section in the navigation panel and once you have written the code, click on the submit button on the top right and choose the language and then submit the code.
If I am understanding
Part of my message was cut
Part of my message was cut off. As I mentioned, I don't see how the first output is a valid solution over '1','01','00' and therefore how it was arrived at over the inverse.
1,01,00 is a valid
1,01,00 is a valid prefix-free encoding. Since it uses three 0s (weight 2 each) and two 1s (weight 1 each), the total weight is 8.
The total weight of 0,10,11 is 7, which is better.