133B — Unary
In the Editorial of The Problem 133B — Unary.......It is given to multiply by 16 and then add...i can't Understand Why to multiply by 16.....can anybody help????
Editorial Link — http://codeforces.net/blog/entry/3302
And why is this soln giving me negative decimal value for large binary value...Please help if i can correct my soln..
my soln — Your text to link here...
Concatenating two binary numbers of size 4
abcd
andefgh
toabcdefgh
is the same asabcd*2^4 + efgh
. Same reason why27 = 2*10 + 7
or1234 = 12*10^2 + 34
.Your solution doesn't work, because
pow(2,x - i)
will return adouble
.You convert it implicitly into a
long long
. But for some bigx
and smalli
, the value ofpow(2,x - i)
will be too big for along long
, and therefore you will get an integer overflow, and you end up with a random number, possible negative.Second,
doubles
only have a certain amount of accuracy. So computing the power and converting it back will almost always end up with an inaccurate result.If you want to compute big exponents mod some number, take a look at this algorithm: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation
Each character of the original program is replaced by a binary code of length 4. This means that when you append code for one character, the rest of the code is shifted right by 4 binary digits, which is the same as multiplied by 24 = 16.
Storing power of 2 in long long overflows; you have to take modulo during the power calculation, not in the end (https://ideone.com/Kq9tBI)