Submission #1331923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1331923		lucas_bussinger	Cutting a rectangle (LMIO18_staciakampis)	Pypy 3	0 / 100	148 ms	48784 KiB

staciakampis

import sys


data = sys.stdin.read().split()

K = int(data[0])
rects = []
area_total = 0

for i in range(K):
    a = int(data[1 + 2*i])
    b = int(data[2 + 2*i])
    rects.append((a, b))
    area_total += a * b
    
a_k, b_k = rects[-1]

candidatos = []
if area_total % a_k == 0:
    candidatos.append((a_k, area_total // a_k))
if a_k != b_k and area_total % b_k == 0:
    candidatos.append((b_k, area_total // b_k))
    
def check(H, W, retangulos):
    h, w = H, W
    
    for i in range(len(retangulos) - 1, 0, -1):
        ai, bi = retangulos[i]
        
        if ai == h and bi < w:
            w -= bi
        elif ai == w and bi < h:
            h -= bi
        elif bi == h and ai < w:
            w -= ai
        elif bi == w and ai < h:
            h -= ai
        else:
            return False
    
    af, bf = retangulos[0]
    return (af == h and bf == w) or (af == w and bf == h)

shorter_edges_validas = set()
for h, w in candidatos:
    if check(h, w, rects):

        shorter_edges_validas.add(min(h, w))
        
sorted_results = sorted(list(shorter_edges_validas))
sys.stdout.write(str(len(sorted_results)) + '\n')

for res in sorted_results:
    sys.stdout.write(str(res) + '\n')

Compilation message (stdout)

Compiling 'staciakampis.py'...

=======
  adding: __main__.pyc (deflated 32%)

=======

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 55