starting-game-development

Every one is now a days playing games on their smartphones for passing free time. Because of which there are number of game developing companies growing in the market. Not only that, each company is now flooding the market with a lot of games. With such a huge number of games in the market, for each company, with millions of users, keeping track of all the data and maintaining good user experience is now a big problem for them.

One of the very important aspect of building these games is the ability to maintain all the information about the user. 
This is a very important step in maintaining the user experience. No user would want to restart from the beginning of the game every time he/she restarts it. They would just then switch to a competitive game developer and that is not good for business.
Most of the games now have a similar structure and some of the game companies follows the logic below in their games to handle this problem:
The game has N different parameters on which a user's strength in the game is calculated. The game has a total of M different levels of play.
    And hence each parameter also gets these M levels of granularity, i.e. for each parameter itself a user can be on any one of those M levels.
For each parameter, the following is done:
    
User's strength on the parameter is calculated.
Each of the M levels have some strength value associated with them such that the strength value grows when you move from a lower level to the higher level. It may happen that any two consecutive levels have same required strength.
If a user's strength is more than or equal to the strength value associated with a level, he/she is said to be fit to be on that level of the game
        for this parameter.
The level for this parameter is the maximum level for which a user satisfies the above criteria.
The level of the game a user is on, is decided from its level in all of the N parameters of the game as follows:
    
For each parameter, the level user is on for that parameter is computed as described above.
The level of game at which a user is the minimum of all the levels in each of the N parameters.

You are now interested in building a game for the smartphone user's as well. But before that, you would need to solve this problem effeciently.
Given the strength of user's for each parameter, print the level they are on.

Input:
The first line of the input contains three space separated integers, N, M and Q. (N is the number of parameters, M is the number of levels, and Q is the 
number of queries that you have to answer.) 
Next N line contains M space separated integers, the i^th line contains the M strength values for the M levels of the i^th
level.

Next Q lines, each contains N space separated integers, the strength of a user in each of the N parameters.

Output:
Print Q lines, one for each query. For each query, print the level on which that user is.

Constraints:
1 ≤ N ≤ 100 
1 ≤ M ≤ 5000 
1 ≤ Q ≤ 5000  
Every input will fit in an integer.

SAMPLE INPUT
2 3 3
10 20 30
7 14 100
11 7
35 13
100 1002

SAMPLE OUTPUT
1
1
3

Source: hackerearth | Difficulty: MEDIUM


Solutions:
import bisect
n,m,q = list(map(int,input().split()))
dn = n
ls = []
while n:
	ls.append(list(map(int,input().split())))
	n -= 1
while q:
	s = list(map(int, input().split()))
	a = 0
	r = []
	while a < dn: 
		r.append(bisect.bisect(ls[a],s[a]))
		a += 1
	print(min(r))
	q -= 1


import bisect

N,M,Q = list(map(int,input().split()))
levels = []
for _ in range(N):
	levels.append(list(map(int,input().split())))
	
for _ in range(Q):
	q=list(map(int,input().split()))
	m=M
	for i in range(N):
		m = min(m,bisect.bisect_right(levels[i],q[i],0,m))
	print(m)


import bisect

N,M,Q = list(map(int,input().split()))
levels = []
for _ in range(N):
	levels.append(list(map(int,input().split())))
	
for _ in range(Q):
	q=list(map(int,input().split()))
	m=M
	for i in range(N):
		m = min(m,bisect.bisect_right(levels[i],q[i]))
	print(m)


arr = list(map(int, list(input().strip().split(' '))))
n = arr[0]
m = arr[1]
q = arr[2]

arr_m = []

for i in range(n):
	arr_temp = list(map(int, list(input().strip().split(' '))))	
	arr_m.append(arr_temp)

for i in range(q):
	arr_t = list(map(int, list(input().strip().split(' '))))
	arr_l = []
	for i in range(len(arr_t)):
		a_temp = arr_m[i]
		num = arr_t[i]
		low = 0
		high = len(a_temp) - 1
		while(low < high):
			mid = (low+high)//2
			if a_temp[mid] <= num:
				low = mid + 1
			else:
				high = mid
		if a_temp[len(a_temp)-1] < num:
			arr_l.append(len(a_temp))
		else:
			arr_l.append(low)
		#print arr_l
	print(min(arr_l))


from bisect import *
n, m, q = [int(i) for i in input().split()]

a = []
for i in range(n):
	a.append([int(j) for j in input().split()])

for i in range(q):
	b = [int(j) for j in input().split()]
	m = 10000000
	for j in range(len(b)):
		m = min(bisect(a[j], b[j]), m)
	print(m)


# https://www.hackerearth.com/problem/algorithm/starting-game-development/
import sys

n, m, q = [int(x) for x in sys.stdin.readline().split()]
params = [[] for _ in range(n)]
for param in params:
	param.extend([int(x) for x in sys.stdin.readline().split()])
	
def level(grade, x):
	start = 0
	end = len(grade) - 1

	while (1):
		if end - start < 2:
			if grade[end] <= x:
				return end
			if grade[start] <= x:
				return start
			return 0
		
		mid = int((start + end)/2)
		#print(start, mid, end, 'looking for', x, 'in', grade[mid], grade[mid + 1])
		if grade[mid] <= x and grade[mid + 1] > x:
			return mid
		elif grade[mid] <= x and grade[mid + 1] <= x:
			start = mid + 1
		elif grade[mid] > x:
			end = mid


for _ in range(q):
	player = [int(x) for x in sys.stdin.readline().split()]
	print((min([level(params[i], player[i]) for i in range(n)]) + 1))


# https://www.hackerearth.com/problem/algorithm/starting-game-development/
import sys

n, m, q = [int(x) for x in sys.stdin.readline().split()]
params = [[] for _ in range(n)]
for param in params:
	param.extend([int(x) for x in sys.stdin.readline().split()])
	
def level(grade, x):
	start = 0
	end = len(grade) - 1

	while (1):
		if end - start < 2:
			if grade[end] <= x:
				return end
			if grade[start] <= x:
				return start
			return 0
		
		mid = int((start + end)/2)
		#print(start, mid, end, 'looking for', x, 'in', grade[mid], grade[mid + 1])
		if grade[mid] <= x and grade[mid + 1] > x:
			return mid
		elif grade[mid] <= x and grade[mid + 1] <= x:
			start = mid + 1
		elif grade[mid] > x:
			end = mid


for _ in range(q):
	player = [int(x) for x in sys.stdin.readline().split()]
	print((min([level(params[i], player[i]) for i in range(n)]) + 1))


import bisect

N,M,Q = list(map(int,input().split()))
levels = []
for _ in range(N):
	levels.append(list(map(int,input().split())))
	
for _ in range(Q):
	q=list(map(int,input().split()))
	m=bisect.bisect_right(levels[0],q[0])
	#print "initial",m
	for i in range(1,N):
		if m==0:
			break
		while q[i]<levels[i][m-1]:
			m-=1
	print(m)


import bisect
 
N,M,Q = list(map(int,input().split()))
levels = []
for _ in range(N):
	levels.append(list(map(int,input().split())))
	
for _ in range(Q):
	q=list(map(int,input().split()))
	m=M
	for i in range(N):
		m = min(m,bisect.bisect_right(levels[i],q[i],0,m))
	print(m)