Codeforces Beta Round #50 B. Cutting Jigsaw Puzzle

Cutting Jigsaw Puzzle

約数の個数はそんなに多くないので全通り試しても間に合う。

def rotate(p):
    w,h = len(p[0]),len(p)
    r = []
    for y in range(w):
        r += [[]]
        for x in range(h):
            r[-1] += [p[x][w-y-1]]
    return r

A,B = map(int,raw_input().split())
P = []
for i in range(A):
    P += [list(raw_input())]

def check(X,Y):
    if A%X>0 or B%Y>0:
        return False
    Q = []
    for x in range(0,A,X):
     for y in range(0,B,Y):
        p = [[P[x+i][y+j] for j in range(Y)] for i in range(X)]
        for d in range(4):
            if p in Q:
                return False
            p = rotate(p)
        Q += [p]
    return True

c,aX,aY = 0,A,B

for X in range(1,A+1):
 for Y in range(1,B+1):
    if check(X,Y):
        c += 1
        if X*Y<aX*aY or X*Y==aX*aY and X<aX:
            aX,aY = X,Y

print c
print aX,aY