Warning

# Example solutions

of selected older exam programming problems

# Gallery Guards

#  ---------------------------------------------------------------------------------------------
#  solution 1
#  ---------------------------------------------------------------------------------------------

import sys

terms = line.strip().split(', ')
G = int(terms[0])
P = int(terms[1])

guards = line.strip().split(', ')
guard_dict = {
guard: [[0] * 600, [0] * 600] for guard in guards
}

terms = line.strip().split(', ')

gallery_dict = {
terms[0]: 0,
terms[1]: 1
}

gallery_time_list = [[0] * 600, [0] * 600]
for _ in range(P):
terms = line.strip().split(', ')

# get guard name
guard = terms[0]

# get start and end times
h, m = terms[1].split(':')
start = int(h) * 60 + int(m) - 8 * 60
start = max(start, 0)

h, m = terms[2].split(':')
end = int(h) * 60 + int(m) - 8 * 60
end = min(end, 599)

if start > end:
continue

# get gallery index
gallery_index = gallery_dict[terms[3]]

for i in range(start, end + 1):
# update free time
gallery_time_list[gallery_index][i] = 1

# update conflict time
guard_dict[guard][gallery_index][i] = 1

# calculate free time
free_time = [0, 0]
for i, gallery_time in enumerate(gallery_time_list):
for j in gallery_time:
if j == 0:
free_time[i] += 1

# calculate conflict time
conflict_dict = {}
for guard in guard_dict:
conflict_time = 0
for i in range(600):
if guard_dict[guard][0][i] == guard_dict[guard][1][i] == 1:
conflict_time += 1

conflict_dict[guard] = conflict_time

conflict_time_list = sorted(conflict_dict.items(), key=lambda kv: (kv[1], kv[0]))

# output free time
sys.stdout.write(f'{free_time[0]//60:0>2}:{free_time[0]%60:0>2}{free_time[1]//60:0>2}:{free_time[1]%60:0>2}')
sys.stdout.write('\n')

# output conflict time
for item in conflict_time_list:
sys.stdout.write(f'{item[1] // 60:0>2}:{item[1] % 60:0>2} ')
sys.stdout.write(item[0] + '\n')

#  ---------------------------------------------------------------------------------------------
#  solution 2
#  ---------------------------------------------------------------------------------------------
def Gallery_Guards():
line1 = input()
list1 = line1.split(', ')
G = int(list1[0])
P = int(list1[1])
line2 = input()
list2 = line2.split(', ')
line3 = input()
list3 = line3.split(', ')
R1 = list3[0]
R2 = list3[1]
libm = {}
for i in list2:
libm[i] = 0
lib1 = {}
lib2 = {}
for i in range(8,18):
for j in range(60):
lib1[60*i+j] = []
lib2[60*i+j] = []
for i in range(P):
line4 = input()
list4 = line4.split(', ')
m = str(list4[0])
R = str(list4[3])
s = (int(list4[1].split(':')[0]))*60+int(list4[1].split(':')[1])
e = (int(list4[2].split(':')[0]))*60+int(list4[2].split(':')[1])
if R == R1:
for j in range(s,e+1):
if m not in lib1[j]:
c = lib1[j]
c.append(m)
lib1[j] = c
if m in lib2[j]:
libm[m] = libm[m] + 1
else:
for j in range(s,e+1):
if m not in lib2[j]:
c = lib2[j]
c.append(m)
lib2[j] = c
if m in lib1[j]:
libm[m] = libm[m] + 1
f1 = 0
f2 = 0
for value in lib1.values():
if value == []:
f1 += 1
for value in lib2.values():
if value == []:
f2 += 1
strlist = str(f'{f1//60:02}')+':'+str(f'{f1%60:02}')+' '+str(f'{f2//60:02}')+':'+str(f'{f2%60:02}')
mlist = []
for key in libm:
mlist.append((key,libm[key]))
def firsort(elem):
return elem[0]
def secsort(elem):
return elem[1]
mlist.sort(key=firsort)
mlist.sort(key=secsort)
for i in mlist:
strlist += '\n'+str(f'{i[1]//60:02}')+':'+str(f'{i[1]%60:02}')+' '+i[0]
return(strlist)
print(Gallery_Guards())

#  ---------------------------------------------------------------------------------------------
#  solution 3
#  ---------------------------------------------------------------------------------------------

ef toHM( n ):
return ("00" +str(n//60))[-2:] + ":" + ("00" +str(n%60))[-2:]

def register( item ):
global gallery1, gallery2, gallery1free, gallery2free
item = item.split(", ")
t1 = toMinutes(item[1])
t2 = toMinutes(item[2])
iperson = personI[item[0]]
if item[3] == gallery1name:
gallery1[iperson][t1: t2+1] = [1] * (t2+1-t1)
gallery1free[t1: t2+1] = [0] * (t2+1-t1)
else:
gallery2[iperson][t1: t2+1] = [1] * (t2+1-t1)
gallery2free[t1: t2+1] = [0] * (t2+1-t1)

def solve():
confltime = []
for person in personI:
conflt = 0
iperson = personI[person]
for i in range(minmin, maxmin+1):
if gallery1[iperson][i] * gallery2[iperson][i] > 0:
conflt += 1
confltime.append( toHM(conflt) +" " + person)
confltime.sort()

print(toHM(sum(gallery1free)), toHM(sum(gallery2free)))
print( "\n". join(confltime) )

#    M A I N

NP, Nit  = map(int, input().split(", "))
names = input().split(", ")

gallery1name, gallery2name = input().split(", ")
gallery1 = [[0]*(maxmin+1) for k in range(NP)]
gallery2 = [[0]*(maxmin+1) for k in range(NP)]
gallery1free = [0] * minmin + ([1]*(maxmin+1-minmin))
gallery2free = [0] * minmin + ([1]*(maxmin+1-minmin))

for i in range(NP):
personI[names[i]] = i
for i in range(Nit):
item = input()
register(item)

#for k in gallery1: print(k)
#for k in gallery2: print(k)

solve ()

# Rectangles area

#  ---------------------------------------------------------------------------------------------
#  solution 1
#  ---------------------------------------------------------------------------------------------
matrix = []
rows = 0
col = 0
num_rect = 0
total_area = 0
upper_left_container = []

def get_inputs():
global matrix
global rows
global col

rows, col = input().split()
rows = int(rows)
col = int(col)

for row in range(rows):
new_row = input().split()
matrix.append(new_row)

return matrix

def start_corner_finder():

for y in range(rows-1):
for x in range(col-1):
if matrix[y][x] == "1":
find_borders(y, x)

def find_borders(y1,x1):

up = 1
bottom = 1
left = 0
right = 1

for y in range(y1, rows):
if matrix[y][x1] == "1":
left += 1
else:
break

for x in range(x1+1, col):
if matrix[y1][x] == "1":
up += 1
else:
break

if up > 2 and left > 2:
for y in range(y1+1, rows):
if matrix[y][x1+up-1] == "1":
right += 1
else:
break
for x in range(x1+1, col):
if matrix[y1+left-1][x] == "1":
bottom += 1
else:
break

get_parameters(up,bottom,left, right)

def get_parameters(up, bottom, left, right):
global num_rect
global total_area

if up > 2 and left > 2:
if up == bottom and left == right:
num_rect += 1
area = (up-2)*(left-2)
total_area += area

get_inputs()
start_corner_finder()
print(num_rect, total_area)

#  ---------------------------------------------------------------------------------------------
#  solution 2
#  ---------------------------------------------------------------------------------------------

import sys

try:
basic = []
while True:
if m == '':
break
m = list(m.split())
basic.append(m)
#print(basic)
except:
pass

#basic = [['17', '4'], ['1', '1', '1', '1'], ['1', '0', '0', '1'], ['1', '1', '1', '1'], ['0', '0', '0', '0'], ['1', '1', '1', '1'], ['1', '0', '0', '1'], ['1', '1', '1', '1'], ['0', '0', '0', '0'], ['1', '1', '1', '1'], ['0', '0', '0', '0'], ['1', '1', '1', '1'], ['1', '0', '0', '1'], ['1', '1', '1', '1'], ['0', '0', '0', '0'], ['1', '1', '1', '0'], ['0', '0', '0', '0'], ['1', '1', '1', '1']]

for i in range(len(basic)):
basic[i] = [int(num) for num in basic[i]]

R = basic[0][0]
C = basic[0][1]
basic.pop(0)

def find_sq(y, x):
w = 0
h = 0
t = 0
for a in range(x, C):
if basic[y][a] == 1:
w += 1
else: break
for b in range(y, R):
if basic[b][x] == 1:
h += 1
else: break
for c in range(w):
if basic[y+h-1][x+c] != 1:
t += 1
break
for d in range(h):
if basic[y+d][x+w-1] == 0:
t += 1
break
if t == 0:
return w, h
else: return 0, 0

num = 0
area = 0
for i in range(R-1):
for j in range(C-1):
wid = 0
height = 0
if basic[i][j] == 1:
wid, height = find_sq(i, j)
if wid >= 3 and height >= 3:
num += 1
area += (wid-2)*(height-2)
else:
basic[i][j] = 0

print(num, area)

#  ---------------------------------------------------------------------------------------------
#  solution 3
#  ---------------------------------------------------------------------------------------------
def get_rect(board, ci, ri, board_c, board_r):
width, height = 1, 1
for mc in range(ci + 1, board_c):
if board[ri][mc] == "1":
width += 1
else:
break

if width < 2:
return None

for mr in range(ri + 1, board_r):
if board[mr][ci] == "1":
height += 1
else:
break

if height < 2:
return None

# check bottom row
for mc in range(ci + 1, ci+width):
if board[ri+height-1][mc] != "1":
return None

# check right column
for mr in range(ri + 1, ri+height):
if board[mr][ci+width-1] != "1":
return None

return {
"wh": (width, height),
"cr": (ci, ri)
}

def sum_area(rect_list):
sa = 0
for rect in rect_list:
w, h = rect["wh"]
sa += (w-2) * (h-2)
return sa

def solve(board):
rect_list = []

board_r = len(board)
board_c = len(board[0])

for ri in range(board_r):
for ci in range(board_c):
if board[ri][ci] == "1":
rect = get_rect(board, ci, ri, board_c, board_r)
if rect:
rect_list.append(rect)

areas = sum_area(rect_list)
return len(rect_list), areas

rc = input()
r, c = rc.split()
r, c = int(r), int(c)

board = []
for ri in range(r):
line = input()
row = line.split()
board.append(row[:c])

return board

def main():
rect_num, rect_areas = solve(board)
print(rect_num, rect_areas)

if __name__ == '__main__':
main()
#  ---------------------------------------------------------------------------------------------
#  solution 4
#  ---------------------------------------------------------------------------------------------
import time
arr = []
M, N = list(map(int, input().split()))
t1 = time.time()
for i in range(M):
line = list(map(int, input().split()))
arr.append(line)
t2 = time.time()
range_rows = []
for n, lst in enumerate(arr):
start = 0
end = 0
for i in range(N):
if lst[i] == 1 and end == 0:
start = i
end = i+1
elif lst[i] == 1 and end != 0 and i == N-1:
range_rows.append((n, start, end))
elif lst[i] == 1 and end!= 0:
end += 1
elif lst[i] == 0 and end == 0:
end = 0
start = 0
elif lst[i] == 0 and end != 0:
end -= 1
range_rows.append((n, start, end))
end = 0
start = 0
range_rows = sorted(range_rows, key = lambda element: (element[1], element[2]))
poss_rect = []
for i in range(len(range_rows)- 1):
if range_rows[i][1] == range_rows[i+1][1] and range_rows[i][2] == range_rows[i+1][2] and (range_rows[i][2]- range_rows[i][1]) > 1:
poss_rect.append((range_rows[i], range_rows[i+1]))
else:
continue
rect = []
for points in poss_rect:
first, second = points
for i in range(first[0], second[0]):
if arr[i][first[1]] != arr[i][second[1]] or  arr[i][first[2]] != arr[i][second[2]]:
break
elif arr[i][first[1]] == arr[i][second[1]] == 0 or arr[i][first[2]] == arr[i][second[2]]== 0:
break
else:
rect.append(points)
area = 0
for values in rect:
top, bottom = values
area += (bottom[0]-top[0]-1)*(top[2]-top[1]-1)
t3 = time.time()
print(len(rect), area)
#print(t2-t1)
#print(t3-t2)

# Cooperating Robot Pairs

#  ---------------------------------------------------------------------------------------------
#  solution 1
#  ---------------------------------------------------------------------------------------------
M, N = input().split()
M, N = [int(M), int(N)]
matrix = []
for row in range(M):
matrix.append(list(map(int, input().split())))
degree_dict = {2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0}
checked = []

def isNeighbour(cell, matrix, M, N):
count = 0
neighbours = []
for i in range(cell[1]+1, N): #right
if matrix[cell[0]][i] == 2: break
if matrix[cell[0]][i] == 1:
neighbours.append((cell[0], i))
count+=1
break
for i in range(cell[1]-1, -1, -1): #left
if matrix[cell[0]][i] == 2: break
if matrix[cell[0]][i] == 1:
neighbours.append((cell[0], i))
count+=1
break
for i in range(cell[0] - 1, -1, -1): #up
if matrix[i][cell[1]] == 2: break
if matrix[i][cell[1]] == 1:
neighbours.append((i, cell[1]))
count+=1
break
for i in range(cell[0] + 1, M): #down
if matrix[i][cell[1]] == 2: break
if matrix[i][cell[1]] == 1:
neighbours.append((i, cell[1]))
count+=1
break
listed= []
listed.append(count)
listed.append(neighbours)
# print(listed)
return listed

for row in range(M):
for col in range(N):
if matrix[row][col] == 1:
data = isNeighbour([row, col], matrix, M, N)
if data[0] == 0 : continue
sumX = data[0] #first robot
for cell in data[1]: #paired robots
if((row, col), cell) in checked or (cell, (row, col)) in checked: continue
checked.append(((row, col), cell))
sumY = isNeighbour(cell, matrix, M, N)[0]
degree_dict[sumX + sumY] += 1

for i in degree_dict:
print(i, degree_dict[i])

#  ---------------------------------------------------------------------------------------------
#  solution 2
#  ---------------------------------------------------------------------------------------------
def check_pair_right(m: int, n: int):
while True:
if n + 1 <= N - 1:
if p[m][n + 1] == 2:
return (0, 0)
elif p[m][n + 1] == 0:
n += 1
continue
elif p[m][n + 1] == 1:
return (m, n + 1)
else:
return (0, 0)

def check_pair_down(m: int, n: int):
while True:
if m + 1 <= M - 1:
if p[m + 1][n] == 2:
return (0, 0)
elif p[m + 1][n] == 0:
m += 1
continue
elif p[m + 1][n] == 1:
return (m + 1, n)
else:
return (0, 0)

p = []
res = {i: 0 for i in range(2, 9)}
pairs = []

M, N = [int(i) for i in input().split()]
for m in range(M):
p.append(list(int(i) for i in input().split()))

# Формируем список пар роботов
for m in range(M):
for n in range(N):
if p[m][n] == 1:
r = check_pair_right(m, n)
if r != (0, 0):
pairs.append(((m, n), r))
d = check_pair_down(m, n)
if d != (0, 0):
pairs.append(((m, n), d))

for pair in pairs:
counter = 0
for c in pairs:
if pair[0] in c:
counter += 1
if pair[1] in c:
counter += 1
res[counter] += 1

for val in res:
print(val, res[val])

#  ---------------------------------------------------------------------------------------------
#  solution 3
#  ---------------------------------------------------------------------------------------------
import time
import sys
import numpy as np
from io import StringIO

start = time.time()
def main():
# input = open("/Users/prasoondwivedi/PycharmProjects/ProgrammingForEngineers/Homeworks/5CoopPairs/datapub/pub10.in", "r")
input = sys.stdin

c = StringIO(input)  # make matrix from text input without first line
rows, cols = fieldMatrix.shape[0], fieldMatrix.shape[1]

coopPairs = []
for x in range(0, rows):
for y in range(0, cols):
if fieldMatrix[x][y] == 1:      # detect robot

for vpair in range(x + 1, rows):    # vertical searching
if fieldMatrix[vpair][y] == 2: break    # break if obstacle in same column
else:
if fieldMatrix[vpair][y] == 1:      # find cooperation pair
coopPairs.append([x, y])
coopPairs.append( [vpair, y])
break

for hpair in range(y + 1, cols):    # horizontal searching
if fieldMatrix[x][hpair] == 2: break    # break if obstacle in same row
else:
if fieldMatrix[x][hpair] == 1:      # find cooperation pair
coopPairs.append([x, y])
coopPairs.append([x, hpair])
break
coopPairs1 = []

# print(coopPairs)
for i in range(0, len(coopPairs), 2):
coopPairs1.append(coopPairs.count(coopPairs[i]) + coopPairs.count(coopPairs[i + 1]))

for i in range(2, 8 + 1):
print(str(i), str(coopPairs1.count(i)))
main()

# end = time.time()
# print("time:", end - start, "s ")

#  ---------------------------------------------------------------------------------------------
#  solution 4
#  ---------------------------------------------------------------------------------------------
import time

a  = []

t1 = time.time()
M, N = map(int, input().split())
for i in range(M):
row = list( map( int, input().split() ) )
a.append(row)

e = [[] for _ in range(M*N)]

# hor edges
for i in range(M):
inEdge = False
lastj = -1
for j in range(N):
if a[i][j] == 2:
inEdge = False; continue
if a[i][j] == 1:
if inEdge: # edge found
e[i*N+lastj].append(i*N+j)
e[i*N+j].append(i*N+lastj)
else:
inEdge = True
lastj = j
# ver edges
for j in range(N):
inEdge = False
lasti = -1
for i in range(M):
if a[i][j] == 2:
inEdge = False; continue
if a[i][j] == 1:
if inEdge: # edge found
e[lasti*N+j].append(i*N+j)
e[i*N+j].append(lasti*N+j)
else:
inEdge = True
lasti = i

# compute edge statistics:
hist = [0]*9
for i in range(M*N-1):
for neigh in e[i]:
if neigh > i:
hist[len(e[i])+len(e[neigh])] += 1

for k in range(2,9):
print( k, hist[k])

# Secure Matrix Areas

#  ---------------------------------------------------------------------------------------------
#  solution 1
#  ---------------------------------------------------------------------------------------------
# gets input
firstline = input().split()
M = int(firstline[0])
N = int(firstline[1])
#creates matrix
matrix = []
size = {}
upper_left = []
for i in range(M):
row = input().split()
matrix.append(row)

#search for secure area
def secure_area(start):
val = []
y, x = start[0], start[1]
loop = min(M-y, N-x)
cells = 1
for k in range(1, loop):
if cells > 3: break

for g in range(0, k):
if cells > 3: break
if matrix[y+g][x+k] == '1':
cells += 1
if matrix[y+k][x+g] == '1':
cells += 1
if matrix[y+k][x+k] == '1':
cells += 1

if cells == 3:
val.append(k+1)
return val

for y in range(M-1):
for x in range(N-1):
if matrix[y][x] == '1':
area = secure_area([y, x])
# print(area)
upper_left.append(area)
for h in area:
if h in size:
cs = size[h]
size[h] = cs + 1
else:
size[h] = 1

key = list(size.keys())
# print(size)
if None in key:
key.remove(None)
keys = sorted(key) #ascending order
for s in keys:
if s > 1:
print(s, size[s])

#  ---------------------------------------------------------------------------------------------
#  solution 2
#  ---------------------------------------------------------------------------------------------
import time

mx = []
M, N = 0, 0
hist = []

def checkL( ii, jj, len):

global mx
count = 0
for j in range(jj, jj+len):
if mx[ii][j] == 1:
count += 1
rightJ = jj+len-1

for i in range(ii-len+1, ii):
if mx[i][rightJ] == 1:
count += 1
return count

def checkArea( i1, j1 ):
global N, hist
size = 1
count = 1
while True:
size += 1
ii = i1+size-1
# check boundaries
if ii >= M: return
if j1+size-1 >= N: return
count += checkL( ii, j1, size )
if count < 3: continue
if count == 3:
hist[size] += 1
#print("found at", i1, j1, size)
else: return

def histo():
global mx, M, N, hist
for i in range(M):
for j in range(N):
if mx[i][j] == 1:
checkArea(i, j)
return hist

t1 = time.time()
M, N = map(int, input().split())
for i in range(M):
row =  list( map( int, input().split() ) )
mx.append(row)

hist = [0] *( max(M,N)+1 )
histo()

for i in range( len(hist)):
if hist[i] > 0:
print(i, hist[i])

#  ---------------------------------------------------------------------------------------------
#  solution 3
#  ---------------------------------------------------------------------------------------------
M, N = input().split(" ")
M, N = [int(M), int(N)]
matrix = []
for row in range(M):
matrix.append(list(map(int, input().split())))
secure_dict = {}
for i in range(max(M, N)):
secure_dict[i] = 0
checked = []

def checkForSecureCells(cell, matrix, M, N, secure_dict):
cell_x = cell[0]
cell_y = cell[1]
secureCells = 1
while True:
# placing new reference point
if cell[0] + 1 < M and cell[1] + 1 < N:
cell[0] += 1
cell[1] += 1
else:
return
# checking diag.
if matrix[cell[0]][cell[1]] == 1:
secureCells += 1
# checking upwards
for i in range(cell[0] - 1, cell_x - 1, -1):
if matrix[i][cell[1]] == 1:
secureCells += 1
# checking leftwards
for i in range(cell[1] - 1, cell_y - 1, -1):
if matrix[cell[0]][i] == 1:
secureCells += 1
if secureCells > 3:
return
if secureCells == 3:
s = (cell[0] - cell_x) + 1
secure_dict[s] += 1
def solve():
for row in range(M):
for col in range(N):
if matrix[row][col] == 1:
checkForSecureCells([row, col], matrix, M, N, secure_dict)
for i in secure_dict:
if secure_dict[i] != 0 and i != 0:
print(i, secure_dict[i])
solve()

#  ---------------------------------------------------------------------------------------------
#  solution 4
#  ---------------------------------------------------------------------------------------------
def check_for_secure(y, x, M, N, matrix):
r = []
c = 1  # cells with x
n = min(M - y, N - x)
for k in range(1, n):

if matrix[y+k][x+k] == '1':
c += 1

for g in range(0, k):
if matrix[y+g][x+k] == '1':
c += 1
if matrix[y+k][x+g] == '1':
c += 1

if c > 3: break
if c > 3: break
if c == 3:
r.append(k+1)
return r

def main():
finput = input().split()
M, N = int(finput[0]), int(finput[1])

matrix, dictf = [], {}
for i in range(M):
row = input().split()
matrix.append(row)

for y in range(M-1):
for x in range(N-1):
if matrix[y][x] == '1':
area = check_for_secure(y, x, M, N, matrix)
if None in area: area.remove(None)
for h in area:
if h not in dictf: dictf[h] = 1
else:
cs = dictf[h]
dictf[h] = cs + 1
d = list(dictf.keys())
# if None in d: d.remove(None)
dd = sorted(d)
for s in dd:
if s > 1:
print(s, dictf[s])

main()