chess-tournament-4

2^N participants (P1 , P2 , P3 .... , P2^N ) have enrolled for a knockout chess tournament. In the first round, each participant P2k-1 is to play against participant P2k, (1 ≤ k ≤ 2^N-1) . Here is an example for k = 4 : 

Some information about all the participants is known in the form of a triangular matrix A with dimensions (2^N-1) X (2^N-1). If Aij = 1 (i > j), participant Pi is a better player than participant Pj, otherwise Aij = 0 and participant Pj is a better player than participant Pi. Given that the better player always wins, who will be the winner of the tournament?

Note : Being a better player is not transitive i.e if Pi is a better player than Pj and Pj is a better player than Pk, it is not necessary that Pi is a better player than Pk .

Input
The first line consists of N. Then, 2^N-1 lines follow, the i^th line consisting of  i space separated integers Ai+1 1 , Ai+1 2 , .... Ai+1 i 
Output
A single integer denoting the id of the winner of the tournament.
Constraints
1 ≤ N ≤ 10
Aij = {0, 1} (i > j)

SAMPLE INPUT
2
0
1 0
0 1 1

SAMPLE OUTPUT
1

Explanation

When 1 plays against 2, 1 wins.
When 3 plays against 4, 4 wins.
When 1 plays against 4, 1 wins.

So, 1 wins the tournament.

Source: hackerearth | Difficulty: EASY
Tags: Fundamentals


Solutions:
N = eval(input())
A = [[]]
for ith in range(2**N - 1):
	A.append(list(map(int, input().split())))
players = list(range(2**N - 1, -1, -1))    
while len(players) > 1:
	pairs = list(zip(players[::2], players[1::2]))
	players = [x if A[x][y] else y for x, y in pairs]
print(players[0] + 1)



# cook your code here

n = eval(input())
d  = [n]
for i in range(1,2**n):
	y = d.append(list(map(int,input().split())))
j = 1
l = [x for x in range(0,2**n )]
while j != (2**n):
	s = []
	for i in range(0,len(l)-1,2):
		ans = d[l[i + 1]][l[i]]
		
		if ans == 1:
			s.append(l[i+1])
		else:
			s.append(l[i])
	l = s
	k = [x+1 for x in l]
	
	j = j*2
print(k[0])



#!/bin/python
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n = eval(input())
n2 = 2 ** n
pred = dict()
for i in range(n2):
	pred[i] = dict()
#loop = 1
for i in range(n2 - 1):
	inp = input()
	j = 0
	for val in inp.split():
		if int(val) == 1:
			pred[i + 1][j] = 1
		else:
			pred[j][i + 1] = 1
		j += 1
#print n
#print n2
#print pred

players = list(range(n2))
next_players = []
for i in range(n):
#	print "Round: " + str(i + 1)
	for j in range(2 ** (n - i - 1)):
#		print "Comparing ->" + str(2*j) + " & " + str(2*j+1)
		if players[2 * j + 1] in pred[players[2 * j]]:
			next_players.append(players[2 * j])
		else:
			next_players.append(players[2 * j + 1])
	players = next_players
#	print next_players
	next_players = []

	
print(players[0]+1)
	


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
n = int(input())
lines = []
winners = []
if n<1 or n> 10:
	print(" ")
else:
 #print "n",n,(2**n)-1
 for i in range(0,(2**n)-1):
	line = input()
	if line:
		lines.append(line.strip())
 #print lines 
 flag = 0
 if len(lines) < (2**n)-1:
 	print("")
 else:
  for i,line in enumerate(lines):
	if flag == 0:
		if int(line.split(" ")[-1]) == 0:
			winners.append(i+1)
		else:
			winners.append(i+2)
		flag = 1
	else:
		flag = 0
  #print winners
  index = 0
  winnerlen = len(winners)
  tempW = []
  while winnerlen != 1 and index < winnerlen:
	op1 = winners[index]
	op2 = winners[index+1]
	index += 2
	if int(lines[op2-2].split(" ")[op1 -1]) == 0:
		tempW.append(op1)
	else:
		tempW.append(op2)
	#print "tempW",tempW
	#print "ind ", index
	if index == winnerlen:
		winners  = tempW
		winnerlen = len(winners)
		index = 0
		tempW = []
		#print "change",winners,winnerlen
  print(winners[0])



import sys
n=int(sys.stdin.readline())
a=[[0 for _ in range(pow(2,n)+1)] for _ in range(pow(2,n)+1)]
for i in range(pow(2,n)-1):
	m=list(map(int,sys.stdin.readline().split()))
	for j in range(len(m)):
		a[i+2][j+1]=m[j]
		a[j+1][i+2]=m[j]^1
stack=[i for i in range(1,pow(2,n)+1)]

while len(stack)>1:
	lab=[]
	for i in range(0,len(stack),2):
		ii = stack[i]
		ii1 = stack[i+1]
		if a[ii][ii1]==1:
			lab.append(ii)
		else:
			lab.append(ii1)
	stack=[]
	for la in lab:
		stack.append(la)
print(stack[0])
		


N = int(input())
val = [[0]*(2**N+1) for i in range(2**N+1)]
for i in range(1, 2**N ):
	nums = [int(j) for j in input().split()]
	for j in range(len(nums)):
		val[i+1][j+1] = nums[j]
	
#print val

cur = []
prev = [i for i in range(1, 2**N+1)]

for i in range(N, 0, -1):
	l = len(prev)
	for j in range(0, l, 2):
		if val[prev[j+1]][prev[j]] == 1:
			cur.append(prev[j+1])
		else:
			cur.append(prev[j])
		#print j, prev[j], prev[j+1]
	prev = cur
	cur = []
	#print prev, i

print(prev[0])	
	


#!/usr/bin/env python
# -*- coding: utf-8 -*-

def power(n, e):
	result = 1
	for i in range(0, e):
		result = result * n
	return result

N = int(input())
two_power_N = power(2, N)
t = []
for i in range(1, two_power_N):
		t.append([int(x) for x in input().split()])

participants = [i for i in range(0, two_power_N)]

while len(participants) > 1:
		new_participants = []
		for i in range(1, len(participants), 2):
				if t[participants[i] - 1][participants[i - 1]]:
						new_participants.append(participants[i])
				else:
						new_participants.append(participants[i - 1])
		participants = new_participants

print((participants[0] + 1))


def findwinner(arr,dudes):
	if arr[dudes[1]-2][dudes[0]-1] == 0:
		return dudes[0]
	else:
		return dudes[1]

def dude(arr,n,players):
	players = players
	while len(players)!=1:
		win = []
		for i in range(0,len(players),2):
			#print players[i:i+2]
			winner = findwinner(arr,players[i:i+2])
			win.append(winner)
		players = win
	return players[0]


n = int(input())
size = 2**(n)-1
arr = [[]*size]*size
#print size
#print arr

for i in range(size):
	inp = input().split()
	inp = [int(x) for x in inp]
	arr[i] = (inp)

players = list(range(1,(2*2**(n-1))+1))
print(dude(arr,n,players))

	



def winner(p, q, c):
	if p>q:
		p,q = q,p
	if c[q-1][p] == 0:
		return p
	else:
		return q
		
n = eval(input())
l = 2**n
c = []
for ____ in range(l-1):
	c.append(list(map(int, input().split())))

L = [i for i in range(l)]
L1 = []

while(len(L) != 1):
	for k in range(l/2):
		p = 2*k
		q = 2*k+1
		L1.append(winner(L[p],L[q], c))
	L = L1
	L1 = []
	l = l/2
	
print(L[0]+1)


def flip(n):
	if n==0:
		return 1
	return 0
n=int(input())
n_p=2**n

data=[[None for i in range(n_p)] for j in range(n_p)]

for i in range(n_p-1):
	d=list(map(int,input().split()))
	for j in range(i+1):
		data[i+1][j]=d[j]
		data[j][i+1]=flip(d[j])

#print data
players=list(range(n_p))
winners=[]
while(1):
	#print players
	for i in range(0,len(players),+2):
		if data[players[i]][players[i+1]]==1:
			winners.append(players[i])
		else:
			winners.append(players[i+1])
	players=[i for i in winners]
	winners=[]
	if len(players)==1:
		print(players[0]+1)
		break



import sys
import math

def better():
	k = int(sys.stdin.readline())
	n = 1 << k
	a = [[-1 for x in range(0,n)] for x in range(0,n)]
	for i in range(0,n):
		j = 0
		if j < i:
			val = sys.stdin.readline().split(" ")
		while j < i:
			a[i][j]  = int(val[j])
			j += 1
			
	winner = [x for x in range(0, n)]
	for m in range(0,k):
		i = 0
		nw = []
		while i+1 < len(winner):
			if a[winner[i+1]][winner[i]]:
				nw.append(winner[i+1])
			else:
				nw.append(winner[i])
				
			i += 2
		winner = nw

	print(winner[0] + 1)
		
		


if __name__ == "__main__":
	better()


n=eval(input())
players=list(range(0,2**n))
pow=[]
for i in range ((2**n)-1):
	pow.append([int(x) for x in input().strip().split()])
for i in range(n):
	nextp=[0]*(len(players)/2)
	for j in range(0,len(players),2):
		p1,p2=players[j+1],players[j]
		if p1<p2:
			p1,p2=p2,p1
		x=pow[p1-1][p2]
		if x==0:
			nextp[j/2]=p2
		else:
			nextp[j/2]=p1
	players=nextp
print(players[0]+1)


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
n = int(input())
lines = []
winners = []
if n<1 or n> 10:
	print(" ")
else:
 #print "n",n,(2**n)-1
 for i in range(0,(2**n)-1):
	line = input()
	if line:
		lines.append(line.strip())
 #print lines 
 flag = 0
 if len(lines) < (2**n)-1:
 	print("")
 else:
  for i,line in enumerate(lines):
	if flag == 0:
		if int(line.split(" ")[-1]) == 0:
			winners.append(i+1)
		else:
			winners.append(i+2)
		flag = 1
	else:
		flag = 0
  #print winners
  index = 0
  winnerlen = len(winners)
  tempW = []
  while winnerlen != 1 and index < winnerlen:
	op1 = winners[index]
	op2 = winners[index+1]
	index += 2
	if int(lines[op2-2].split(" ")[op1 -1]) == 0:
		tempW.append(op1)
	else:
		tempW.append(op2)
	if index == winnerlen:
		winners  = tempW
		winnerlen = len(winners)
		index = 0
		tempW = []
		#print "change",winners,winnerlen
  print(winners[0])



mat= []	

	
def winner(num1,num2):
	if num2==0 and num1==0:
		if(mat[0]==1):
			return num1+2
		return num2+1
	if (mat[int(num1)][int(num2)]==1):
		return num1+2
	return num2+1

def simulator(thelist):
	listbuilder =[]
	if len(thelist)==1:
		return thelist[0]
	for i in range(0,len(thelist),2):
		listbuilder.append(winner(thelist[i+1]-2,thelist[i]-1))
	return simulator(listbuilder)

N = int(input())
r = []
r = int(eval(input()))
mat.append(r)
for _ in range((2**N)-2):
	r = [int(n) for n in input().split()]
	mat.append(r)

thefirstlist = list(range(1,(2**N)+1))
print(simulator(thefirstlist))



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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n = int(input())
l = []
for kappa in range((2**n)-1):
	x = list(map(int, input().split()))
	l.append(x)
	
lst = [[num for num in range(1,(2**n)+1)]]
for i in range(n):
	sent = []
	for j in range(0,2**(n-i)-1,2):
		p1 = lst[i][j]
		p2 = lst[i][j+1]
		if l[p2-2][p1-1] == 0:
			sent.append(p1)
		else:
			sent.append(p2)
	lst.append(sent)		
print(lst[n][0])            


#!/usr/bin/python -tt

import sys

def main():
	n = int(input())
	if n<1 or n>10 :
		sys.exit()
	temp = 2**n - 1
	a = []
	while temp >0 :
		temp -=1
		a.append( [int(val)for val in input().split()])
	p = list(range(1,2**n+1))
	p_temp = p
	while len(p)!= 1 :
		k = 0
		p_len = len(p)
		while k < p_len:
			i = p[k+1]
			j = p[k]
			temp = a[i-2][j-1]
			if temp == 0:
				p.append(j)
			else :
				p.append(i)
			k +=2
		del p[0:p_len]
	print(p[0])

if __name__ == "__main__":
	main()


n=int(input())
#j=2**n-1
n=2**n-1
win=[x for x in range(1,n+2)]
row=[]
mat=[]
win1=[]

#input triangular matrix
while(n):
	row=[int(i) for i in input().split()]
	mat.append(row)
	n=n-1


#append each round winners
while(True):
	if len(win)==1:
		break
	
	for i in range(0,len(win),2):
		p=win[i]
		q=win[i+1]
		r=max(p,q)
		s=min(p,q)
		aij=mat[r-2][s-1]
		if aij==0:
			win1.append(s)
		else:
			win1.append(r)
	win=win1[:]
	win1=[]
print(win[0])
	
	


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
n = int(input())
lines = []
winners = []
if n<1 or n> 10:
	print(" ")
else:
 #print "n",n,(2**n)-1
 for i in range(0,(2**n)-1):
	line = input()
	if line:
		lines.append(line.strip())
 #print lines 
 flag = 0
 if len(lines) < (2**n)-1:
 	print("")
 else:
  for i,line in enumerate(lines):
	#print "i",i
	#print "flag",flag
	#print "line",line
	if flag == 0:
		if int(line.split(" ")[-1]) == 0:
			winners.append(i+1)
		else:
			winners.append(i+2)
		flag = 1
	else:
		flag = 0
  #print winners
  index = 0
  winnerlen = len(winners)
  tempW = []
  while winnerlen != 1 and index < winnerlen:
	op1 = winners[index]
	op2 = winners[index+1]
	index += 2
	if int(lines[op2-2].split(" ")[op1 -1]) == 0:
		tempW.append(op1)
	else:
		tempW.append(op2)
	#print "tempW",tempW
	#print "ind ", index
	if index == winnerlen:
		winners  = tempW
		winnerlen = len(winners)
		index = 0
		tempW = []
		#print "change",winners,winnerlen
  print(winners[0])



N = eval(input())
A = [[]]
for ith in range(2**N - 1):
	A.append(list(map(int, input().split())))
players = list(range(2**N - 1, -1, -1))    
while len(players) > 1:
	pairs = list(zip(players[::2], players[1::2]))
	try:
		players = [x if A[x][y] else y for x, y in pairs]
	except:
		exit()
print(players[0] + 1)


arr = [[0],[0]]
t  = eval(input())
for i in range(1,2**t):
	new_list = [0]+list(map(int,input().split()))
	arr.append(new_list)
a = [i for i in range(1,2**t+1)]
for i in range(1,2*(2**t-1),2):
	for j in range(i-1,i):
		x,y = a[i],a[j]
		if arr[x][y] == 1:
			a.append(x)
		else:
			a.append(y)
print(a.pop())


def compare(firstIndex,secondIndex):
	if find[(firstIndex,secondIndex)] == firstIndex:
		return True
	return False

def MergeSort(A):
	if len(A) > 1:
		mid = len(A) // 2
		lefthalf = A[:mid]
		righthalf = A[mid:]
		MergeSort(lefthalf)
		MergeSort(righthalf)
		i = j = k = 0
		while i < len(lefthalf) and j < len(righthalf):
			if compare(lefthalf[i],righthalf[j]):
				A[k] = lefthalf[i]
				i = i + 1
			else:
				A[k] = righthalf[j]
				j = j + 1
			k = k + 1

		while i < len(lefthalf):
			A[k] = lefthalf[i]
			i = i + 1
			k = k + 1

		while j < len(righthalf):
			A[k] = righthalf[j]
			j = j + 1
			k = k + 1
	return A[0]
		
A = []    
val = []
find = {}
N = int(input())
i = 1
while(len(A) < (2**N)):
	A.append(i)
	i += 1
	
for i in range(1,(2**N)):
	val = input().split(' ')
	for index,j in enumerate(val):
		if j == '0':
			find[(index+1,i+1)] = (index+1)
		else :
			find[(index+1,i+1)] = i+1
		find[(i+1,index+1)] = find[(index+1,i+1)]
		
print(MergeSort(A))


player_info = []

def match(a,b):
	winner = 0	
	
	if player_info[b][a] == 0:
		winner = a
	else:
		winner = b
	

	return winner

t = int(input(''))

player_info = [[0 for x in range(2**t+2)] for y in range(2**t+2)]

for x in range(1,2**t):
	num_array = list(map(int, input().split()))
	for y in range(1,len(num_array)+1):		
		player_info[x+1][y] = num_array[y-1]


players = [x for x in range(1,2**t+1) ]

for z in range(t):	
	
	players_won = []
	k = len(players)/2
	for x in range(k):
		a = 2*x
		b = 2*x + 1
		
		
		players_won.append(match(players[a],players[b]))
	players = players_won

print(players[0])