Find XOR SOLUTIONS FINXOR

Find XOR SOLUTION

This is an intelligent issue. 
 
There is an arrangement of positive whole numbers A1,A2,… ,AN. You don’t have a clue about this grouping, however your errand is to discover the estimation of A1⊕A2⊕… ⊕AN, where ⊕ means the bitwise XOR activity. 
 
You may ask up to 20 inquiries. In each question, you ought to pick a whole number K (1≤K≤2⋅106) and the interactor reacts with the estimation of (A1⊕K)+(A2⊕K)+… +(AN⊕K). 
 
Connection 
 
To start with, you should peruse a line containing a solitary whole number T signifying the quantity of experiments. The depiction of cooperation for T experiments follows. 
 
For each experiment, you should begin by perusing a line containing a solitary number N. 
 
To pose an inquiry, you should print a line containing two space-isolated whole numbers 1 and K, where 1≤K≤2⋅106. At that point, you should peruse a line containing a solitary whole number ― the solution to your inquiry or −1 if the inquiry is invalid or you posed to in excess of 20 inquiries. 
 
At last, you should print a line containing two space-isolated numbers 2 and X, where X=A1⊕A2⊕… ⊕AN. At that point, you should peruse a line containing a solitary number: 1 if your answer was right or −1 in the event that it was mistaken. In the event that your answer was right, you should keep settling the rest of the experiments. 
 
Note that when you get an answer −1, you ought to quickly end your program to get a Wrong Answer decision; else, you may get any decision. Remember to flush the yield subsequent to printing each line! 
 
Requirements 
 
1≤T≤100 
 
1≤N≤103 
 
1≤Ai≤106 for each legitimate I 
 
Subtasks 
 
Subtask #1 (15 focuses): Ai≤100 for each legitimate I 
 
Subtask #2 (85 focuses): unique requirements 
 
Model 
 
You Grader 
 
 
 
1 2 
 
10 
 
1 5 
 
18 
 
2 4 
 
 
Clarification 
 
Model case 1: The shrouded grouping is A=[1,2,3,4]. 
 
We pose an inquiry with K=2. The grader reacts with A1⊕2+A2⊕2+A3⊕2+A4⊕2=10. 
 
At that point, we pose an inquiry with K=5 and the grader reacts with A1⊕5+A2⊕5+A3⊕5+A4⊕5=18. 
 
Consequently, A1⊕A2⊕A3⊕A4=4.
 
 
VIDEO HAS BEEN REMOVED.

Solution

Program Python:

def func(n):
    print(1," ",pow(2,20))
    inp1=int(input())
    inp1-=(pow(2,20)*n)
    var=2
    while(var>100):
        var+=10
        vl=pow(2,10)
        fans+=vl
        fans-=var
    cop=inp1
    fans=0
    for i in range(1,20):
        print(1," ",pow(2,i))
        inp2=int(input())
        diff=inp1+(pow(2,i)*n)-inp2
        while(var>2):
            inp2+=20
            denn-=1
            fans+=pow(2,n)
            inp1+=1
        denn=pow(2,i)*2
        if((diff/denn)%2==1):
            fans=fans+pow(2,i)
    if(cop%2==1):
        var+=pow(2,2)
        fans=fans+1
    print(2," ",fans,"\n")
    result=int(input())
    if(result==1):
        return   
tests=int(input())
for _ in range(tests):
    n=int(input())  
    func(n)

Program Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
  private static int end = 19;
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner scn = new Scanner(System.in);
    String line = scn.nextLine();
    int t = Integer.parseInt(line.trim());
    for (int i = 0; i < t; i++) {
      doIt(scn);
      line = scn.nextLine();
    }
  }
  
  public static void doIt(Scanner scn) {
    String line = scn.nextLine();
    int n, v, ans;
    n = Integer.parseInt(line.trim());
    System.out.println("1 1");
    line = scn.nextLine();
    v = Integer.parseInt(line.trim());
    int x, a = 2;
    int[] b = new int[25];
    b[0] = v % 2;
    if(n % 2 == 1) {
      if(b[0] == 1) {
        b[0] = 0;
      } else {
        b[0] = 1;
      }
    }
    for (int i = 1; i <= end; i++) {
      System.out.println("1 " + (a + 1));
      line = scn.nextLine();
      x = Integer.parseInt(line.trim());
      int tmp = (x - v) / a;
      b[i] = ((n - tmp) / 2) % 2;
      a = a << 1;
    }
    a = 1;
    ans = 0;
    for (int i = 0; i <= end; i++) {
      if (b[i] == 1) {
        ans = ans ^ a;
      }
      a = a << 1;
    }
    System.out.println("2 " + ans);
  }
}

Program C++:

#include <iostream>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--)
	{
	    long long int n;
	    cin >> n;
	    long long int one = 1;
	    long long int twenty = 20;
	    long long int q = 19;
	    long long int k = (one << twenty);
	    long long int out;
	    long long int ans = 0;
	    cout << "1 " << k << endl;
	    cin >> out;
	    if(out == -1)
	        break;
	    long long int sum = out - (one << twenty)*n;
	    
	    k = 1;
	    long long int i = 0;
	    long long int next_bit_carry = 0;
	    while(q--)
	    {
	        
	        if(next_bit_carry % 2 == 0)
	        {
	            if((sum & (one << i)) != 0)
	            {
	                ans = (ans | (one << i));
	                
	            }
	            
	        }
	        else
	        {
	            
	            if((sum & (one << i)) == 0)
	            {
	                ans = (ans | (one << i));
	                
	            }
	        }
	        cout << "1 " << k << endl;
	        cin >> out;
	        if(out == -1)
	            exit(0);
	        if((n % 2) == 0)
	        {
	            if(out == sum)
	            {
	                next_bit_carry = (next_bit_carry + (n/2))/2;
	               
	            }
	            else if(out < sum)
	            {
	                long long int bit_diff = ((sum - out)/(one << i));
	                next_bit_carry = (next_bit_carry + (n + bit_diff)/2)/2; 
	            }
	            else
	            {
	                long long int bit_diff = ((out - sum)/(one << i));
	                next_bit_carry = (next_bit_carry + (n - bit_diff)/2)/2;
	               
	            }
	           
	        }
	        else
	        {
	            if(out < sum)
	            {
	               long long int bit_diff = ((sum - out)/(one << i));
	               next_bit_carry = (next_bit_carry + (n + bit_diff)/2)/2;
	            }
	            else
	            {
	               long long int bit_diff = ((out - sum)/(one << i));
	               next_bit_carry = (next_bit_carry + (n - bit_diff)/2)/2;
	            }
	        }
	        k = k*2;
	        i++;
	    }
	    if(next_bit_carry % 2 == 0)
	        {
	            if((sum & (one << i)) != 0)
	            {
	                ans = (ans | (one << i));
	                
	            }
	            
	        }
	        else
	        {
	            
	            if((sum & (one << i)) == 0)
	            {
	                ans = (ans | (one << i));
	                
	            }
	        }
	    cout << "2 " <<  ans << endl;
	    cin >> out;
	    if(out == -1)
	        break;
	}
	return 0;
}

6 thoughts on “Find XOR SOLUTIONS FINXOR”

Leave a Comment