A group of n friends enjoys playing popular video game Toda 2. There is a rating system describing skill level of each player, initially the rating of the i-th friend is r_{i}.

The friends decided to take part in the championship as a team. But they should have equal ratings to be allowed to compose a single team consisting of all n friends. So the friends are faced with the problem: how to make all their ratings equal.

One way to change ratings is to willingly lose in some matches. Friends can form a party consisting of two to five (but not more than n) friends and play a match in the game. When the party loses, the rating of each of its members decreases by 1. A rating can't become negative, so r_{i} = 0 doesn't change after losing.

The friends can take part in multiple matches, each time making a party from any subset of friends (but remember about constraints on party size: from 2 to 5 members).

The friends want to make their ratings equal but as high as possible.

Help the friends develop a strategy of losing the matches so that all their ratings become equal and the resulting rating is maximum possible.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 100) — the number of friends.

The second line contains n non-negative integers r_1, r_2, ..., r_{n} (0 ≤ r_{i} ≤ 100), where r_{i} is the initial rating of the i-th friend.


-----Output-----

In the first line, print a single integer R — the final rating of each of the friends.

In the second line, print integer t — the number of matches the friends have to play. Each of the following t lines should contain n characters '0' or '1', where the j-th character of the i-th line is equal to:

  '0', if friend j should not play in match i,  '1', if friend j should play in match i. 

Each line should contain between two and five characters '1', inclusive.

The value t should not exceed 10^4, it is guaranteed that such solution exists. 

Remember that you shouldn't minimize the value t, but you should maximize R. If there are multiple solutions, print any of them.


-----Examples-----
Input
5
4 5 1 7 4

Output
1
8
01010
00011
01010
10010
00011
11000
00011
11000

Input
2
1 2

Output
0
2
11
11

Input
3
1 1 1

Output
1
0

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Implementation

Greedy algorithms


Solutions:
from operator import itemgetter

class CodeforcesTask730ASolution:

	def __init__(self):
		self.result = ''
		self.players = 0
		self.rating = []

	def read_input(self):
		self.players = int(input())
		self.rating = [int(x) for x in input().split(' ')]

	def process_task(self):
		if self.players > 2:
			moves = []
			players = [[x + 1, self.rating[x]] for x in range(self.players)]
			players.sort(key=itemgetter(1), reverse=True)
			while players[1][1] != players[-1][1]:
				players[0][1] = max(0, players[0][1] - 1)
				players[1][1] = max(0, players[1][1] - 1)
				moves.append([players[0][0], players[1][0]])
				players.sort(key=itemgetter(1), reverse=True)
			if players[0][1] != players[-1][1]:
				added = False
				for m in moves:
					if not players[0][0] in m:
						m.append(players[0][0])
						players[0][1] = max(0, players[0][1] - 1)
						added = True
						break
				if not added:
					moves.append([players[-1][0], players[0][0]])
					players[0][1] = max(0, players[0][1] - 1)
					players[-1][1] = max(0, players[-1][1] - 1)
					players.sort(key=itemgetter(1), reverse=True)
					while players[0][1] != players[-1][1] and players[1][1] != players[-1][1]:
						players[0][1] = max(0, players[0][1] - 1)
						players[1][1] = max(0, players[1][1] - 1)
						moves.append([players[0][0], players[1][0]])
						players.sort(key=itemgetter(1), reverse=True)
					if players[0][1] != players[-1][1]:
						added = False
						for m in moves:
							if not players[0][0] in m:
								m.append(players[0][0])
								players[0][1] = max(0, players[0][1] - 1)
								added = True
								break
						if not added:
							moves.append([players[-1][0], players[0][0]])
							players[0][1] = max(0, players[0][1] - 1)
							players[-1][1] = max(0, players[-1][1] - 1)
							players.sort(key=itemgetter(1), reverse=True)
							while players[0][1] != players[-1][1] and players[1][1] != players[-1][1]:
								players[0][1] = max(0, players[0][1] - 1)
								players[1][1] = max(0, players[1][1] - 1)
								moves.append([players[0][0], players[1][0]])
								players.sort(key=itemgetter(1), reverse=True)
							if players[0][1] != players[-1][1]:
								added = False
								for m in moves:
									if not players[0][0] in m:
										m.append(players[0][0])
										players[0][1] = max(0, players[0][1] - 1)
										added = True
										break
								if not added:
									moves.append([players[-1][0], players[0][0]])
									players[0][1] = max(0, players[0][1] - 1)
									players[-1][1] = max(0, players[-1][1] - 1)
									players.sort(key=itemgetter(1), reverse=True)
									while players[0][1] != players[-1][1] and players[1][1] != players[-1][1]:
										players[0][1] = max(0, players[0][1] - 1)
										players[1][1] = max(0, players[1][1] - 1)
										moves.append([players[0][0], players[1][0]])
										players.sort(key=itemgetter(1), reverse=True)
									if players[0][1] != players[-1][1]:
										added = False
										for m in moves:
											if not players[0][0] in m:
												m.append(players[0][0])
												players[0][1] = max(0, players[0][1] - 1)
												added = True
												break
										if not added:
											moves.append([players[-1][0], players[0][0]])
											players[0][1] = max(0, players[0][1] - 1)
											players[-1][1] = max(0, players[-1][1] - 1)
											players.sort(key=itemgetter(1), reverse=True)
											while players[0][1] != players[-1][1] and players[1][1] != players[-1][1]:
												players[0][1] = max(0, players[0][1] - 1)
												players[1][1] = max(0, players[1][1] - 1)
												moves.append([players[0][0], players[1][0]])
												players.sort(key=itemgetter(1), reverse=True)
											if players[0][1] != players[-1][1]:
												added = False
												for m in moves:
													if not players[0][0] in m:
														m.append(players[0][0])
														players[0][1] = max(0, players[0][1] - 1)
														added = True
														break
												if not added:
													print('edge case 5')
			players.sort(key=itemgetter(1), reverse=True)
			print(players[-1][1])
			print(len(moves))
			for m in moves:
				print(''.join(['1' if x + 1 in m else '0' for x in range(self.players)]))
		elif self.rating[0] == self.rating[1]:
			print(self.rating[0])
			print('0')
		else:
			print('0')
			print(max(self.rating))
			for x in range(max(self.rating)):
				print('11')

	def get_result(self):
		return self.result

def __starting_point():
	Solution = CodeforcesTask730ASolution()
	Solution.read_input()
	Solution.process_task()
	print(Solution.get_result())
__starting_point()


n = int(input())
R = list(map(int, input().split()))
Time = 0
check = False
Output = []
while check == False:
	pos_max = []
	pos_sec = []
	Max_sec = -1
	Max_num = 0
	Max = -1
	Min = 999999999
	Time += 1
	string = ''
	for i in range(len(R) - 1, -1, -1):
		if R[i] < Min:
			Min = R[i]
		if R[i] > Max:
			Max_sec = Max
			Max = R[i]
			pos_sec = pos_max
			pos_max = []
			pos_max.append(i)
			Max_num = 1
		elif R[i] == Max:
			Max_num += 1
			pos_max.append(i)
		elif R[i] > Max_sec:
			Max_sec = R[i]
			pos_sec = []
			pos_sec.append(i)
	if Max == Min:
		check = True
		break
	if Max_num > 1:
		if Max_num % 2 == 1:
			j = 0
			some = []
			for k in range(n - 1, -1, -1):
				if pos_max[j] == k:
					if R[k] != 0:
						R[k] -= 1
					some.append(k)
					j += 1
					if j > 2:
						j = 0
			j = len(some) - 1
			for k in range(n):
				if some[j] == k:
					string += '1'
					j -= 1
					if j < 0:
						j = 0
				else:
					string += '0'
		else:
			j = 0
			some = []
			for k in range(n - 1, -1, -1):
				if pos_max[j] == k:
					if R[k] != 0:
						R[k] -= 1
					some.append(k)
					j += 1
					if j > 1:
						j = 1
			j = len(some) - 1
			for k in range(n):
				if some[j] == k:
					string += '1'
					j -= 1
					if j < 0:
						j = 0
				else:
					string += '0'
	else:
		for k in range(n):
			if pos_max[0] == k:
				if R[k] != 0:
					R[k] -= 1
				string += '1'
				continue
			if pos_sec[0] == k:
				if R[k] != 0:
					R[k] -= 1
				string += '1'
				continue
			string += '0'
	Output.append(string)
print(Max)
print(Time - 1)
for i in range(len(Output)):
	print(Output[i])


import heapq

def solve_for_0(d, max_, ans):
	pos_M = list(d[max_])[0]
	pos_m = list(d[0])[0]
	for _ in range(max_):
		ans.append([pos_M, pos_m])

def solve_one_seg(d, max_, min_, ans):
	seg = list(d[max_])
	n = len(seg)
	if n <= 5:
		for _ in range(max_ - min_):
			ans.append(seg)
	else:
		ori = []
		for i in range(0, n, 2):
			if i == n - 1:
				ori[-1].append(seg[i])
			else:
				ori.append([seg[i], seg[i + 1]])
		for _ in range(max_ - min_):
			ans.extend(ori)

def push(d, x, val, i):
	if x not in d:
		d[x] = set()
	if val == 1:
		d[x].add(i)
	else:
		d[x].remove(i)
	if len(d[x]) == 0:
		del d[x]

def check(d):
	if len(d) != 2:
		return ('none', None)
	max_ = max(list(d.keys()))
	min_ = min(list(d.keys()))
	if len(d[max_]) >= 2:
		return ('seg', [max_, min_])
	elif min_ == 0:
		return ('0', [max_])
	return ('none', None)

def pr(ans, n):
	print(len(ans))
	arr = [[0] * n for _ in range(len(ans))]
	for (i, val) in enumerate(ans):
		for ind in val:
			arr[i][ind] = 1
	S = ''
	for s in arr:
		S += ''.join([str(x) for x in s])
		S += '\n'
	print(S)
n = int(input())
arr = list(map(int, input().split()))
ans = []
Q = []
d = {}
for (i, x) in enumerate(arr):
	push(d, x, 1, i)
	heapq.heappush(Q, (-x, x, i))
if len(d) == 1:
	print(list(d.keys())[0])
	print(0)
else:
	while True:
		(type_, arg) = check(d)
		if type_ == 'none':
			(val1, num1, i1) = heapq.heappop(Q)
			(val2, num2, i2) = heapq.heappop(Q)
			push(d, num1, -1, i1)
			push(d, num2, -1, i2)
			ans.append([i1, i2])
			new1 = max(0, num1 - 1)
			new2 = max(0, num2 - 1)
			heapq.heappush(Q, (-new1, new1, i1))
			heapq.heappush(Q, (-new2, new2, i2))
			push(d, new1, 1, i1)
			push(d, new2, 1, i2)
		elif type_ == 'seg':
			(max_, min_) = (arg[0], arg[1])
			solve_one_seg(d, max_, min_, ans)
			print(min_)
			pr(ans, n)
			break
		else:
			max_ = arg[0]
			solve_for_0(d, max_, ans)
			print(0)
			pr(ans, n)
			break


import collections

def temp(list1):
	list2 = list(list1)
	list3 = []
	cnt = collections.Counter()
	for i in range(len(list1)):
		cnt[list1[i]] += 1
	tep = max(list1)
	if cnt[tep] != 1:
		if cnt[tep] <= 5:
			for i in range(5):
				if tep in list2:
					list3.append(list2.index(tep))
					list2[list2.index(tep)] = -1
				else:
					break
		else:
			for i in range(4):
				if tep in list2:
					list3.append(list2.index(tep))
					list2[list2.index(tep)] = -1
				else:
					break
	else:
		list3.append(list1.index(tep))
		list2.remove(tep)
		list3.append(list1.index(max(list2)))
	return list3
n = int(input())
intgrade = list(map(int, input().split()))
bitlists = []
if len(set(intgrade)) == 1:
	print(intgrade[0])
	print(0)
else:
	while len(set(intgrade)) != 1:
		listA = temp(intgrade)
		bitlist = ''
		for i in range(len(listA)):
			if intgrade[listA[i]] > 0:
				intgrade[listA[i]] -= 1
		for i in range(n):
			if i in listA:
				bitlist += '1'
			else:
				bitlist += '0'
		bitlists.append(bitlist)
	print(intgrade[0])
	print(len(bitlists))
	for i in range(len(bitlists)):
		print(bitlists[i])


n = int(input())
L = list(map(int, input().split()))
ans = 0
M = []
while max(L) != min(L):
	ans += 1
	k = max(L)
	if L.count(k) == 3:
		s = ''
		for i in range(len(L)):
			if L[i] == k:
				s += '1'
				L[i] -= 1
			else:
				s += '0'
		M.append(s)
	else:
		max_1 = 0
		max_2 = 1
		if L[max_1] < L[max_2]:
			(max_1, max_2) = (max_2, max_1)
		for i in range(2, n):
			if L[i] > L[max_1]:
				(max_2, max_1) = (max_1, i)
			elif L[i] > L[max_2]:
				max_2 = i
		s = ''
		for i in range(n):
			if i == max_1 or i == max_2:
				s += '1'
			else:
				s += '0'
		M.append(s)
		L[max_1] -= 1
		if L[max_1] < 0:
			L[max_1] = 0
		L[max_2] -= 1
		if L[max_2] < 0:
			L[max_2] = 0
print(max(L))
print(ans)
for i in M:
	print(i)


n = int(input())
d = list(map(int, input().split()))
answer = []
while not all((i == d[0] for i in d)):
	i = max(range(n), key=lambda x: d[x])
	max1 = d[i]
	d[i] = -1
	j = max(range(n), key=lambda x: d[x])
	max2 = d[j]
	d[j] = -1
	z = max(range(n), key=lambda x: d[x])
	if max1 == max2 and max1 == d[z]:
		for t in range(n):
			if t != i and t != j and (t != z):
				break
		if all((d[v] == d[t] for v in range(n) if v != i and v != j and (v != z))) and d[t] < max1:
			d[i] = max1 - 1
			d[j] = max2 - 1
			d[z] -= 1
			answer.append(''.join(('1' if k == i or k == j or k == z else '0' for k in range(n))))
			continue
	d[i] = max(max1 - 1, 0)
	d[j] = max(max2 - 1, 0)
	answer.append(''.join(('1' if k == i or k == j else '0' for k in range(n))))
print(d[0])
print(len(answer))
for i in answer:
	print(i)


def sum1(b):
	sum1 = 0
	for i in range(len(b)):
		sum1 += b[i][0]
	return sum1
n = int(input())
a = list(map(int, input().split()))
if n != 2:
	do = True
	b = []
	min2 = min(a)
	for i in range(n):
		a[i] -= min2
		b.append([a[i], i])
	prin = []
	b.sort()
	prinx = -1
	if sum(a) == 1 and min2 != 0:
		min2 -= 1
		for i in range(n):
			b[i][0] += 1
	if sum1(b) % 2:
		if b[-3][0] == 0:
			if min2 == 0:
				do = False
			else:
				min2 -= 1
				for i in range(n):
					b[i][0] += 1
		if do:
			b[-1][0] -= 1
			b[-2][0] -= 1
			b[-3][0] -= 1
			prinx = (b[-1][1], b[-2][1], b[-3][1])
			b.sort()
	while b[-1][0] != 0 and do:
		if b[-2][0] == 0:
			if min2 == 0:
				do = False
			else:
				min2 -= 1
				for i in range(n):
					b[i][0] += 1
				if sum1(b) % 2:
					if prinx == -1:
						b[-1][0] -= 1
						b[-2][0] -= 1
						b[-3][0] -= 1
						prinx = (b[-1][1], b[-2][1], b[-3][1])
						b.sort()
					else:
						prin.append([prinx[0], prinx[1]])
						prin.append([prinx[2], b[-1][1]])
						b[-1][0] -= 1
						prinx = -1
		b[-1][0] -= 1
		b[-2][0] -= 1
		prin.append([b[-1][1], b[-2][1]])
		b.sort()
	if not do:
		while b[-1][0] > 0:
			b[-1][0] -= 1
			prin.append([b[-1][1], b[-2][1]])
	x = [0 for i in range(n)]
	print(min2)
	if prinx != -1:
		print(len(prin) + 1)
		x[prinx[0]] = 1
		x[prinx[1]] = 1
		x[prinx[2]] = 1
		print(*x, sep='')
		x[prinx[0]] = 0
		x[prinx[1]] = 0
		x[prinx[2]] = 0
	else:
		print(len(prin))
	for i in prin:
		x[i[0]] = 1
		x[i[1]] = 1
		print(*x, sep='')
		x[i[0]] = 0
		x[i[1]] = 0
elif a[1] == a[0]:
	print(a[0])
	print(0)
else:
	print(0)
	print(max(a))
	for i in range(max(a)):
		print('11')