Problem:


Score : 300 points

Problem Statement

There are N towns in a coordinate plane. Town i is located at coordinates (x_i, y_i). The distance between Town i and Town j is \sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}.

There are N! possible paths to visit all of these towns once. Let the length of a path be the distance covered when we start at the first town in the path, visit the second, third, \dots, towns, and arrive at the last town (assume that we travel in a straight line from a town to another). Compute the average length of these N! paths.

Constraints

2 \leq N \leq 8

-1000 \leq x_i \leq 1000

-1000 \leq y_i \leq 1000

\left(x_i, y_i\right) \neq \left(x_j, y_j\right) (if i \neq j)

(Added 21:12 JST) All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the average length of the paths.
Your output will be judges as correct when the absolute difference from the judge's output is at most 10^{-6}.

Sample Input 1

3
0 0
1 0
0 1

Sample Output 1

2.2761423749

There are six paths to visit the towns: 1 → 2 → 3, 1 → 3 → 2, 2 → 1 → 3, 2 → 3 → 1, 3 → 1 → 2, and 3 → 2 → 1.

The length of the path 1 → 2 → 3 is \sqrt{\left(0-1\right)^2+\left(0-0\right)^2} + \sqrt{\left(1-0\right)^2+\left(0-1\right)^2} = 1+\sqrt{2}.

By calculating the lengths of the other paths in this way, we see that the average length of all routes is:

\frac{\left(1+\sqrt{2}\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)}{6} = 2.276142...

Sample Input 2

2
-879 981
-866 890

Sample Output 2

91.9238815543

There are two paths to visit the towns: 1 → 2 and 2 → 1. These paths have the same length.

Sample Input 3

8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310

Sample Output 3

7641.9817824387



Sample input:
3
0 0
1 0
0 1


Sample output:
2.2761423749

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    import numpy as np
    n=int(input())
    l=[list(map(int,input().split())) for i in range(n)]
    import itertools
    ans=0
    p=list(itertools.permutations(l))
    for x in p:
        z = list(x)
        for y in range(n-1):
            a=np.array(z[y])
            b=np.array(z[y+1])
            ans+=np.linalg.norm(a-b)
    print(ans/len(list(p)))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
import numpy as np
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dist(p1, p2):
	p1 = np.array(p1)
	p2 = np.array(p2)
	return np.linalg.norm(p1-p2)

N = INT()
xy = [LIST() for _ in range(N)]

distance = 0
cnt = 0

for p in permutations(xy, N):
	cnt += 1
	for i in range(N-1):
		distance += dist(p[i], p[i+1])

print(distance/cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
zahyo =[list(map(int,input().split())) for _ in range(N)]
N_list = [i for i in range(N)]
P = itertools.permutations(N_list,N)
P = list(P)
L = []
for p in P:
    for i,j in zip(p,p[1:]):
        xi,yi = zahyo[i]
        xj,yj = zahyo[j]
        L.append(((xi-xj)**2+(yi-yj)**2)**0.5)
    Lsum = sum(L)
print(Lsum/len(P))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
zahyo =[list(map(int,input().split())) for _ in range(N)]
N_list = [i for i in range(N)]
P = itertools.permutations(N_list,N)
P = list(P)
L = []
for i in range(len(P)):
    for j in range(N-1):
        I = P[i][j]
        J = P[i][j+1]
        xi = zahyo[I][0]
        xj = zahyo[J][0]
        yi = zahyo[I][1]
        yj = zahyo[J][1]
        L.append(((xi-xj)**2+(yi-yj)**2)**0.5)
    Lsum = sum(L)
print(Lsum/len(P))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations, tee
import numpy as np

n = int(input())
pos = [np.array(list(map(int, input().split()))) for _ in range(n)]

def pairwise(itr):
    a, b = tee(itr)
    next(b, None)
    return zip(a, b)

dist = np.array([])
for p in permutations(pos):
    d = 0
    for i, j in pairwise(p):
        d += np.linalg.norm(i-j)
    dist = np.append(dist, d)
print(np.mean(dist))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import numpy as np
import sys
input = sys.stdin.readline

n = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(n)])

n_list = [l for l in range(n)]
dsum = 0
for i in itertools.permutations(n_list, n):
    skip = 1
    for j in i:
        if skip:
            skip = 0
            xy1 = xy[j]
        else:
            xy2 = xy[j]
            dsum += np.sqrt(np.sum((xy1 - xy2)**2))
            xy1 = xy2

print(dsum/math.factorial(n))

Submission status: Time Limit Exceeded

Solution code:
import itertools,math,numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
xy = np.array(sorted([LI() for _ in range(N)]))
sum_norm = 0
for a in itertools.permutations(range(N)):
    for i in range(len(a)-1):
        sum_norm += np.linalg.norm(xy[a[i+1]]-xy[a[i]])
print(sum_norm/math.factorial(N))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

N = int(input())

x_y_list = []
for i in range(N):
    x, y = list(map(int, input().split()))
    x_y_list.append((x, y))

average_distance = 0
count = 0
for v in itertools.permutations(x_y_list, N):
    dis = 0
    for i in range(N - 1):
        dis = np.sqrt(np.abs(v[i][0] - v[i + 1][0])**2 + np.abs(v[i][1] - v[i + 1][1])**2)
        average_distance += dis
    count += 1

print('{:.10f}'.format(average_distance / count))

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
N=int(input())
S = [list(map(int, input().split())) for i in range(N)]

#町のいく順番　順列
from itertools import permutations
import math
from statistics import mean
junban=[]
for t in permutations(range(N)):
    if t[::-1] not in junban:
        junban.append(t)
#junban =[ t for t in permutations(range(N)) ]
#junban =junban_2[:len(junban_2)//2] # 逆順は考えなくていい
j_len =len(junban) # 順番の要素数
x =[] #距離
x_sum =[]

def kyori(a,b): 
    return math.sqrt(pow( S[a][0]-S[b][0],2) + pow( S[a][1] - S[b][1],2) )

# 各点の距離　　組み合わせ
from itertools import combinations
kumiawase = [t for t in combinations(range(N), 2)]
kyori_all ={i:kyori(i[0],i[1]) for i in kumiawase}

#
for i in junban:
    for ji,jv in enumerate(i[:-1]):
        if i[ji]<i[ji+1]:
            x.append(kyori_all[ i[ji],i[ji+1] ] )
        if i[ji+1]<i[ji]:
            x.append(kyori_all[ i[ji+1],i[ji] ] )

    y =sum(x)    
    x_sum.append(y)
    x.clear()
kotae =mean(x_sum) 

print(kotae)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
from scipy.spatial import distance

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

n_fct = math.factorial(n)
d = [0] * n_fct
for i in itertools.permutations(l):
    for j in range(n-1):
        if j+1 < n:
            d[j] += distance.euclidean((i[j][0], i[j][1]), (i[j+1][0], i[j+1][1]))
        else:
            d[j] += distance.euclidean((i[j][0], i[j][1]), (i[0][0], i[0][1]))

print(sum(d)/len(d))

Submission status: Time Limit Exceeded

Solution code:
import decimal
from itertools import permutations

decimal.getcontext().prec = 16

cache = {}


def distance(a, b):
  if b < a:
    a, b = b, a
  key = a + b
  if key in cache:
    return cache[key]
  else:
    v = decimal.Decimal(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2)).sqrt()
    cache[key] = v
    return v


N = int(input())

P = [None] * N
for i in range(N):
  P[i] = tuple(map(int, input().split()))

total = decimal.Decimal(0)
count = 0
for points in permutations(P, len(P)):
  it = iter(points)
  last = next(it)
  for p in it:
    total += distance(p, last)
    last = p
  count += 1

print(total / count)

Submission status: Time Limit Exceeded

Solution code:
import decimal
from itertools import permutations


decimal.getcontext().prec = 16

def distance(a, b):
  return decimal.Decimal(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2)).sqrt()


N = int(input())

P = [None] * N
for i in range(N):
  P[i] = tuple(map(int, input().split()))

total = decimal.Decimal(0)
count = 0
for points in permutations(P, len(P)):
  it = iter(points)
  last = next(it)
  for p in it:
    total += distance(p, last)
    last = p
  count += 1

print(total / count)

Submission status: Time Limit Exceeded

Solution code:
import decimal
from itertools import permutations


def distance(a, b):
  return decimal.Decimal(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2)).sqrt()


N = int(input())

P = [None] * N
for i in range(N):
  P[i] = tuple(map(int, input().split()))

total = decimal.Decimal(0)
count = 0
for points in permutations(P, len(P)):
  it = iter(points)
  last = next(it)
  for p in it:
    total += distance(p, last)
    last = p
  count += 1

print(total / count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import numpy as np

N = int(input())
x= []
y = []
town = []
for i in range(N):
    x_i,y_i = (int(x) for x in  input().split())
    x.append(x_i)
    y.append(y_i)
    town.append(i)

grand_sum = 0.0
for v in itertools.permutations(town):
    d_sum = 0.0
    v = list(v)
    for i in range(len(v)-1):
        n1 = np.array([x[v[i]],y[v[i]]])
        n2 = np.array([x[v[i+1]],y[v[i+1]]])
        d_sum += np.linalg.norm(n2-n1)

    grand_sum += d_sum
    
print(grand_sum / math.factorial(N))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations
from math import factorial
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
XY = np.array([list(map(int, readline().split())) for _ in range(N)])

dist = 0
for route in permutations(XY, N):
    acc = 0
    dists = [
        np.sqrt(sum(pow(route[i] - route[i + 1], 2))) for i in range(N - 1)
    ]
    dist += sum(dists)
print(dist / factorial(N))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
XY = np.array([list(map(int, readline().split())) for _ in range(N)])

dist = 0
cnt = 0
for route in permutations(XY, N):
    acc = 0
    for i in range(N - 1):
        acc += np.sqrt(sum(pow(route[i] - route[i + 1], 2)))
    dist += acc
    cnt += 1
print(dist / cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
XY = np.array([list(map(int, readline().split())) for _ in range(N)])

dist = []
for route in permutations(XY, N):
    acc = 0
    for i in range(N - 1):
        acc += np.sqrt(sum(pow(route[i] - route[i + 1], 2)))
    dist.append(acc)

print(np.mean(dist))

Submission status: Time Limit Exceeded

Solution code:
import sys,math,itertools
import numpy as np

n=int(sys.stdin.readline())
a=np.array([sys.stdin.readline().split() for _ in range(n)],dtype='int64')

to=0
num=0

for i in itertools.permutations(range(n)):
    f=0
    num+=1
    for j in i:
        if f!=0:
            x=a[j,0]
            y=a[j,1]
            tot=((x-x0)**2+(y-y0)**2)**(1/2)
            to+=tot
            x0=x
            y0=y
        else:
            f=1
            x0=a[j,0]
            y0=a[j,1]

print(to/num)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n=int(input())
lis=[input().split() for i in range(n)]

res=[]
for i in range(n):
    for j in range(i+1,n):
        dist=(int(lis[i][0])-int(lis[j][0]))**2 + (int(lis[i][1])-int(lis[j][1]))**2
        res.append(dist)
sqrt_res = [i**0.5 for i in res]
ans = 0
perm = list(itertools.permutations(sqrt_res, n-1))
for v in perm:
    ans+=sum(v)
print(ans/len(perm))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from itertools import permutations

N = int(input())
mati = np.array([list(map(int, input().split())) for _ in range(N)])
total = 0

for v in permutations(mati,N):
    for i in range(N-1):
        total += np.linalg.norm(v[i+1]-v[i])
print(total/math.factorial(N))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import permutations
    import math
    import numpy as np
    tot = 0

    N = int(input())
    locs = np.array([
        [int(x) for x in input().split()]
        for _ in range(N)
    ])

    for order in permutations(range(N)):
        d = 0
        for i in range(N-1):
            i0 = order[i]
            i1 = order[i+1]
            d += np.linalg.norm(locs[i0]-locs[i1])
        tot += d
    print(tot/math.factorial(N))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
import math

def main():
    N = int(input())

    coordinate = np.array([[]])
    for _ in range(N):
        x, y = map(int, input().split())
        coordinate = np.append(coordinate, [x, y])
    coordinate = coordinate.reshape((N, 2))
    #print(coordinate)

    sum = 0

    for i in itertools.permutations(coordinate):
        v_1 = i[0]
        for j in range(1, len(i)):
            v_2 = i[j]
            sum += np.linalg.norm(v_1 - v_2)
            v_1 = v_2

    print(sum/math.factorial(N))
    return 0
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
import math

def main():
    N = int(input())

    coordinate = []
    for _ in range(N):
        x, y = map(int, input().split())
        coordinate.append((x, y))

    path = [i for i in range(N)]
    sum = 0

    for i in itertools.permutations(path):
        v_1 = np.array(coordinate[i[0]])
        for j in range(1, len(i)):
            v_2 = np.array(coordinate[i[j]])
            sum += np.linalg.norm(v_1 - v_2)
            #print(np.linalg.norm(v_1 - v_2))
            v_1 = v_2


    print(sum/math.factorial(N))
    return 0
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

n = int(input())
x = [list(map(int, input().split())) for i in range(n)]

res = 0
cnt = 0
for v in itertools.permutations(x):
  for i in range(n-1):
    res += np.linalg.norm(np.array(v[i+1])-np.array(v[i]))
  cnt += 1

print((res+0.0)/cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

N = int(input())

X = []
for i in range(N):
  X.append(list(map(int,input().split())))

pattern = list(itertools.permutations(X))
dist_sum = 0

for i in pattern:
  for j in range(N-1):
    a = np.array(i[j])
    b = np.array(i[j+1])
    dist = np.linalg.norm(a-b)
    dist_sum += dist

#平均計算
dist_avr = dist_sum / len(pattern)
print(dist_avr)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools as it
n=int(input())
x=[]
for i in range(n):
	X=list(map(int,input().split()))
	x.append(X)
x=np.array(x)
ans=0
roots=list(it.permutations(range(n)))
for root in roots:
	for i in range(1,n):
		d=np.linalg.norm(x[root[i-1]]-x[root[i]])
		ans+=d
print('{:.8f}'.format(ans/len(roots)))

Submission status: Time Limit Exceeded

Solution code:
from statistics import mean
from itertools import combinations
dist = lambda p1, p2: ((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2) ** (1 / 2)

N = int(input())
P = (tuple(map(int, input().split())) for _ in range(N))

distances = (dist(*combination) for combination in combinations(P, 2))
total_distance = (sum(distance) for distance in combinations(distances, N - 1))
print(mean(total_distance))

Submission status: Time Limit Exceeded

Solution code:
import numpy
import itertools
import math
n = int(input())
town_list = []
for i in range(n):
	x, y = map(int, input().split())
	town_list.append(numpy.array([x, y]))

pattern_list = list(itertools.permutations(town_list, n))

sum = 0
for j in range(math.factorial(n)):
	for k in range(n-1):
		sum += numpy.linalg.norm(pattern_list[j][k+1] - pattern_list[j][k])

print(sum/math.factorial(n))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations
from math import factorial

N = int(input())

points = []
for i in range(0,N):
    points.append(list(map(int,input().split())))

p = permutations(points,N)

average = 0
for j in p:
    for k in range(0,len(j)-1):
        average += np.linalg.norm(np.array(j[k+1])-np.array(j[k]))

print('{:.10f}'.format(average/factorial(N)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
from math import factorial

N = int(input())

points = []
for i in range(0,N):
    points.append(list(map(int,input().split())))

p = itertools.permutations(points,N)

average = 0
for j in p:
    for k in range(0,len(j)-1):
        average += np.linalg.norm(np.array(j[k+1])-np.array(j[k]))

print('{:.10f}'.format(average/factorial(N)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
num=int(input())
List=[[int(e) for e in input().split()] for i in range(num)]
List=np.array(List)

#distance関数  
def distance(x,y):
  delta=List[x]-List[y]
  length=(delta[0]**2+delta[1]**2)**(1/2)
  return length
  
#順列リスト作る
order=[i for i in range(num)]
jun=list(itertools.permutations(order))

final_ans=[]
#その順列にしたがって、for文で計算：結果をansに加え、平均値とる
for k in jun:
  ans=[]
  for j in range(num-1):
    length = distance(k[j],k[j+1])
    ans.append(length)
  final_ans.append(sum(ans))
print(np.average(final_ans))

Submission status: Time Limit Exceeded

Solution code:
import math

n=int(input())
info=[[0]]
for i in range(n):
    x,y=map(int,input().split())
    info.append([x,y])
max_num=""
for i in range(n,0,-1):
    max_num+=str(i)

def sitigosan(num):
    total=0
    if int(num)>int(max_num):
        return 0
    check=0
    #print(num)
    for i in range(1,n+1):
        if str(i) not in num:
            check=1
            break
    if check==0:
        total+=kyori(num)
    for i in max_num:
        total+=sitigosan(num+i)
    return total

def kyori(num):
    d=0
    a=list(num)
    for i in range(1,len(a)-1):
        d+=math.sqrt((info[int(a[i])][0]-info[int(a[i+1])][0])**2+(info[int(a[i])][1]-info[int(a[i+1])][1])**2)
    return d

ans=sitigosan("0")/(math.factorial(n))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

def solve(n, x, y):
    total, num = 0, 0
    for p in itertools.permutations(range(n)):
        num += 1
        for i in range(n-1):
            total += np.linalg.norm([x[p[i+1]]-x[p[i]],y[p[i+1]]-y[p[i]]])
    return total / num

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
import math

# print('input >>')
N = int(input())
towns = []
for _ in range(N):
    x, y = map(int,(input().split()))
    towns.append(np.array([x,y]))

sum = 0
perms = itertools.permutations(towns, N)

for path in perms:
    distance = 0
    for i in range(len(path) - 1):
        distance += np.linalg.norm(path[i]-path[i + 1])
    sum += distance

# print('----------output----------')
print(sum / math.factorial(N))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import copy
from math import factorial

def solve():
    N = int(input())
    cities = [[None, None]]
    for i in range(N):
        x, y = list(map(int, input().split()))
        cities.append([x,y])

    def calc_distance(a, b):
        return ((a[0]-b[0])**2+(a[1]-b[1])**2)**(1/2)

    memo = {}  # 距離の事前計算
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            memo[(i,j)] = calc_distance(cities[i], cities[j])

    def dfs(will_visit, visited, now_i, total_d):
        if now_i is None:
            ans = 0
            for i in will_visit:
                new_will_visit = copy.deepcopy(will_visit)
                new_visited = copy.deepcopy(visited)
                new_will_visit.remove(i)
                new_visited.add(i)
                ans += dfs(new_will_visit, new_visited, i, 0)
            return ans

        if will_visit == []:
            return total_d

        ans = 0
        for i in will_visit:
            if i in visited: continue
            new_will_visit = copy.deepcopy(will_visit)
            new_visited = copy.deepcopy(visited)
            new_will_visit.remove(i)
            new_visited.add(i)
            ans += dfs(new_will_visit, new_visited, i, total_d+memo[min(now_i, i), max(now_i, i)])
        return ans

    will_visit = [i for i in range(1, N+1)]
    visited = set()
    ans = dfs(will_visit, visited, None, 0)
    print(ans/factorial(N))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import copy
from math import factorial

def solve():
    N = int(input())
    cities = [[None, None]]
    for i in range(N):
        x, y = list(map(int, input().split()))
        cities.append([x,y])

    def calc_distance(a, b):
        return ((a[0]-b[0])**2+(a[1]-b[1])**2)**(1/2)

    def dfs(will_visit, visited, now_i, total_d):
        if now_i is None:
            ans = 0
            for i in will_visit:
                new_will_visit = copy.deepcopy(will_visit)
                new_visited = copy.deepcopy(visited)
                new_will_visit.remove(i)
                new_visited.add(i)
                ans += dfs(new_will_visit, new_visited, i, 0)
            return ans

        if will_visit == []:
            return total_d

        ans = 0
        for i in will_visit:
            if i in visited: continue
            new_will_visit = copy.deepcopy(will_visit)
            new_visited = copy.deepcopy(visited)
            new_will_visit.remove(i)
            new_visited.add(i)
            ans += dfs(new_will_visit, new_visited, i, total_d+calc_distance(cities[now_i], cities[i]))
        return ans

    will_visit = [i for i in range(1, N+1)]
    visited = set()
    ans = dfs(will_visit, visited, None, 0)
    print(ans/factorial(N))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations

n = int(input())

li = []
for _ in range(n):
    i, j = map(int, input().split())
    li.append(np.array([i, j]))

li2 = permutations(li)

re = []
for a in li2:
    dis = 0 
    for (x1,y1),(x2,y2) in zip(a,a[1:]):
        dis += ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))**0.5
    re.append(dis)

print(np.average(re))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from itertools import permutations
N = int(input())
coodinate = [list(map(int,input().split())) for _ in range(N)]
coodinate = np.array(coodinate)
SumDistance = 0
for val in permutations(coodinate):
    for i in range(N-1):
        SumDistance += ((val[i+1][0] - val[i][0]) ** 2 + (val[i+1][1] - val[i][1]) ** 2) ** (1 / 2)
print(SumDistance / math.factorial(N))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations

n = int(input())
k = 0
dis = 0

li = []
for _ in range(n):
    i, j = map(int, input().split())
    li.append(np.array([i, j]))

li2 = permutations(li)

re = []
for a in li2:
    k += 1
    for (x1,y1),(x2,y2) in zip(a,a[1:]):
        dis += ((x1-x2)**2+(y1-y2)**2)**0.5

print(dis/k)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations

n = int(input())

li = []
for _ in range(n):
    i, j = map(int, input().split())
    li.append(np.array([i, j]))

li2 = permutations(li)

re = []
for a in li2:
    dis = 0 
    for (x1,y1),(x2,y2) in zip(a,a[1:]):
        dis += ((x1-x2)**2+(y1-y2)**2)**0.5
    re.append(dis)

print(np.average(re))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

num_list = []
result = 0

n = int(input())
town_array = [list(map(int,input().split(" "))) for i in range(n)]

new_town_array = tuple(itertools.permutations(town_array))

for i in range(len(new_town_array)):
  for j in range(n-1):
    a = np.array(new_town_array[i][j])
    b = np.array(new_town_array[i][j+1])
    result += np.linalg.norm(b-a)

print(result/len(new_town_array))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xy = []
for i in range(n):
	xy.append(list(map(int, input().split())))

a = []
num = [i for i in range(n)]
num2 = num.reverse()
m = "".join(map(str, num))
for i in range(int(m)+1):
	s = []
	for l in range(len(str(i))):
		s.append(str(i)[l])
	ii = ['0' for j in range(n-len(str(i)))] + s
	for l in range(len(ii)):
		ii[l] = int(ii[l])
	if set(ii) == set(num):
		a.append(ii)

dt = []
for i in range(len(a)):
	d = []
	for j in range(n-1):
		d.append(((xy[int(a[i][j])][0]-xy[int(a[i][j+1])][0])**2+(xy[int(a[i][j])][1]-xy[int(a[i][j+1])][1])**2)**(1/2))
	dt.append(sum(d))
print(sum(dt)/len(dt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations

n = int(input())

li = []
for _ in range(n):
    i, j = map(int, input().split())
    li.append(np.array([i, j]))

li2 = permutations(li)
# f = lambda i : np.linalg.norm((a[i] - a[i+1]))

re = []
for a in li2:
    # dis = map(f, range(n-1))
    # print(a)
    b = np.array([i for i in a])
    dis = map(np.linalg.norm, (b[1:] - b[:-1]))
    re.append(sum(dis))

print(np.average(re))

Submission status: Time Limit Exceeded

Solution code:
import statistics
import math
from itertools import permutations, combinations,combinations_with_replacement,product



N = int(input())
s = []
d = []
l = []
for i in range(N):
    s.append(list(map(int,input().split())))
a = list(permutations(s))
b = len(a)

for c in range(b):
    for i in range(N):
        for j in range(i+1,N):
            d = math.sqrt(((a[c][j][0] - a[c][i][0])**2 + (a[c][j][1] - a[c][i][1])**2))
            l.append(d)
if N == 2:
    print(statistics.mean(l))
else:
    print(statistics.mean(l) * (N - 1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations

n = int(input())

li = []
for _ in range(n):
    i, j = map(int, input().split())
    li.append(np.array([i, j]))

li2 = permutations(li)
f = lambda i : np.linalg.norm((a[i] - a[i+1]))

re = []
for a in li2:
    dis = map(f, range(n-1))
    re.append(sum(dis))

print(np.average(re))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations

n = int(input())

li = []
for _ in range(n):
    i, j = map(int, input().split())
    li.append(np.array([i, j]))

li2 = permutations(li)

re = []
for a in li2:
    dis = map(np.linalg.norm, [(a[i] - a[i+1]) for i in range(len(a)-1)])
    re.append(sum(dis))

print(np.average(re))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import numpy as np
z = []
N = int(input())
for i in range(N):
  z.append(list(map(int,input().split(' '))))
d = 0  
x = []
p = list(itertools.permutations(z, N))
#print(p,N)  
for i in p:
  #print(i)
  #ans = math.sqrt((i[0][0]-i[1][0])**2) + math.sqrt((i[0][1]-i[1][1])**2)
  for j in range(N-1):
    #print(j,i)
    d += np.linalg.norm(np.array([i[j+1][0],i[j+1][1]]) - np.array([i[j][0],i[j][1]]))
    #print(([i[j+1][0],i[j+1][1]]), ([i[j][0],i[j][1]]))
  x.append(d) 
  d = 0
  
  
#  print(ans)
  
#print(x)  
print(sum(x)/len(x))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

num_list = []
new_list = []
result = 0

n = int(input())
town_array = [list(map(int,input().split(" "))) for i in range(n)]

for i in range(n):
  num_list.append(i)

list_array = list(itertools.permutations(num_list))

# print(list_array)

for i in range(len(list_array)):
  for j in list_array[i]:
    new_list.append(town_array[j])
  
  for k in range(n-1):
    a = np.array(new_list[k])
    b = np.array(new_list[k+1])
    result += np.linalg.norm(b-a)
  # print(new_list)
  new_list = []

print(result/len(list_array))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations, permutations

n = int(input())
ls = [list(map(int, input().split())) for _ in range(n)]


def mean_dis(data):
    comb = permutations(data, n)
    sum = 0
    count = 0
    for c in comb:
        count += 1
        for i in range(1, len(c)):
            _c = np.array([c[i-1], c[i]])
            euclid = np.sqrt(np.sum((_c[0]-_c[1]) ** 2))
            sum += euclid
    return sum/count


print(mean_dis(ls))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy

n = int(input())

seq = []
for _ in range(n):
  i = list(map(int, input().split(" ")))
  seq.append(i)
  
count = 0
results = []
for path in itertools.permutations(seq):
  pwd = None
  count += 1
  for p in path:
    if pwd is None:
      pwd = p
    else:
      a = numpy.array(pwd)
      b = numpy.array(p)
      u = b - a
      results.append(numpy.linalg.norm(u))
      pwd = p
print(sum(results) / count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations

n = int(input())

li = []
for _ in range(n):
    i, j = map(int, input().split())
    li.append(np.array([i, j]))

li2 = permutations(li)

re = []
for a in li2:
    dis = [np.linalg.norm(a[i] - a[i+1]) for i in range(len(a)-1)]
    re.append(sum(dis))

print(np.average(re))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy

n = int(input())

seq = []
for _ in range(n):
  i = list(map(int, input().split(" ")))
  seq.append(i)
  
permutations = list(itertools.permutations(seq))

results = []
for path in itertools.permutations(seq):
  pwd = None
  for p in path:
    if pwd is None:
      pwd = p
    else:
      a = numpy.array(pwd)
      b = numpy.array(p)
      u = b - a
      results.append(numpy.linalg.norm(u))
      pwd = p
print(sum(results) / len(permutations))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import numpy as np

lines = sys.stdin.readlines()

N = int(lines[0].rstrip())
perms = list(itertools.permutations(range(N)))

arr_2d = np.zeros((N,2))
arr_dist = np.zeros(len(perms))

for i, line in enumerate(lines[1:]):
    x, y = map(int,line.split(' '))
    arr_2d[i, 0] = x
    arr_2d[i, 1] = y


index = 0
for l in perms:
    for i in range(N-1):
        arr_dist[index] += np.linalg.norm(arr_2d[l[i]] - arr_2d[l[i+1]])
    index += 1
    
print(np.mean(arr_dist))