[Solution] Find A, B, C solution codechef

Find A, B, C solution codechef – Chef has 33 hidden numbers A,B,A,B, and CC such that 0A,B,CN0≤A,B,C≤N.

Let ff be a function such that f(i)=(Ai)+(Bi)+(Ci)f(i)=(A⊕i)+(B⊕i)+(C⊕i). Here  denotes the bitwise XOR operation.

Table of Contents

[Solution] Find A, B, C solution codechef

Given the values of f(0),f(1),,f(N)f(0),f(1),…,f(N), determine the values of A,B,A,B, and CC.

It is guaranteed that at least one tuple exists for the given input. If there are multiple valid tuples of A,B,CA,B,C, print any one.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains a single integer NN denoting the upper bound on the values of A,B,CA,B,C.
    • Next line contains N+1N+1 space-separated integers denoting f(0),f(1),,f(N)f(0),f(1),…,f(N).

Output Format

For each test case, output on a new line, three space-separated integers, the values of A,B,A,B, and CC. If there are multiple valid tuples of A,B,CA,B,C, print any one.

[Solution] Find A, B, C solution codechef

  • 1T21041≤T≤2⋅104
  • 2N1052≤N≤105
  • Sum of NN over all test cases does not exceed 21052⋅105.

Sample Input 1 

3
2
0 3 6
2
4 7 2
5
9 6 11 8 13 10

Sample Output 1 

0 0 0
2 0 2
1 3 5

[Solution] Find A, B, C solution codechef Explanation

Test case 11: The tuple A=0,B=0,C=0A=0,B=0,C=0 satisfies as:

  • f(0)=00+00+00=0f(0)=0⊕0+0⊕0+0⊕0=0.
  • f(1)=01+01+01=3f(1)=0⊕1+0⊕1+0⊕1=3.
  • f(2)=02+02+02=6f(2)=0⊕2+0⊕2+0⊕2=6.

Test case 22: The tuple A=2,B=0,C=2A=2,B=0,C=2 satisfies as:

  • f(0)=20+00+20=4f(0)=2⊕0+0⊕0+2⊕0=4.
  • f(1)=21+01+21=7f(1)=2⊕1+0⊕1+2⊕1=7.
  • f(2)=22+02+22=2f(2)=2⊕2+0⊕2+2⊕2=2.

Test case 33: The tuple A=1,B=3,C=5A=1,B=3,C=5 satisfies as:

  • f(0)=10+30+50=9f(0)=1⊕0+3⊕0+5⊕0=9.
  • f(1)=11+31+51=6f(1)=1⊕1+3⊕1+5⊕1=6.
  • f(2)=12+32+52=11f(2)=1⊕2+3⊕2+5⊕2=11.
  • f(3)=13+33+53=8f(3)=1⊕3+3⊕3+5⊕3=8.
  • f(4)=14+34+54=13f(4)=1⊕4+3⊕4+5⊕4=13.
  • f(5)=15+35+55=10

For Solution

Click Here

Leave a Comment