Problem:


Score : 500 points

Problem Statement

Snuke has two boards, each divided into a grid with N rows and N columns.
For both of these boards, the square at the i-th row from the top and the j-th column from the left is called Square (i,j).

There is a lowercase English letter written in each square on the first board. The letter written in Square (i,j) is S_{i,j}. On the second board, nothing is written yet.

Snuke will write letters on the second board, as follows:

First, choose two integers A and B ( 0 \leq A, B < N ).

Write one letter in each square on the second board.
Specifically, write the letter written in Square ( i+A, j+B ) on the first board into Square (i,j) on the second board.
Here, the k-th row is also represented as the (N+k)-th row, and the k-th column is also represented as the (N+k)-th column.

After this operation, the second board is called a good board when, for every i and j ( 1 \leq i, j \leq N ), the letter in Square (i,j) and the letter in Square (j,i) are equal.

Find the number of the ways to choose integers A and B ( 0 \leq A, B < N ) such that the second board is a good board.

Constraints

1 \leq N \leq 300

S_{i,j} ( 1 \leq i, j \leq N ) is a lowercase English letter.

Input

Input is given from Standard Input in the following format:

N
S_{1,1}S_{1,2}..S_{1,N}
S_{2,1}S_{2,2}..S_{2,N}
:
S_{N,1}S_{N,2}..S_{N,N}

Output

Print the number of the ways to choose integers A and B ( 0 \leq A, B < N ) such that the second board is a good board.

Sample Input 1

2
ab
ca

Sample Output 1

2

For each pair of A and B, the second board will look as shown below:

The second board is a good board when (A,B) = (0,1) or (A,B) = (1,0), thus the answer is 2.

Sample Input 2

4
aaaa
aaaa
aaaa
aaaa

Sample Output 2

16

Every possible choice of A and B makes the second board good.

Sample Input 3

5
abcde
fghij
klmno
pqrst
uvwxy

Sample Output 3

0

No possible choice of A and B makes the second board good.



Sample input:
2
ab
ca


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
def is_sym(n, ss, tt, a, b):
    for i in range(n):
        s_row = ss[(i + a) % n]
        t_row = tt[(i + b) % n]
        for j in range(n):
            if s_row[(j + b) % n] != t_row[(j + a) % n]:
                return False
    return True


def t(n, ss):
    ret = []
    for i in range(n):
        row = tuple(ss[j][i] for j in range(n))
        ret.append(row)
    return ret


def it_a(n, ss):
    d = {}
    for i in range(n):
        a = tuple(ss[i:] + ss[:i])
        if a in d:
            d[a][1] += 1
        else:
            d[a] = [i, 1]
    return list(d.values())


def main():
    n = int(input())
    ss = []
    for _ in range(n):
        row = []
        for c in input().strip():
            row.append(ord(c) - 97)
        ss.append(tuple(row))
    tt = t(n, ss)
    ans = 0
    aa = it_a(n, ss)
    bb = it_a(n, tt)
    for a, ac in aa:
        for b, bc in bb:
            if is_sym(n, ss, tt, a, b):
                ans += ac * bc
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

s = [input() for i in range(n)]

# print(s)
    
s1 = [[None for i in range(n)] for j in range(n)]

# print(s1)

for i in range(n):
    for j in range(n):
        s1[i][j] = s[i][j]
# print(s1)

a = 0
b = 1

cnt = 0
for a in range(n):
    for b in range(n):
        flag = True
        s2 = [[None for i in range(n)] for j in range(n)]

        for i in range(n):
            for j in range(n):
                oi = (i + a) % n
                oj = (j + b) % n
                # print(oi, oj, s1[oi][oj])
                
                s2[i][j] = s1[oi][oj]

        # print(s2)

        for i in range(n):
            for j in range(n):
                if s2[i][j] != s2[j][i]:
                    flag = False
                    break
        if flag:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def cnv(mtx, n):
    result = []
    for x in mtx:
        result.append(x[n:] + x[:n])
    return result


def cnv2(mtx, n):
    return mtx[n:] + mtx[:n]


def debugprint(mtxs):
    for x in mtxs:
        for y in x:
            print(y)
        print()


def check(mtx, N):
    for i in range(N):
        for j in range(N // 2 + 1):
            if mtx[i][j] != mtx[j][i]:
                return False
    return True


def main():
    N = int(stdin.readline().rstrip())
    mtx = [list(stdin.readline().rstrip()) for _ in range(N)]
    mtxs = []
    for i in range(N):
        temp = cnv(mtx, i)
        for j in range(N):
            mtxs.append(cnv2(temp, j))
    print(len([x for x in mtxs if check(x, N)]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
board = []
for i in range(n):
  s = input()
  board += [[]]
  for j in range(n):
    board[i] += [s[j]]

ex_board = []
for i in range(2 * n):
  ex_board += [[]]
  for j in range(2 * n):
    ex_board[i] += [board[i % n][j % n]]

count = 0

for i in range(n):
  for j in range(n):
    flag = True
    for k in range(n):
      for l in range(n - k):
        if ex_board[i + k][j + l] != ex_board[i + l][j + k]:
          flag = False
          break
      if flag == False:
        break
    
    if flag == True:
      count += 1
      
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s1 = [[i for i in input()] for j in range(n)]
count = int(0)
for a in range(n):
  flag = 0
  for i in range(n):
    for j in range(n):
      if s1[i][(j+a)%n] != s1[j][(i+a)%n]:
        flag += 1
        break
    if flag == 1:
      break
  if flag == 0:
    count += 1
print(count* n)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
S = []
for _ in range(N):
    S.append(list(input()))
def taikaku(A):
    n = len(A)
    A2 = []
    for i in range(n):
        p = []
        for j in range(n):
            p.append(A[j][i])
        A2.append(p)
    return(A == A2)
ans = 0
for i in range(N):
    if taikaku(S[i:]+S[:i]):
        ans += N
print(ans)

Submission status: Time Limit Exceeded

Solution code:
exec("def nWord(): nWord.cache = raw_input() if not hasattr(nWord, 'cache') or nWord.cache=='' else nWord.cache ; pos = nWord.cache.find(nWord.sep) ; ret, nWord.cache = (nWord.cache, '') if pos==-1 else (nWord.cache[:pos], nWord.cache[pos+1:].lstrip(nWord.sep)) ; return ret") ; exec("nWord.sep = ' '") ; exec("def ___nLine2(): ret, nWord.cache = (raw_input(), nWord.cache if hasattr(nWord, 'cache') else '') if not hasattr(nWord, 'cache') or nWord.cache=='' else (nWord.cache, '') ; return ret") ; exec('def nInt(): return int(nWord())') ; exec('def nFloat(): return float(nWord())') ; exec("def ___nAuto2():\n ret = nWord()\n try: return int(ret)\n except: pass\n try: return float(ret)\n except: return ret") ; exec("def nAuto(n=None): return ___nAuto2() if n is None else [___nAuto2() for i in range(n)]") ; exec("def nLine(n=None): return ___nLine2() if n is None else [___nLine2() for i in range(n)]")
 
N = nAuto()
S = nAuto(N)

def check(A):
    for i in range(N):
        for j in range(N):
            if S[(A+i) % N][j]!=S[(A+j) % N][i]:
                return 0
    return N
 
count = 0
for A in range(N):
    count += check(A)
print count

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
s=[chr(i) for i in range(97, 97+26)]

a=[]    
for i in range(n):
  a0=list(input())
  an=[s.index(i)+1  for i in a0]
  a.append(an)

aa=np.array(a)
z=np.zeros((n,n))
ans=0
for i in range(n):
  for j in range(n):
    ci=[_ % n for _ in range(i,i+n)]
    cj=[_ % n for _ in range(j,j+n)]
    aa_ci=aa[ci,:]
    aa_cij=aa_ci[:,cj]
    at=aa_cij-aa_cij.T
    #print(ci)
    #print(cj)
    #print(aa_cij)
    #print(aa_cij.T)
    #print(np.diag(np.diag(at)))
    #print(at-np.diag(np.diag(at)))
    if np.allclose(at-np.diag(np.diag(at)),z):
      ans+=1 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
import random
import numpy as np
import time

alph="abcdefghijklmnopqrstuvwxyz"

n=int(input())
S=[list(input())for _ in range(n)]
"""
S=[]
for i in range(n):
    s=[]
    for _ in range(n):
        s.append(alph[random.randint(0,25)])
    S.append(s)
"""
#for i in S:print(i)

count=0

for A in range(n):
    for B in range(n):
        flag=0
        for i in range(n):
            for j in range(i+1,n):
                c1=S[(i+A)%n][(j+B)%n]
                c2=S[(j+A)%n][(i+B)%n]
                if(c1!=c2):
                    flag=1
                    break
            if(flag==1):break
        else:count+=1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    global S, N
    N = int(input())

    S = []
    for n in range(N):
        S.append(list(input()))


    res = 0
    for n in range(N):
        if check(n):
            res += N

    print(res)

def check(move):
    for i in range(N):
        for j in range(i+1, N):
            if S[(i-move)%N][j] != S[(j-move)%N][i]:
                return False
    return True


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
exec("def nWord(): nWord.cache = raw_input() if not hasattr(nWord, 'cache') or nWord.cache=='' else nWord.cache ; pos = nWord.cache.find(nWord.sep) ; ret, nWord.cache = (nWord.cache, '') if pos==-1 else (nWord.cache[:pos], nWord.cache[pos+1:].lstrip(nWord.sep)) ; return ret") ; exec("nWord.sep = ' '") ; exec("def ___nLine2(): ret, nWord.cache = (raw_input(), nWord.cache if hasattr(nWord, 'cache') else '') if not hasattr(nWord, 'cache') or nWord.cache=='' else (nWord.cache, '') ; return ret") ; exec('def nInt(): return int(nWord())') ; exec('def nFloat(): return float(nWord())') ; exec("def ___nAuto2():\n ret = nWord()\n try: return int(ret)\n except: pass\n try: return float(ret)\n except: return ret") ; exec("def nAuto(n=None): return ___nAuto2() if n is None else [___nAuto2() for i in range(n)]") ; exec("def nLine(n=None): return ___nLine2() if n is None else [___nLine2() for i in range(n)]")

N = nAuto()
S = nAuto(N)

H = N
W = N

def fH(p, H2):
    for k in range(1, p):
        for i in range(H2):
            for j in range(W):
                if S[i][j]!=S[i+k*H2][j]:
                    return False
    return True

def fW(p, W2):
    for k in range(1, p):
        for i in range(H):
            for j in range(W2):
                if S[i][j]!=S[i][j+k*W2]:
                    return False
    return True

rate = 1
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 39, 41, 43, 47]:
    while H % p == 0:
        H2 = H / p
        if fH(p, H2):
            H = H2
            rate *= p
        else:
            break
    while W % p == 0:
        W2 = W / p
        if fW(p, W2):
            W = W2
            rate *= p
        else:
            break

D = {}
for  i in range(H):
    for j in range(W):
        c = S[i][j]
        if c in D:
            D[c] += 1
        else:
            D[c] = 1

max_c = 'a'
max_count = 0
for c in D:
    if max_count < D[c]:
        max_count = D[c]
        max_c = c

L = []
for  i in range(H):
    for j in range(W):
        c = S[i][j]
        if c!=max_c:
            L.append((i, j, c))

def check(A, B):
    for i2, j2, c in L:
        i = (i2-A+N) % N
        j = (j2-B+N) % N
        if c!=S[(A+j) % N][(B+i) % N]:
            return False
    return True

ng = 0
count = 0
for A in range(H):
    if check(A, 0):
        count += W
    else:
        ng += W
print count * rate

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

IN = 'sample-1.in'  # sample case for local test
def local_test():
    try:
        from pcm.utils import set_stdin
        import sys
        import os
        if len(sys.argv) == 1:
            set_stdin(os.path.dirname(__file__) + '/test/' + IN)
    except:
        pass


def preprocess():
    import sys
    import os
    import time
    import re
    from pydoc import help
    import string
    import math
    import numpy as np
    from operator import itemgetter
    from collections import Counter
    from collections import deque
    from collections import defaultdict as dd
    import fractions
    from heapq import heappop, heappush, heapify
    import array
    from bisect import bisect_left, bisect_right, insort_left, insort_right
    from copy import deepcopy as dcopy
    import itertools
    sys.setrecursionlimit(10**7)
    INF = 10**20
    GOSA = 1.0 / 10**10
    MOD = 10**9+7
    def LI(): return [int(x) for x in sys.stdin.readline().split()]
    def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
    def LF(): return [float(x) for x in sys.stdin.readline().split()]
    def LS(): return sys.stdin.readline().split()
    def I(): return int(sys.stdin.readline())
    def F(): return float(sys.stdin.readline())
    def DP(N, M, first): return [[first] * M for n in range(N)]
    def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]


def solve():
    global S, N
    preprocess()
    N = int(input())

    S = []
    for n in range(N):
        S.append(list(input()))

    res = 0
    for n in range(N):
        if check(n):
            res += N

    print(res)

def check(move):
    for i in range(N):
        for j in range(i+1, N):
            if S[(i-move)%N][j] != S[(j-move)%N][i]:
                return False
    return True


if __name__ == "__main__":
    local_test()
    solve()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=[list(input()) for i in range(N)]
count=0
for A in range(N):
    judge=1
    for i in range(N):
        for j in range(i+1,N):
            if S[(i+A)%N][j]!=S[(j+A)%N][i]:
                judge=0
    if judge==1:
        count+=1
print(N*count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def sym(S, a, b, N):
    s = np.array(S)
    if (s[a:a+N, b:b+N] == s[a:a+N, b:b+N].T).all():
        return True
    else:
        return False

def main():
    N = int(input())
    S = []
    for i in range(N):
        S.append(list(input()))
    extended_S = []
    for _ in range(2):
        for i in range(N):
           extended_S.append(S[i] * 2)
    res = 0
    for a in range(N):
        for b in range(N):
            if sym(extended_S, a, b, N):
                res += 1
    print(res)
    
main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [input() for i in range(n)]
if all(s[i][j]==s[0][0] for i in range(n) for j in range(n)): print(n**2)
else:
	for i in range(n): s[i] += s[i]
	s,ans = s+s,0
	for j in range(n):
		for k in range(n):
			flag = True
			for k2 in range(k,n+k):
				for j2 in range(j,n+j):
					if s[k2][j2]!=s[j2-j+k][k2-k+j]:
						flag = False
						break
				if not flag: break
			if flag: ans += 1
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=[list(input()) for i in range(N)]
count=0
for A in range(N):
    judge=1
    for i in range(N):
        for j in range(N):
            if S[(i+A)%N][j]!=S[(j+A)%N][i]:
                judge=0
    if judge==1:
        count+=1
print(N*count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

N = int(input())
#S = [[]]
S = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    chars = input()
    for j in range(N):
        S[i][j] = chars[j]
    #S.append(input().split())

S2 = [[0 for i in range(N)] for j in range(N)]
# for i in range(len(S)):
#     for j in range(len(S[i])):
#         S2[i][j] = S[i][j]

# 対角行列の対象成分だけ見れば良い
ans = 0
for A in range(N):
    for B in range(N):
        okFlg = True
        for i in range(N):
            for j in range(N):
                ii = i + A
                jj = j + B
                if ii >= N:
                    ii -= N
                if jj >= N:
                    jj -= N

                S2[ii][jj] = S[i][j]
            #s_row = S[ii][jj]
            #s_col = S[jj][ii]

        for i in range(N):
            for j in range(N):
                if S2[i][j] != S2[j][i]:
                    okFlg = False
                    break
        if okFlg == True:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [input() for i in range(n)]

cnt = 0
for i in range(n):
    for j in range(n):
        i_ = (n+i)%n
        j_ = (n+j)%n
        for k in range(n):
            for l in range(n):
                if s[(i_+k)%n][(j_+l)%n] != s[(i_+l)%n][(j_+k)%n]:
                    break
            else:
                continue
            break
        else:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
table = [input() for _ in range(N)]

count = 0

for a, b in list(itertools.product(range(N), repeat = 2)):
    symmetric = True
    new_table = []
    for i in range(N):
        string = table[(i+a)%N][b:] + table[(i+a)%N][:b]
        new_table.append(string)
    
    for i in range(N-1):
        string1 = new_table[i][i+1:]
        string2 = ''.join([s[i] for s in new_table[i+1:]])
        if string1 != string2:
            symmetric = False
            break
    
    if symmetric:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
ban = [input() for i in range(n)]

ans = 0
for (a,b) in list(itertools.product(range(n),repeat=2)):
    flag = True
    for (i,j) in list(itertools.product(range(n),repeat=2)):
        if i+a >= n:
            x = i+a-n
        else:
            x = i+a
        if j+b >= n:
            y = j+b-n
        else:
            y = j+b
        if j+a >= n:
            X = j+a-n
        else:
            X = j+a
        if i+b >= n:
            Y = i+b-n
        else:
            Y = i+b
        #print(a,b,x,y,ban[x][y],ban[X][Y])
        if ban[x][y] != ban[X][Y]:
            flag = False
            break
    if flag == True:
        ans += 1
        #print(a,b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
exec("def nWord(): nWord.cache = raw_input() if not hasattr(nWord, 'cache') or nWord.cache=='' else nWord.cache ; pos = nWord.cache.find(nWord.sep) ; ret, nWord.cache = (nWord.cache, '') if pos==-1 else (nWord.cache[:pos], nWord.cache[pos+1:].lstrip(nWord.sep)) ; return ret") ; exec("nWord.sep = ' '") ; exec("def ___nLine2(): ret, nWord.cache = (raw_input(), nWord.cache if hasattr(nWord, 'cache') else '') if not hasattr(nWord, 'cache') or nWord.cache=='' else (nWord.cache, '') ; return ret") ; exec('def nInt(): return int(nWord())') ; exec('def nFloat(): return float(nWord())') ; exec("def ___nAuto2():\n ret = nWord()\n try: return int(ret)\n except: pass\n try: return float(ret)\n except: return ret") ; exec("def nAuto(n=None): return ___nAuto2() if n is None else [___nAuto2() for i in range(n)]") ; exec("def nLine(n=None): return ___nLine2() if n is None else [___nLine2() for i in range(n)]")

N = nAuto()
S = nAuto(N)

H = N
W = N

def fH(p, H2):
    for k in range(1, p):
        for i in range(H2):
            for j in range(W):
                if S[i][j]!=S[i+k*H2][j]:
                    return False
    return True

def fW(p, W2):
    for k in range(1, p):
        for i in range(H):
            for j in range(W2):
                if S[i][j]!=S[i][j+k*W2]:
                    return False
    return True

rate = 1
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 39, 41, 43, 47]:
    while H % p == 0:
        H2 = H / p
        if fH(p, H2):
            H = H2
            rate *= p
        else:
            break
    while W % p == 0:
        W2 = W / p
        if fW(p, W2):
            W = W2
            rate *= p
        else:
            break

D = {}
for  i in range(H):
    for j in range(W):
        c = S[i][j]
        if c in D:
            D[c] += 1
        else:
            D[c] = 1

max_c = 'a'
max_count = 0
for c in D:
    if max_count < D[c]:
        max_count = D[c]
        max_c = c

L = []
for  i in range(H):
    for j in range(W):
        c = S[i][j]
        if c!=max_c:
            L.append((i, j, c))

def check(A, B):
    for i2, j2, c in L:
        i = (i2-A+N) % N
        j = (j2-B+N) % N
        if c!=S[(A+j) % N][(B+i) % N]:
            return False
    return True

ng = 0
count = 0
for A in range(H):
    for B in range(W):
        if check(A, B):
            count += 1
            if 300<=count and ng==0:
                print N*N
                exit()
        else:
            ng += 1
print count * rate

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = []

for i in range(n):
    s.append(list(input()))
s = [l*2 for l in s] * 2

count = 0
for a in range(n):
    for b in range(n):
        t = [l[b:b+n] for l in s[a:a+n]]
        if t == list(map(list, zip(*t))):
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
exec("def nWord(): nWord.cache = raw_input() if not hasattr(nWord, 'cache') or nWord.cache=='' else nWord.cache ; pos = nWord.cache.find(nWord.sep) ; ret, nWord.cache = (nWord.cache, '') if pos==-1 else (nWord.cache[:pos], nWord.cache[pos+1:].lstrip(nWord.sep)) ; return ret") ; exec("nWord.sep = ' '") ; exec("def ___nLine2(): ret, nWord.cache = (raw_input(), nWord.cache if hasattr(nWord, 'cache') else '') if not hasattr(nWord, 'cache') or nWord.cache=='' else (nWord.cache, '') ; return ret") ; exec('def nInt(): return int(nWord())') ; exec('def nFloat(): return float(nWord())') ; exec("def ___nAuto2():\n ret = nWord()\n try: return int(ret)\n except: pass\n try: return float(ret)\n except: return ret") ; exec("def nAuto(n=None): return ___nAuto2() if n is None else [___nAuto2() for i in range(n)]") ; exec("def nLine(n=None): return ___nLine2() if n is None else [___nLine2() for i in range(n)]")

N = nAuto()
S = nAuto(N)

H = N
W = N

def fH(p, H2):
    for k in range(1, p):
        for i in range(H2):
            for j in range(W):
                if S[i][j]!=S[i+k*H2][j]:
                    return False
    return True

def fW(p, W2):
    for k in range(1, p):
        for i in range(H):
            for j in range(W2):
                if S[i][j]!=S[i][j+k*W2]:
                    return False
    return True

for p in [2, 3, 5, 7, 11, 13, 17]:
    while H % p == 0:
        H2 = H / p
        if fH(p, H2):
            H = H2
        else:
            break
    while W % p == 0:
        W2 = W / p
        if fW(p, W2):
            W = W2
        else:
            break

D = {}
for  i in range(H):
    for j in range(W):
        c = S[i][j]
        if c in D:
            D[c] += 1
        else:
            D[c] = 1

max_c = 'a'
max_count = 0
for c in D:
    if max_count < D[c]:
        max_count = D[c]
        max_c = c

L = []
for  i in range(H):
    for j in range(W):
        c = S[i][j]
        if c!=max_c:
            L.append((i, j, c))

def check(A, B):
    for i2, j2, c in L:
        i = (i2-A+N) % N
        j = (j2-B+N) % N
        if c!=S[(A+j) % N][(B+i) % N]:
            return False
    return True

ng = 0
count = 0
for A in range(N):
    for B in range(N):
        if check(A, B):
            count += 1
            if 300<=count and ng==0:
                print N*N
                exit()
        else:
            ng += 1
print count

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations
def inpl(): return map(int, input().split())

N = int(input())
S = [list(input()) for _ in range(N)]
ans = 0

for k in range(N):
    for i, j in combinations(range(N), 2):
        if S[i][(j+k)%N] != S[j][(i+k)%N]:
            break
    else:
        ans += N

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = []
for i in range(N):
    S.append(input())
def check(S, A, B):
    for i in range(N):
        for j in range(N):
            if i + A < N:
                a = i + A
            else:
                a = i + A - N
            if j + B < N:
                b = j + B
            else:
                b = j + B - N
            if j + A < N:
                c = j + A
            else:
                c = j + A - N
            if i + B < N:
                d = i + B
            else:
                d = i + B - N
            if S[a][b] != S[c][d]:
                return False
    return True

cnt = 0
for i in range(N):
    for j in range(N):
        if check(S, i, j):
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy

n = int(input())
s = []

alpha_dict = {}
for i,c in enumerate(range(ord('a'),ord('z')+1)):
    alpha_dict[chr(c)] = i + 1

for i in range(n):
	s.append([alpha_dict[i] for i in list(input())])
count = 0

for a in range(n):
	for b in range(n):
		s2 = s[b:] + s[:b]
		for c in range(n):
			s2[c] = s2[c][a:] + s2[c][:a]
		s2 = numpy.array(s2)

		if numpy.allclose(s2, s2.T):
			count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = []

for i in range(n):
    s.append(list(input()))
s = [l*2 for l in s] * 2

count = 0
for a in range(n):
    for b in range(n):
        t = [l[b:b+n] for l in s[a:a+n]]
        if all([t[i][j] == t[j][i] for i in range(n) for j in range(n)]):
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools


def slv(S):
    count = 0
    N = len(S)
    for a, b in itertools.product(range(len(S)), repeat=2):
        # print(a, b)
        for i, j in itertools.product(range(len(S)), repeat=2):
            if S[(i + a) % N][(j + b) % N] != S[(j + a) % N][(i + b) % N]:
                break

        else:
            count += 1
    # print(S)
    return count


def main():
    N = int(input())
    S = [input() for _ in range(N)]

    # print(len(A))
    print(slv(S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ss = list()
for _ in range(n):
    ss.append(input())
ans = 0
for a in range(n):
    for b in range(n):
        flag = True
        for i in range(n):
            for j in range(i + 1, n):
                x1, y1 = (i - a) % n, (j -  b) % n
                x2, y2 = (j - a) % n, (i -  b) % n
                if ss[x1][y1] != ss[x2][y2]:
                    flag = False
                    break
            if not flag:
                break
        if flag:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = []
for i in range(n):
    s_ = input() * 2
    s__ = []
    for j in range(n):
        s__.append(s_[j])
    s__ = s__ * 2
    s.append(s__) 

count = 0
for i in range(n):
    flag = True
    for j in range(n - 1):
        for k in range(j + 1, n):
            if s[j][k + i] != s[k][j + i]:
                flag = False
                break
        if flag == False:
            break
    if flag == True:
        count = count + 1
count = count * n
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [input() for i in range(n)]
if all(s[i][j]==s[0][0] for i in range(n) for j in range(n)): print(n**2)
else:
	for i in range(n): s[i] += s[i]
	ans = 0
	for i in range(n):
		s2 = []
		for j in s: s2.append(j[i:i+n])
		s2 += s2
		for k in range(n):
			flag = True
			for k2 in range(k,n+k):
				for k3 in range(n):
					if s2[k2][k3]!=s2[k3+k][k2-k]:
						flag = False
						break
				if not flag: break
			if flag: ans += 1
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy
N = int(input())
a = []
for i in range(N):
    a.append(list(input()))
nda = numpy.array(a)
count = 0
for i in range(N):
    for j in range(N):
        rolled = numpy.roll(numpy.roll(nda, i, axis=0), j, axis=1)
        transed = rolled.T
        if numpy.all(rolled == transed):
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def can_be_pair(row, col, A, B):
    for k in range(N):
        s1 = s[row][(k-B)%N]
        s2 = s[(k-A)%N][col]
        if s1 != s2:
            return False
    return True

N = int(input())
s = []
for i in range(N):
    s.append(input())

ret = 0
A = 0
for B in range(N):
    valid = True
    for row in range(N):
        col = (row + A - B)%N
        if not(can_be_pair(row, col, A, B)):
            valid = False
            break
    if valid:
        ret += N
print(ret)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
S = [str(input()) for _ in range(N)]


def isGoodTable(table, A, B):
    for i in range(N):
        for j in range(i, N):
            if table[i][j] != table[j][i]:
                return False
    return True


def shiftTable(table, A, B):
    shifted = [[i for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            shifted[i][j] = table[(i + A) % N][(j + B) % N]
    return shifted


def countGoodShift(table):
    count = 0
    for a in range(N):
        for b in range(N):
            shifted = shiftTable(table, a, b)
            if isGoodTable(shifted, a, b):
                count += 1
    return count


print(countGoodShift(S))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ban = []
for i in range(N):
    ban.append(list(input()))
res = 0

for i in range(N):
    for j in range(N):
        flag = True
        for k in range(N):
            for l in range(k+1,N):
                if ban[(k-i)%N][(l-j)%N] != ban[(l-i)%N][(k-j)%N]:
                    flag = False
                    break
            if not flag:break
        if flag:res+=1
        
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
A = [[ord(i) for i in input()] for j in range(n)]
count = 0
for a in range(n):
    for b in range(n):
        arr = np.roll(A, a, axis=0)
        arr = np.roll(arr, b, axis=1)
        if np.allclose(arr,arr.T):
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
exec("def nWord(): nWord.cache = raw_input() if not hasattr(nWord, 'cache') or nWord.cache=='' else nWord.cache ; pos = nWord.cache.find(nWord.sep) ; ret, nWord.cache = (nWord.cache, '') if pos==-1 else (nWord.cache[:pos], nWord.cache[pos+1:].lstrip(nWord.sep)) ; return ret") ; exec("nWord.sep = ' '") ; exec("def ___nLine2(): ret, nWord.cache = (raw_input(), nWord.cache if hasattr(nWord, 'cache') else '') if not hasattr(nWord, 'cache') or nWord.cache=='' else (nWord.cache, '') ; return ret") ; exec('def nInt(): return int(nWord())') ; exec('def nFloat(): return float(nWord())') ; exec("def ___nAuto2():\n ret = nWord()\n try: return int(ret)\n except: pass\n try: return float(ret)\n except: return ret") ; exec("def nAuto(n=None): return ___nAuto2() if n is None else [___nAuto2() for i in range(n)]") ; exec("def nLine(n=None): return ___nLine2() if n is None else [___nLine2() for i in range(n)]")

N = nAuto()
S = nAuto(N)

D = {}
for  i in range(N):
    for j in range(N):
        c = S[i][j]
        if c in D:
            D[c] += 1
        else:
            D[c] = 1

max_c = 'a'
max_count = 0
for c in D:
    if max_count < D[c]:
        max_count = D[c]
        max_c = c

L = []
for  i in range(N):
    for j in range(N):
        c = S[i][j]
        if c!=max_c:
            L.append((i, j, c))

def check(A, B):
    for i2, j2, c in L:
        i = (i2-A+N) % N
        j = (j2-B+N) % N
        if c!=S[(A+j) % N][(B+i) % N]:
            return False
    return True

ng = 0
count = 0
for A in range(N):
    for B in range(N):
        if check(A, B):
            count += 1
            if 1000<=count and ng==0:
                print N*N
                exit()
        else:
            ng += 1
print count