find-the-ring

There is a new magician in town. His trick is known as "Find the Ring".

He puts 3 glasses at 3 spots on the table, labeling them as 0, 1 and 2. Now, he hides a ring under one of the glasses. The glasses are opaque and placed upside down, so that the ring is not visible to the audience.

Now, he begins to make certain swaps in between adjacent glasses, i.e. the glass at position 0 can be swapped with that at position 1, and the glass at position 2 can be swapped with glass at 1.

Assuming that all swaps are done randomly with equal probability of 50%, you have to find index of the glass that is most likely to have the ring, at the end. In case of a tie, choose the one with lower index.

Assume that the glass containing the ring was swapped exactly N times.

Input:

The first line contains an integer T, denoting the number of test cases. Each of the following T lines contain two space separated integers, index and N. index is index of glass that initially contains the ring and N is the total number of swaps involving the glass with ring.

Output:

For, each of the T test cases, output the corresponding answer in a new line.

Constraints:

1 ≤ T ≤ 100
0 ≤ index ≤ 2
0 ≤ N ≤ 10000

SAMPLE INPUT
3
1 1
0 1
2 2

SAMPLE OUTPUT
0
1
0

Explanation

Case 1:

The ring is at index 1. There is only one swap to be made. The probability of ring ending up at 0 is .5, at 1 is 0 and at 2 is also .5 
So, we have a tie between positions 0 and 2. We must choose the lower index, i.e. 0

Case 2:

The ring is at index 0. There is only one swap to be made. There is also only one choice. The probability of ring ending up at 0 is 0, at 1 is 1 and at 2 is 0.
The maximum probability occurs at index 1.

Case 3:

The ring is situated at index 2. There are 2 swaps to be made. 
So, we can make following swaps: {2 -> 1 -> 0} or {2 -> 1 -> 2}
Hence, the probability of ring ending up at 0 is .5, at 1 is 0 and at 2 is .5
Again, there is a tie between 0 and 2, and we choose 0, i.e. the lower index.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
t=eval(input())
i=0
while i<t:
	x=input().split(' ')
	ind=int(x[0])
	n=int(x[1])
	if n==0:
		print(ind)
	else:
		if ind==1:
			if n%2==0:
				print("1")
			else:
				print("0")
		else:
			if n%2==0:
				print("0")
			else:
				print("1")
	i=i+1
		


t = int(input())

for test in range(t):
	index, n = list(map(int, input().split(' ')))

	if index == 1:
		if n % 2 == 0:
			print(1)
		else:
			print(0)
			
	else:
		if n == 0:
			print(index)
		elif n == 1:
			print(1)
		else:
			if n % 2 == 0:
				print(0)
			else:
				print(1)
			


T = int(input())

for i in range(T):
	pos, n = list(map(int, input().split()))
	if n % 2 == 0:
		if n == 0:
			ans = pos
		elif pos == 1:
			ans = 1
		else:
			ans = 0
	else:
		if pos == 1:
			ans = 0
		else:
			ans = 1
	print(ans)


for i in range(eval(input())):
	index,n=list(map(int,input().split()))
	find =index
	if (index in [0,2] and n%2==1) or (index in [1] and n%2==0):
		 find =1
	if (index in [0,2] and n%2==0 and n>0) or (index in [1] and n%2==1):
		 find =0
	print(find)
		 
		 


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

test_count = int(input())
for line in range(test_count):
	line_input = input()
	line_items = line_input.split(' ')
	start_index = int(line_items[0])
	num_swaps = int(line_items[1])
	
	if num_swaps is 0:
		print(start_index)
	else:
		if start_index is 1:
			if num_swaps % 2 is 0:
				print((1))
			else:
				print((0))
		else:
			if num_swaps % 2 is 0:
				print((0))
			else:
				print((1))
	




t=eval(input())
while(t>0):
	i,n=[int(x) for x in input().split()]
	if(n==0):
		print(i)
	else:
		if(i==0):
			if(n%2==0):
				print(0)
			else:
				print(1)
		elif(i==1):
			if(n%2==0):
				print(1)
			else:
				print(0)
		else:
			if(n%2==0):
				print(0)
			else:
				print(1)
	t=t-1	


n=int(input())
while n:
	
	t=(input())
	t=t.split(' ')
	t[0]=int(t[0])
	t[1]=int(t[1])
	if t[1]==0:
		print(t[0])
		
	elif t[1]%2==0:
		if t[0]==1:
			print("1")
		else :
			print('0')
	else :
		if t[0]==1:
			print("0")
		else :
			print('1')
	n-=1


tc = eval(input())
for _ in range(tc):
	n, m = list(map(eval, input().split()))
	if(m==0):
		print(n)
	elif(n==0 or n==2):
		if(m%2==0):
			print(0)
		else:
			print(1)
	else:
		if(m%2==0):
			print(1)
		else:
			print(0)


t=int(input())
while t>0 :
	t=t-1
	index, N=input().split()
	index, N=[int(index), int(N)]
	while N>0 :
		N=N-1
		if index==0 :
			index=1
		elif index==1 :
			index=0
		elif index==2 :
			index=1
	print(index)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
if __name__ == '__main__':
	cases = int(input())
	start = 1
	while start <= cases:
		input_list = input()
		input_list = input_list.split()
		first = int(input_list[0])
		second = int(input_list[1])
		if first == 0:
			if second % 2 == 0:
				print(0)
			else:
				print(1)
		elif first == 1:
			if second % 2 == 0:
				print(1)
			else:
				print(0)
		else:
			if second == 0:
				print(2)
			elif second % 2 == 1:
				print(1)
			else:
				print(0)
		start = start + 1




for i in range(eval(input())):
	a,b = list(map(int,input().split()))
	if(b==0):
		print(a)
	else:
		print((a+b)%2)


n = int(input())
while n > 0:
	ans = 0
	a = input().split()
	a = [int(x) for x in a]
	ind = a[0]
	moves = a[1]
	if moves>0:
		if ind == 0:
			ans = moves%2
		elif ind == 1:
			if moves%2==0:
				ans = 1
			else :
				ans = 0
		else :
			ans = moves%2
	else :
		ans = ind
	print(ans)
	n = n - 1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t=eval(input())
while t:
	a = input().split()
	a = [int(x) for x in a]
	index = a[0]
	n = a[1]
	if(n>0):
		if(index%2==0): index=n%2
		else: 
			index=(n%2)
			if index:index-=1
			else: index+=1
	print(index)
	t-=1


t=eval(input())
for test in range(t):
	index,n=list(map(int,input().split()))
	place=['#','#','#']
	place[index]='r'
	pos=index
	while (n!=0):
		if pos==0:
			place[1]='r'
			place[0]='#'
			pos=1
		elif pos==1:
			place[1]='#'
			place[0]='r'
			pos=0
		elif pos==2:
			place[1]='r'
			place[2]='#'
			pos=1
	   
		n-=1
	print(pos)
		
	


t=eval(input())
for i in range(t):
	index,n=list(map(int,input().split()))
	if index==0:(a,b,c)=(1.0,0.0,0.0)
	if index==1:(a,b,c)=(0.0,1.0,0.0)
	if index==2:(a,b,c)=(0.0,0.0,1.0)
	for j in range(n):
		x=0.5*b
		y=a+c
		z=0.5*b
		a=x
		b=y
		c=z
	if a>=b and a>=c:print(0)
	if b>=c and b>a:print(1)
	if c>a and c>b:print(2)


'''
T = int(raw_input())
for i in range(T):
	pos, n = map(int, raw_niput().split())
	if n % 2 == 0:
		if pos == 1:
			ans = 1
		else:
			ans = 0
	else:
		if pos == 1:
			ans = 0
		else:
			ans = 1
	print ans
'''
def final_pos(n, pos, num, result):
    if num == n:
        result[pos] += 1
    else:
        if pos == 0 or pos == 2:
            final_pos(n, 1, num+1, result)
        elif pos == 1:
            final_pos(n, 0, num+1, result)
            final_pos(n, 2, num+1, result)

T = int(input())

for i in range(T):
    pos, n = list(map(int, input().split()))
    
    #result = [0, 0, 0]
    '''
    final_pos(n, pos, 0, result)
    print "result:", result
    max = 1 if result[1] >= result[2] else 2
    max = 0 if result[0] >= result[max] else max
    print max
    '''
    if n % 2 == 0:
        if n == 0:
        	ans = pos
        elif pos == 1:
            ans = 1
        else:
            ans = 0
    else:
        if pos == 1:
            ans = 0
        else:
            ans = 1
    print(ans)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
tc = int(input())
for t in range(tc):
	r,n = list(map(int,input().split()))
	if n == 0:
		print(r)
	else:
		if r == 1:
			if (n % 2) == 1:
				print(0)
			else:
				print(1)
		else:
			if (n % 2) == 1:
				print(1)
			else:
				print(0)


t = eval(input())
while t > 0:
	i, n = list(map(int, input().split()))
	while n > 0:
		if i == 0 or i == 2:
			i = 1
		else:
			i = 0
		n -= 1
	print(i)
	t -= 1


t = eval(input())
for i in range(t):
	index, n = list(map(int, input().split()))
	if index == 1:
		if n % 2 == 0:
			print(1)
		else:
			print(0)
	elif index == 2 and n == 0:
		print(2)
	elif index == 0 or index == 2:
		if n % 2 == 0:
			print(0)
		else:
			print(1)
			
			


for i in range(eval(input())):
   
	index,n=list(map(int,input().split()))
	find =index
	if index in [0,2] and n%2==1:
		 find =1
	if index in [0,2] and n%2==0 and n>0:
		 find =0
	if index in [1] and n%2==0:
		 find =1
	if index in [1] and n%2==1:
		 find =0
	print(find)
		 


def mult(matrix1, matrix2):
	n = len(matrix1)
	ans = [[0]*n for i in range(n)]
	for i in range(n):
		for j in range(n):
			for k in range(n):
				ans[i][j] = ans[i][j] + (matrix1[i][k]*matrix2[k][j])
#	print 'two', ans
	return ans

def square(matrix):
	return mult(matrix, matrix)

def pow_mat(matrix, k, index):
	n = len(matrix)
	ans = [[0]*n for i in range(n)]
	for i in range(n):
		ans[i][i] = 1
	if k > 0:
		if k%2 == 1:
			ans = mult(ans, matrix)
		k = k/2
	while k > 0:
		matrix = square(matrix)
		if k%2 == 1:
			ans = mult(ans, matrix)
		k = k/2
	max = 0
	if ans[index][0] < ans[index][1]:
		max = 1
	if ans[index][max] < ans[index][2]:
		max = 2
	print(max)
#	print 'one', ans
	return
#	return ans
	
t = int(input())
while t > 0:
	t = t - 1
	index, n = list(map(int, input().split()))
	matrix = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]
	pow_mat(matrix, n, index)
#	ans = pow_mat(matrix, 15)
#	print matrix


class Find:
	def calculate(self,n,N):
		while N:
			if n==1:
				n= 0
			elif n==0:
				n=1
			elif n==2:
				n=1
			N-=1
		return n

			
T=int(eval(input()))
assert(1<=T and T<=100)
while T:
	i=str(input())
	new=i.split()
	index=int(new[0])
	N=int(new[1])
	# inde/x,N=int(raw_input()),int(raw_input())
	# assert(0<=index and index<=2)
	# N=int(input())
	# assert(1<=N and N<=10000)
	obj=Find()
	print(obj.calculate(index,N))
	T-=1
	


#!/usr/bin/python
T=int(eval(input()))
for t in range(0,T):
	i,n=input().split()
	if (int(n)==0): print(i)
	else: print((int(n)-int(i))%2)


t = eval(input())
while t > 0:
	i, n = list(map(int, input().split()))
	while n > 0:
		if i == 0 or i == 2:
			i = 1
		else:
			i = 0
		n -= 1
	print(i)
	t -= 1


f=int(input())
while f>0 :
	f=f-1
	index, N=input().split()
	index, N=[int(index), int(N)]
	while N>0 :
		N=N-1
		if index==0 :
			index=1
		elif index==1 :
			index=0
		elif index==2 :
			index=1
	print(index)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t=eval(input())
while t:
	index,n = list(map(int,input().split()))
	if(n>0):
		if(index%2==0): index=n%2
		else: 
			index=(n%2)
			if index:index-=1
			else: index+=1
	print(index)
	t-=1


n = eval(input())
for i in range(n):
	
	a = input().split()
	a = [int(x) for x in a]
	ind = a[0]
	moves = a[1]
	
	if moves > 0 :
	    if ind == 0: 
	    	ans = moves % 2
	    elif ind == 1:
	    	if moves % 2 == 0:
	    		ans = 1 
	    	else:
	    		ans = 0
	    else:
	    	ans = moves % 2
	else:
	 	ans = ind
	
	print(ans)