PBBN1 - Print Big Binary Numbers

no tags 

Some answers for some problems could be huge binary numbers. In order to check the computation, one could ask you the sum of its digits. With a little base, the answer is a small number too, but not with a bigger base.

XerK would like to avoid precomputed results and wish check you've computed his huge numbers. Here's a tutorial problem that check computation of a big number N. A classical edition exists with language restrictions.

Let define the function CHK(N, B):
Input : N a big number in binary representation, B a power of two. Consider N as a base B number.
Output : the sum of its digits in this base.

Example :with B=2^8, 12345678 = 78 + 97*B + 188*B*B, so CHK(12345678, B) = 78 + 97 + 188

This should be easily computed with few bitwise-AND, bitshifts and additions.

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are four integers A, B, C, D, given in base 10.

Output

For each test case :
* compute N = (A^B) XOR (C^D).
* print CHK(N, 2^16384) as a base 10 number.
(^ denote the power, and XOR the bitwise operator)

Example

Input:
2
7 3 5 4
1234 5678 9012 4444


Output:
806
1194204158794232147799<...snip...>9938532444216215551948305

Explanations

For test case 1:
7^3 = 343, 5^4 = 625, 343 XOR 625 = 806, CHK(806, 2^16384) = 806.

For test case 2:
You have to output all 4933 digits of the result.

Constraints

1 < T <= 321
1 < A, B, C, D <= 10^4

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2012-11-24 11:37:59

My C code run perfectly on my PC but SIGSEGV here? seems that because case #3, can you tell me what is it? and also my 127Bytes python 3 code getting TLE, is there any tricky test case?
--ans--> it's not case dependent. if T==1 : no SIGSEGV for some input, but with T==2, you have SIGSEGV with the same values. (Experiments on my 64bit hardware, GNU/Linux obviously ;-) .)
EDIT: thanks I got it, seems that infinite allocation occured, and for debug it (large code) is hard...

Last edit: 2012-11-24 12:16:09

Added by:Francky
Date:2012-11-23
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem