Yet Another Constructive Problem solution codechef- You are given a positive integer XX which is at most 108108. Find three distinct non-negative integers A,B,CA,B,C that do not exceed 109109 and satisfy the following equation: (A∣B)&(B∣C)&(C∣A)=X(A∣B)&(B∣C)&(C∣A)=X Here, ∣∣ denotes the bitwise OR operator and && denotes the bitwise AND operator. It can be shown that a solution always exists for inputs satisfying the given constraints. If there are multiple solutions, you may print any of them.

Yet Another Constructive Problem solution codechef

You are given a positive integer XX which is at most 108108.

Find three distinct non-negative integers A,B,CA,B,C that do not exceed 109109 and satisfy the following equation:

(AB)&(BC)&(CA)=X(A∣B)&(B∣C)&(C∣A)=X

Here,  denotes the bitwise OR operator and && denotes the bitwise AND operator.

It can be shown that a solution always exists for inputs satisfying the given constraints. If there are multiple solutions, you may print any of them.

Input Format Yet Another Constructive Problem solution codechef

  • The first line contains an integer TT, the number of test cases. The description of TT test cases follows.
  • Each test case consists of a single line containing one integer, XX.

Output Format

  • For each test case, print on a new line three different space-separated integers A,B,CA,B,C.
  • Your output will be considered correct only if A,B,CA,B,C are distinct non-negative integers not exceeding 109109 that satisfy the equation given in the problem statement.
  • If there are multiple solutions, you may print any of them.

Constraints Yet Another Constructive Problem solution codechef

  • 1T1001≤T≤100
  • 1X1081≤X≤108
  • 0A,B,C1090≤A,B,C≤109
  • A,B,CA,B,C must be pairwise distinct

Sample Input 1 

4
3
2
13
100000000

Yet Another Constructive Problem solution codechef Sample Output 1 

1 2 3
2 3 4
6 9 13
23570468 129811858 80835401

Explanation

Test case 11: (12)&(23)&(31)=3&3&3=3(1∣2)&(2∣3)&(3∣1)=3&3&3=3 and hence A=1,B=2,C=3A=1,B=2,C=3 is one valid solution when X=3X=3. However there are several other solutions.

For example, A=1,B=6,C=3A=1,B=6,C=3 is also valid and will also be considered correct.

Test case 22: (23)&(34)&(42)=(3&7)&6=3&6=2(2∣3)&(3∣4)&(4∣2)=(3&7)&6=3&6=2.

Test case 33: (69)&(913)&(136)=(15&13)&15=13&15=13(6∣9)&(9∣13)&(13∣6)=(15&13)&15=13&15=13.

Leave a Comment

Your email address will not be published.