Problem:
 Score : 900 points    Problem Statement  Diverta City is a new city consisting of N towns numbered 1, 2, ..., N .  The mayor Ringo is planning to connect every pair of two different towns with a bidirectional road. The length of each road is undecided.  A Hamiltonian path is a path that starts at one of the towns and visits each of the other towns exactly once.
The reversal of a Hamiltonian path is considered the same as the original Hamiltonian path.  There are N! / 2 Hamiltonian paths. Ringo wants all these paths to have distinct total lengths (the sum of the lengths of the roads on a path), to make the city diverse.  Find one such set of the lengths of the roads, under the following conditions:   The length of each road must be a positive integer.  The maximum total length of a Hamiltonian path must be at most 10^{11} .       Constraints   N is a integer between 2 and 10 (inclusive).         Input  Input is given from Standard Input in the following format:  N       Output  Print a set of the lengths of the roads that meets the objective, in the following format:  w_{1, 1} \ w_{1, 2} \ w_{1, 3} \ ... \ w_{1, N}  w_{2, 1} \ w_{2, 2} \ w_{2, 3} \ ... \ w_{2, N}  :  :  :  w_{N, 1} \ w_{N, 2} \ w_{N, 3} \ ... \ w_{N, N}   where w_{i, j} is the length of the road connecting Town i and Town j , which must satisfy the following conditions:   w_{i, i} = 0  w_{i, j} = w_{j, i} \ (i \neq j)  1 \leq w_{i, j} \leq 10^{11} \ (i \neq j)   If there are multiple sets of lengths of the roads that meet the objective, any of them will be accepted.        Sample Input 1 3      Sample Output 1 0 6 15
6 0 21
15 21 0  There are three Hamiltonian paths. The total lengths of these paths are as follows:   1 → 2 → 3 : The total length is 6 + 21 = 27 .  1 → 3 → 2 : The total length is 15 + 21 = 36 .  2 → 1 → 3 : The total length is 6 + 15 = 21 .   They are distinct, so the objective is met.       Sample Input 2 4      Sample Output 2 0 111 157 193
111 0 224 239
157 224 0 258
193 239 258 0  There are 12 Hamiltonian paths, with distinct total lengths.

Solution (Python):
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    base=[1, 2, 4, 7, 12, 20, 29, 38, 52, 73]

    ans=[[0]*n for _ in range(n)]
    ans[1][0]=ans[0][1]=1

    for vn in range(3,n+1):
        mx=0
        for path in permutations(range(vn-1)):
            cur=sum(ans[v0][v1] for v0,v1 in zip(path,path[1:]))
            if cur>mx:mx=cur

        ans[vn - 1][0] = ans[0][vn - 1] = base[vn-2] * (mx + 1)
        ans[vn - 1][vn-2] = ans[vn-2][vn - 1] = base[vn-3] * (mx + 1)
        for j in range(1,vn-2):
            ans[vn-1][j]=ans[j][vn-1]=base[j-1]*(mx+1)

    for row in ans:print(*row)

main()

Solution (Python):
import sys
input = sys.stdin.readline

import itertools

N = int(input())

A = [1,2,4]
for _ in range(12):
    sum_2 = set(x+y for x,y in itertools.combinations(A,2))
    avoid = set(x-y for x,y in itertools.product(sum_2,A))
    x = min(set(range(1,1000)) - avoid - sum_2 - set(A))
    A.append(x)

L = [[0] * (N-1-i) for i in range(N)]

x = 1
for n in range(N):
    L[n] = [x*a for a in A[:N-1-n]]
    if n < N-2:
        x = L[n][-1] + L[n][-2]

graph = [[0] * N for _ in range(N)]
for i in range(N):
    for j,x in enumerate(L[i]):
        graph[i][i+j+1] = x
        graph[i+j+1][i] = x

for row in graph:
    print(*row)

Solution (Python):
N = int(input())

s = []
t = []
i = 1
while len(s) < N :
    if i in t or any(i + s_ in t for s_ in s) :
        i += 1
        continue
    
    t.append(i)
    for s_ in s :
        t.append(i+s_)
    
    s.append(i)
    i += 1

w = [[0] * 10 for _ in range(10)]
w[0][1] = w[1][0] = 1

M = 1
for n in range(3, N + 1) :
    M += 1
    for i in range(n-1) :
        w[i][n-1] = w[n-1][i] = M * s[i]
        
    M += w[n-1][n-2] + w[n-1][n-3] - w[n-2][n-3] - 1
    
for i in range(N) :
    print(' '.join([str(j) for j in w[i][:N]]))

Solution (Python):
from itertools import combinations, permutations

N = int(input())




    
    
    
        
        
        
            
                
            
                
                
        
            
            
        
            
            
s = [1, 2, 4, 7, 12, 20, 29, 38, 52, 73]

w = [[0] * 10 for _ in range(10)]
w[0][1] = w[1][0] = 1

for n in range(3, N + 1) :
    
    M = 0
    for perm in permutations(range(n-1), n-1) :
        tmp = 0
        for i in range(n-2) :
            tmp += w[perm[i]][perm[i+1]]
        M = max(M, tmp)
    
    M += 1
    
    
    for i in range(n-1) :
        w[i][n-1] = w[n-1][i] = M * s[i]
        
        
for i in range(N) :
    print(' '.join([str(j) for j in w[i][:N]]))

Solution (Python):
def solve(n):
    if n == 2:
        print('0 1\n1 0')
        return

    can = []
    ban = set()

    k = 1
    while len(can) < 9:
        if k in ban or any(k + l in ban for l in can):
            k += 1
            continue
        ban.add(k)
        ban.update(k + l for l in can)
        can.append(k)
        k += 1

    ans = [[0] * n for _ in [0] * n]
    ans[0][1] = ans[1][0] = 1
    longest_path = 1
    for i in range(2, n):
        np = longest_path + 1
        for j, c in zip(range(i), can):
            ans[i][j] = ans[j][i] = np * c
        longest_path += ans[i][i - 1] + ans[i][i - 2] - ans[i - 1][i - 2]

    print('\n'.join(' '.join(map(str, row)) for row in ans))


n = int(input())
solve(n)