The game of billiards involves two players knocking 3 balls around
on a green baize table. Well, there is more to it, but for our
purposes this is sufficient.
The game consists of several rounds and in each round both players
obtain a score, based on how well they played. Once all the rounds
have been played, the total score of each player is determined by
adding up the scores in all the rounds and the player with the higher
total score is declared the winner.
The Siruseri Sports Club organises an annual billiards game where
the top two players of Siruseri play against each other. The Manager
of Siruseri Sports Club decided to add his own twist to the game by
changing the rules for determining the winner. In his version, at the
end of each round, the cumulative score for each player is calculated, and the leader and her current lead are found. Once
all the rounds are over the player who had the maximum lead at the
end of any round in the game is declared the winner.

Consider the following score sheet for a game with 5 rounds:
RoundPlayer 1Player 2114082289134390110411210658890

The total scores of both players, the leader and the lead after
each round for this game is given below:RoundPlayer 1Player 2LeaderLead114082Player 1582229216Player 1133319326Player 274431432Player 215519522Player 23
Note that the above table contains the cumulative scores.
The winner of this game is Player 1 as he had the maximum lead (58
at the end of round 1) during the game.
Your task is to help the Manager find the winner and the winning
lead. You may assume that the scores will be such that there will
always be a single winner.  That is, there are no ties.
Input
The first line of the input will contain a single integer N (N
≤ 10000) indicating the number of rounds in the game.  Lines
2,3,...,N+1 describe the scores of the two players in the N rounds.
Line i+1 contains two integer Si and Ti, the scores of the Player 1
and 2 respectively, in round i.  You may assume that 1 ≤ Si ≤
1000 and 1 ≤ Ti ≤ 1000.  
Output
Your output must consist of a single line containing two integers
W and L, where W is 1 or 2 and indicates the winner and L is the
maximum lead attained by the winner.
Example
Input:
5
140 82
89 134
90 110
112 106
88 90

Output:
1 58

Source: codechef | Difficulty: EASY
Tags: Data structures

Implementation


Solutions:
n = int(input())
p1 = []
p2 = []
(a, b) = (0, 0)
for i in range(n):
	(s, t) = map(int, input().split(' '))
	a += s
	b += t
	if a > b:
		p1.append(a - b)
		p2.append(0)
	else:
		p2.append(b - a)
		p1.append(0)
if max(p1) > max(p2):
	print('1', max(p1), end=' ')
else:
	print('2', max(p2), end=' ')


n = int(input())
first = 0
second = 0
high = 0
for i in range(n):
	(one, two) = list(map(int, input().split()))
	first = first + one
	second = second + two
	d = first - second
	ab = abs(d)
	if d > 0 and d > high:
		high = d
		hero = 1
	elif d < 0 and ab > high:
		high = ab
		hero = 2
print(hero, high)


player1_score = 0
player2_score = 0
max_lead = 0
winner = 0
for i in range(int(input())):
	round_scores = input().split()
	player1_score += int(round_scores[0])
	player2_score += int(round_scores[1])
	lead = abs(player1_score - player2_score)
	if lead > max_lead:
		max_lead = lead
		if player1_score > player2_score:
			winner = 1
		else:
			winner = 2
print(winner, str(max_lead))


n = int(input())
play1 = 0
play2 = 0
max1 = 0
max2 = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	max1 += a
	max2 += b
	if max1 > max2:
		play1 = max(play1, max1 - max2)
	else:
		play2 = max(play2, max2 - max1)
if play1 > play2:
	print(1, play1)
else:
	print(2, play2)


t = int(input())
a1 = 0
b1 = 0
c = 0
for i in range(t):
	(a, b) = map(int, input().split())
	a1 = a1 + a
	b1 = b1 + b
	if abs(a1 - b1) > c:
		c = abs(a1 - b1)
		if a1 > b1:
			d = 1
		else:
			d = 2
print(d, c)


n = int(input())
p1 = 0
p2 = 0
l = 0
for i in range(n):
	(s1, s2) = map(int, input().split())
	p1 = p1 + s1
	p2 = p2 + s2
	d = p1 - p2
	if d > 0 and d > l:
		l = d
		lr = 1
	elif d < 0 and abs(d) > l:
		l = abs(d)
		lr = 2
print(lr, l)


n = int(input())
l = []
res = []
p1 = 0
p2 = 0
for i in range(n):
	d = []
	d = list(map(int, input().split(' ')))
	p1 += d[0]
	p2 += d[1]
	d[0] = p1
	d[1] = p2
	l.append(d)
	res.append([abs(d[0] - d[1]), 1 if d[0] > d[1] else 2])
maxi = -1
win = 0
for i in range(n):
	if res[i][0] > maxi:
		maxi = res[i][0]
		win = res[i][1]
print(win, ' ', maxi)


s1 = s2 = lead = 0
mlead1 = mlead2 = 0
for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	(s1, s2) = (s1 + x, s2 + y)
	if s1 > s2:
		lead = s1 - s2
		mlead1 = max(mlead1, lead)
	else:
		lead = s2 - s1
		mlead2 = max(mlead2, lead)
if mlead1 < mlead2:
	print('2', mlead2)
else:
	print('1', mlead1)


n = int(input())
player1 = 0
player2 = 0
lead = 0
winner = 0
for i in range(n):
	(s, t) = map(int, input().split())
	player1 += s
	player2 += t
	curr_lead = player1 - player2
	if curr_lead > 0 and curr_lead > lead:
		lead = curr_lead
		winner = 1
	elif curr_lead < 0 and abs(curr_lead) > lead:
		lead = abs(curr_lead)
		winner = 2
print(winner, lead)


try:
	t = int(input())
	l1 = []
	l2 = []
	n1 = 0
	n2 = 0
	for i in range(t):
		(x, y) = list(map(int, input().split()))
		n1 += x
		n2 += y
		if n1 > n2:
			l1.append(n1 - n2)
			l2.append(0)
		else:
			l1.append(0)
			l2.append(n2 - n1)
	m1 = max(l1)
	m2 = max(l2)
	if m1 > m2:
		print(1, m1)
	else:
		print(2, m2)
except:
	pass


p1 = []
p2 = []
a = int(input())
for i in range(a):
	(x, y) = map(int, input().split())
	if len(p1) == 0 and len(p2) == 0:
		p1.append(x)
		p2.append(y)
	else:
		p1.append(x + p1[-1])
		p2.append(y + p2[-1])
dif1 = []
dif2 = []
for i in range(a):
	dif1.append(p1[i] - p2[i])
	dif2.append(p2[i] - p1[i])
if max(dif1) > max(dif2):
	print(1, max(dif1))
else:
	print(2, max(dif2))


def max_find(a, b):
	return (maxi_lead, maxi)
(p1, p2) = (0, 0)
(maxi, maxi_lead) = (0, 0)
for i in range(int(input())):
	(a, b) = map(int, input().split(' '))
	p1 += a
	p2 += b
	if p1 > p2:
		difference = p1 - p2
		if maxi < difference:
			maxi = difference
			maxi_lead = 1
	elif p2 > p1:
		difference = p2 - p1
		if maxi < difference:
			maxi = difference
			maxi_lead = 2
print(maxi_lead, maxi)


n = int(input())
k = 0
l = 0
m1 = 0
m2 = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	m1 += a
	m2 += b
	if m1 > m2:
		k = max(k, m1 - m2)
	else:
		l = max(l, m2 - m1)
if k > l:
	print(1, k)
else:
	print(2, l)


n = int(input())
p1 = 0
p2 = 0
lead = 0
winner = 0
for i in range(n):
	(player1, player2) = list(map(int, input().split()))
	p1 += player1
	p2 += player2
	if abs(p1 - p2) > lead:
		lead = abs(p1 - p2)
		if p2 > p1:
			winner = 2
		else:
			winner = 1
print(winner, lead)


t = int(input())
player1 = 0
player2 = 0
max1 = 0
max2 = 0
for i in range(t):
	(a, b) = map(int, input().split())
	max1 += a
	max2 += b
	if max1 > max2:
		player1 = max(player1, max1 - max2)
	else:
		player2 = max(player2, max2 - max1)
if player1 > player2:
	print(1, player1)
else:
	print(2, player2)


p1 = 0
p2 = 0
m1 = 0
m2 = 0
for i in range(int(input())):
	(a, b) = map(int, input().split())
	m1 += a
	m2 += b
	if m1 > m2:
		p1 = max(p1, m1 - m2)
	else:
		p2 = max(p2, m2 - m1)
if p1 > p2:
	print(1, p1)
else:
	print(2, p2)


pinputA = 0
pinputB = 0
MaxDiff = 0
Win = -1
for i in range(int(input())):
	(A, B) = map(int, input().split())
	Acum = A + pinputA
	Bcum = B + pinputB
	pinputA = Acum
	pinputB = Bcum
	if Acum - Bcum > MaxDiff:
		MaxDiff = Acum - Bcum
		Win = 1
	elif Bcum - Acum > MaxDiff:
		MaxDiff = Bcum - Acum
		Win = 2
print(Win, MaxDiff)


n = int(input())
a = []
TA = 0
TB = 0
for i in range(n):
	(x, y) = map(int, input().split())
	TA += x
	TB += y
	if TA > TB:
		a.append(1)
		a.append(TA - TB)
	else:
		a.append(2)
		a.append(TB - TA)
print(a[a.index(max(a)) - 1], max(a))


n = int(input())
l = []
l1 = []
p = 0
m = 0
while n > 0:
	(x, y) = map(int, input().split())
	x += p
	y += m
	if x > y:
		z = x - y
		r = 1
	else:
		z = y - x
		r = 2
	p = x
	m = y
	l.append(r)
	l1.append(z)
	n -= 1
t = max(l1)
e = l1.index(t)
print(l[e], t)


t = int(input())
l1 = 0
l2 = 0
s1 = 0
s2 = 0
for i in range(t):
	(ss1, ss2) = list(map(int, input().split()))
	s1 += ss1
	s2 += ss2
	if s1 - s2 < 0:
		if s2 - s1 >= l2:
			l2 = s2 - s1
	elif s1 - s2 >= l1:
		l1 = s1 - s2
if l1 > l2:
	print(1, l1)
else:
	print(2, l2)


n = int(input())
max = 0
w = -1
p = 0
q = 0
for i in range(n):
	(x, y) = map(int, input().split())
	p = p + x
	q = q + y
	if abs(p - q) > max:
		max = abs(p - q)
		if p > q:
			w = 1
		else:
			w = 2
print(w, max)


n = int(input())
(p1, p2) = (0, 0)
max_lead = 0
max_lead_player = 0
for i in range(n):
	(s1, s2) = map(int, input().split())
	p1 += s1
	p2 += s2
	diff = abs(p1 - p2)
	if diff > max_lead:
		max_lead = diff
		if p1 > p2:
			max_lead_player = 1
		else:
			max_lead_player = 2
print(max_lead_player, max_lead)


n = int(input())
p1 = 0
p2 = 0
k = 0
for i in range(n):
	(n1, n2) = map(int, input().split())
	p1 += n1
	p2 += n2
	diff = p1 - p2
	if diff > 0 and diff > k:
		k = diff
		l = 1
	elif diff < 0 and abs(diff) > k:
		k = abs(diff)
		l = 2
print(l, k)


t = int(input())
l1 = []
l2 = []
p1 = 0
p2 = 0
for _ in range(t):
	(n, m) = map(int, input().split())
	p1 += n
	p2 += m
	if p1 > p2:
		l = p1 - p2
		l1.append(l)
		l2.append(0)
	else:
		l = p2 - p1
		l1.append(0)
		l2.append(l)
w1 = max(l1)
w2 = max(l2)
if w1 > w2:
	print('1', w1, sep=' ')
else:
	print('2', w2, sep=' ')


N = int(input())
score1 = score2 = lead = max_lead = 0
for i in range(N):
	(s, t) = map(int, input().split())
	score1 += s
	score2 += t
	if score1 > score2:
		lead = score1 - score2
		if lead > max_lead:
			max_lead = lead
			winner = 1
	else:
		lead = score2 - score1
		if lead > max_lead:
			max_lead = lead
			winner = 2
print(winner, max_lead)


p1 = 0
p2 = 0
p = '1'
lead = 0
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	p1 = p1 + a
	p2 = p2 + b
	l = abs(p1 - p2)
	if lead < l:
		lead = l
		if p1 > p2:
			p = '1'
		else:
			p = '2'
print(p, lead)


p1 = 0
p2 = 0
s1 = 0
s2 = 0
for i in range(int(input())):
	(x, y) = map(int, input().split())
	s1 += x
	s2 += y
	if s1 > s2:
		p1 = max(p1, s1 - s2)
	else:
		p2 = max(p2, s2 - s1)
if p1 > p2:
	print('1', p1)
else:
	print('2', p2)


n = int(input())
p1 = 0
p2 = 0
max1 = 0
max2 = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	max1 += a
	max2 += b
	if max1 > max2:
		p1 = max(p1, max1 - max2)
	else:
		p2 = max(p2, max2 - max1)
if p1 > p2:
	print(1, p1)
else:
	print(2, p2)


l = 0
m = 0
p1 = [0]
p2 = [0]
l1 = [0]
l2 = [0]
for i in range(int(input())):
	(a, b) = map(int, input().split())
	p1.append(a + l)
	p2.append(b + m)
	l = p1[-1]
	m = p2[-1]
for (x, y) in zip(p1, p2):
	d = x - y
	if d > 0:
		l1.append(d)
	if d < 0:
		l2.append(abs(d))
if max(l1) > max(l2):
	print(1, end=' ')
	print(max(l1))
else:
	print(2, end=' ')
	print(max(l2))


n = int(input())
l = []
x = 0
y = 0
for i in range(n):
	(a, b) = map(int, input().split())
	x = x + a
	y = y + b
	l.append(x - y)
q = abs(max(l))
w = abs(min(l))
if w > q:
	r = 2
	q = w
else:
	r = 1
r = [r, q]
for p in r:
	print(p, end=' ')


val = 0
A = 0
B = 0
for a in range(int(input())):
	(c, d) = input().split()
	A += int(c)
	B += int(d)
	b = abs(A - B)
	if b > val:
		val = b
		if int(c) > int(d):
			w = 1
		else:
			w = 2
print(str(w) + ' ' + str(val))


n = int(input())
i = 0
s1 = 0
s2 = 0
m = 0
w = 0
while i < n:
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	s1 += a
	s2 += b
	if s1 > s2:
		l = s1 - s2
		if l > m:
			m = l
			w = 1
	else:
		l = s2 - s1
		if l > m:
			m = l
			w = 2
	i += 1
print(w, m)


t = int(input())
lead = 0
s1 = 0
s2 = 0
for i in range(t):
	(a, b) = map(int, input().split())
	s1 = s1 + a
	s2 = s2 + b
	sub = abs(s1 - s2)
	if sub > lead:
		lead = sub
		if s1 > s2:
			winner = 1
		elif s2 > s1:
			winner = 2
print(winner, lead)


t = int(input())
l = []
l1 = []
p1 = 0
p2 = 0
for i in range(t):
	(n, m) = map(int, input().split())
	p1 += n
	p2 += m
	if p1 > p2:
		l.append(p1 - p2)
		l1.append(0)
	else:
		l.append(0)
		l1.append(p2 - p1)
m1 = max(l)
m2 = max(l1)
if m1 > m2:
	print(1, m1)
else:
	print(2, m2)


rounds = input()
rounds = int(rounds)
lead = 0
s1 = 0
s2 = 0
for i in range(rounds):
	scores = input()
	scores = scores.split()
	s1 += int(scores[0])
	s2 += int(scores[1])
	if s1 - s2 > lead:
		leader = 1
		lead = s1 - s2
	elif s2 - s1 > lead:
		leader = 2
		lead = s2 - s1
print(str(leader) + ' ' + str(lead))


n = int(input())
pl1 = 0
pl2 = 0
mx1 = 0
mx2 = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	mx1 += a
	mx2 += b
	if mx1 > mx2:
		pl1 = max(pl1, mx1 - mx2)
	else:
		pl2 = max(pl2, mx2 - mx1)
if pl1 > pl2:
	print(1, pl1)
else:
	print(2, pl2)


(x1, x2) = (0, 0)
(m1, m2) = (0, 0)
for i in range(int(input())):
	(a, b) = map(int, input().split())
	m1 += a
	m2 += b
	if m1 > m2:
		x1 = max(x1, m1 - m2)
	else:
		x2 = max(x2, m2 - m1)
if x1 > x2:
	print(1, x1)
else:
	print(2, x2)


l = []
m = []
c = []
(s, k) = (0, 0)
for i in range(int(input())):
	(a, b) = map(int, input().split(' '))
	s = s + a
	k = k + b
	l.append(s)
	m.append(k)
for j in range(len(l)):
	c.append(abs(l[j] - m[j]))
if l[c.index(max(c))] > m[c.index(max(c))]:
	print('1', end=' ')
else:
	print('2', end=' ')
print(max(c))


n = int(input())
max_lead = 0
winner = 0
p1 = 0
p2 = 0
for i in range(n):
	(x, y) = map(int, input().split())
	p1 += x
	p2 += y
	sub = abs(p1 - p2)
	if sub > max_lead:
		max_lead = sub
		if p1 > p2:
			winner = 1
		elif p1 < p2:
			winner = 2
print(winner, max_lead)


N = int(input())
player1_score = 0
player2_score = 0
max_lead = 0
winner = 0
for i in range(N):
	(s, t) = map(int, input().split())
	player1_score += s
	player2_score += t
	lead = abs(player1_score - player2_score)
	if lead > max_lead:
		max_lead = lead
		if player1_score > player2_score:
			winner = 1
		else:
			winner = 2
print(winner, max_lead)


n = int(input())
g = 0
(c, d) = (0, 0)
for i in range(n):
	(a, b) = map(int, input().split())
	c = a + c
	d = b + d
	if c > d:
		lead = c - d
		if lead > g:
			g = lead
			leader = 1
	else:
		lead = d - c
		if lead > g:
			g = lead
			leader = 2
print(leader, g)


n = int(input())
player1_score = 0
player2_score = 0
lead = 0
for t in range(n):
	(score1, score2) = list(map(int, input().split()))
	player1_score = player1_score + score1
	player2_score = player2_score + score2
	diff = player1_score - player2_score
	if diff > 0 and diff > lead:
		lead = diff
		leader = 1
	elif diff < 0 and abs(diff) > lead:
		lead = abs(diff)
		leader = 2
print(leader, lead)


play1 = 0
play2 = 0
max1 = 0
max2 = 0
for _ in range(int(input())):
	(S, T) = map(int, input().split())
	max1 += S
	max2 += T
	if max1 > max2:
		play1 = max(play1, max1 - max2)
	else:
		play2 = max(play2, max2 - max1)
if play1 > play2:
	print(1, play1)
else:
	print(2, play2)


n = int(input())
player1_score = 0
Player2_score = 0
lead = 0
for i in range(n):
	(score1, score2) = map(int, input().split())
	player1_score = player1_score + score1
	Player2_score = Player2_score + score2
	diff = player1_score - Player2_score
	if diff > 0 and diff > lead:
		lead = diff
		leader = 1
	elif diff < 0 and abs(diff) > lead:
		lead = abs(diff)
		leader = 2
print(leader, lead)


n = int(input())
a = 0
b = 0
max = 0
for i in range(n):
	(x, y) = map(int, input().split())
	x = a + x
	y = b + y
	if abs(x - y) > max:
		max = abs(x - y)
		if x > y:
			w = 1
		else:
			w = 2
	a = x
	b = y
print(w, max)


def findWinner():
	n = int(input())
	p1 = p2 = 0
	p1lead = p2lead = 0
	winner = 1
	diff1 = diff2 = 0
	for i in range(n):
		(p1score, p2score) = list(map(int, input().split()))
		p1 += p1score
		p2 += p2score
		if p1 > p2:
			p1lead += 1
			diff1 = max(diff1, p1 - p2)
		else:
			p2lead += 1
			diff2 = max(diff2, p2 - p1)
	winner = 1 if diff1 > diff2 else 2
	lead = max(diff1, diff2)
	print(winner, lead)
findWinner()


import sys
n = int(input())
l = [0] * 2
a = 0
b = 0
for i in range(n):
	(a1, b1) = map(int, input().split())
	a += a1
	b += b1
	if a > b:
		if l[0] < a - b:
			l[0] = a - b
	elif l[1] < b - a:
		l[1] = b - a
	m = max(l)
print(l.index(m) + 1, m)


a = int(input())
(g, u, m, r) = (0, 0, 0, 0)
f = []
t = []
for i in range(a):
	(b, c) = map(int, input().split())
	g += b
	u += c
	m = max(g, u)
	if max(g, u) == g:
		t.append('1')
	else:
		t.append('2')
	r = min(g, u)
	f.append(m - r)
h = max(f)
print(t[f.index(h)], h)


maxLead = 0
a_sum = 0
b_sum = 0
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	a_sum += a
	b_sum += b
	if a_sum > b_sum:
		lead = a_sum - b_sum
		if lead > maxLead:
			maxLead = lead
			w = 1
	else:
		lead = b_sum - a_sum
		if lead > maxLead:
			maxLead = lead
			w = 2
print(w, maxLead)


N = int(input())
player1 = 0
player2 = 0
score1 = 0
score2 = 0
for _ in range(N):
	(p1, p2) = map(int, input().split())
	score1 += p1
	score2 += p2
	if score1 > score2:
		player1 = max(player1, score1 - score2)
	else:
		player2 = max(player2, score2 - score1)
print(1, player1) if player1 > player2 else print(2, player2)


n = int(input())
s = 0
t = 0
l1 = 0
l2 = 0
for i in range(n):
	(a, b) = map(int, input().split(' '))
	s = s + a
	t = t + b
	if s > t and s - t > l1:
		l1 = s - t
	elif s < t and t - s > l2:
		l2 = t - s
if l1 > l2:
	print(1, l1)
else:
	print(2, l2)


try:
	n1 = int(input())
	wina = winb = ma = mb = n = m = 0
	for i in range(n1):
		(a, b) = list(map(int, input().split()))
		n += a
		m += b
		if n > m and n - m > ma:
			ma = n - m
		elif n < m and m - n > mb:
			mb = m - n
	if ma > mb:
		print('1', ma)
	elif ma < mb:
		print('2', mb)
except:
	pass


p1 = 0
p2 = 0
max1 = 0
max2 = 0
for i in range(int(input())):
	(x, y) = map(int, input().split())
	max1 += x
	max2 += y
	if max1 > max2:
		p1 = max(p1, max1 - max2)
	else:
		p2 = max(p2, max2 - max1)
if p1 > p2:
	print('1', p1)
else:
	print('2', p2)


N = int(input())
p1 = 0
p2 = 0
max_score1 = 0
max_score2 = 0
for i in range(N):
	(A, B) = map(int, input().split())
	max_score1 += A
	max_score2 += B
	if max_score1 > max_score2:
		p1 = max(p1, max_score1 - max_score2)
	else:
		p2 = max(p2, max_score2 - max_score1)
if p1 > p2:
	print(1, p1)
else:
	print(2, p2)


a = 0
b = 0
maxi = 0
for i in range(int(input())):
	(p1, p2) = map(int, input().split())
	a = a + p1
	b = b + p2
	if abs(a - b) > maxi:
		maxi = abs(a - b)
		if a > b:
			d = 1
		else:
			d = 2
print(d, maxi)