Problem:


Score : 400 points

Problem Statement

We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:

For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.

There is an edge between Vertex X and Vertex Y.

For each k=1,2,...,N-1, solve the problem below:

Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

Constraints

3 \leq N \leq 2 \times 10^3

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

For each k=1, 2, ..., N-1 in this order, print a line containing the answer to the problem.

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

There are five pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).

There are four pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).

There is one pair (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 3: (1,5).

There are no pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 4.

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Time Limit Exceeded

Solution code:
import pprint
from itertools import chain
import collections
n, x, y = (int(each) for each in input().split(' '))

# table1 = [[0] * n for i in range(n)]
# table2 = [[0] * n for i in range(n)]
table_shortest = [[0] * n for i in range(n)]
# cntr = {}

# # 点iから点jまでの距離をテーブルにする

# # 抜け道を通らないルートの場合
# for i in range(n):
#     for j in range(n):
#         if j-i > 0:
#             table1[i][j] = j-i

# # 抜け道を通るルートの場合
# for i in range(n):
#     for j in range(n):
#         if j-i > 0:
#             table2[i][j] = abs(j-y+1)+abs(i-x+1)+1

# どちらか近いほうのルートが最短距離
for i in range(n):
    for j in range(n):
        if j-i > 0:
            table_shortest[i][j] = min(j-i, abs(j-y+1)+abs(i-x+1)+1)

# テーブルをflattenして数をかぞえる
cntr = collections.Counter(list(chain.from_iterable(table_shortest)))

cntr = dict(cntr)
for each in range(1,n):
    print(cntr.get(each, 0))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, X, Y = map(int, input().split())

result = []
for i, j in combinations(range(1, N+1), 2):
    jy = abs(Y-j)
    ix = abs(X-i)
    if (j-i)<=(jy+ix+1):
        result.append(j-i)
    else:
        result.append(jy+ix+1)
print(N)
for i in range(1, N-1):
    print(result.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python


def check(p, points, d2):
    if p in points:
        points.remove(p)
        d2.add(p)
    return points, d2


def check(p1, p2, d2, c):
    # print(p1, p2)
    if p1 >= p2 or p1 < 0 or p2 > n - 1:
        return c
    d1 = abs(p1 - p2)
    # d2 = i + j + 1
    if d1 > d2:
        c[d1] -= 1
        c[d2] += 1
    return c


n, x, y = (int(v) for v in input().split())
x -= 1
y -= 1
if x > y:
    x, y = y, x
c = []
for i in range(n):
    c.append(n - i)
# print(c)
d = y - x

for i in range(0, n):
    for j in range(0, n):
        if i == 0 and j == 0:
            c = check(x, y, i + j + 1, c)
        elif i == 0:
            c = check(x, y + j, i + j + 1, c)
            c = check(x, y - j, i + j + 1, c)
        elif j == 0:
            c = check(x + i, y, i + j + 1, c)
            c = check(x - i, y, i + j + 1, c)
        else:
            c = check(x + i, y + j, i + j + 1, c)
            c = check(x + i, y - j, i + j + 1, c)
            c = check(x - i, y + j, i + j + 1, c)
            c = check(x - i, y - j, i + j + 1, c)
#     p1 = x + i
#     p2 = y + i
#     d1 = abs(p1 - p2)
#     d2 = i + j + 1
#     if d1 > d2:
#         c[d1] -= 1
#         c[d2] += 1

#     for j in range(n - y - 1):
#         c[d + i + j] -= 1
#         c[i + j] += 1
#     for j in range(int(d / 2) - 1):

# for i in range
# if i + j < int(d / 2):

#     # d = [[n] * n] * n

#     # c = [0] * (n - 1)
#     # for i in range(n):
#     #     points = set(range(n))
#     #     d1 = {i}
#     #     d2 = set()
#     #     points.remove(i)
#     #     for j in range(n - 1):
#     #         for d in d1:
#     #             points, d2 = check(d + 1, points, d2)
#     #             points, d2 = check(d - 1, points, d2)
#     #             if d == x:
#     #                 points, d2 = check(y, points, d2)
#     #             if d == y:
#     #                 points, d2 = check(x, points, d2)

#     #         c[j] += len(d2)
#     #         d1 = d2
#     #         d2 = set()
#     # # print('\n'.join([str(int(v / 2)) for v in c]))
for v in c[1:]:
    print(str(int(v)))

Submission status: Time Limit Exceeded

Solution code:
# D - Line++
import numpy as np 

N, X, Y = map(int, input().split())

T = np.zeros((N,N), dtype=np.int64)
for i in range(N):
    for j in range(i+1,N):
        T[i,j] = min(j-i, abs(i-X+1)+abs(j-Y+1)+1)

for k in range(1, N):
    print(np.count_nonzero(T==k))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)


def BFS(s):
    color=["white" for _ in range(n)]
    D=[float("inf") for _ in range(n)]

    color[s-1]="gray"
    D[s-1]=0
    queue=deque([s-1])

    while len(queue)!=0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return D


n,x,y=map(int,input().split())

M=[[] for _ in range(n)]
for i in range(n-1):
    M[i].append(i+1)
    M[i+1].append(i)
M[x-1].append(y-1)
M[y-1].append(x-1)

C=[0]*n
for i in range(n):
    for j in BFS(i+1)[i:]:
        C[j] +=1

for i in C[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import collections
N,X,Y = map(int,input().split())
ToltN=N*(N-1)/2
Dist=[[0 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i,N):    
        MyDist=abs(i-(X-1))+abs(j-(Y-1))+1
        if MyDist<j-i:
            Dist[i][j]=MyDist
        else:
            Dist[i][j] = j-i
for j in range(N-1):
    ans=[0]
    for i in range(N):
        ans+=Dist[i]
c = collections.Counter(ans)
for i in range(N-1):
    print(c[i+1])

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
from heapq import *
from collections import defaultdict

N,X,Y = map(int,input().split())
X -= 1
Y -= 1
cost_pri = defaultdict(list)
for i in range(N-1):
    cost_pri[i].append((i+1,1))
    cost_pri[i+1].append((i,1))
cost_pri[X].append((Y,1))
cost_pri[Y].append((X,1))
ans = [0]*(N-1)
for s in range(N):
    dist = [2**60]*N
    dist[s] = 0
    que = [[0,s]]
    heapify(que)
    while que:
        p = heappop(que)
        v = p[1]
        if dist[v] < p[0]:continue
        for e in cost_pri[v]:
            if dist[e[0]] > dist[v] + e[1]:
                dist[e[0]] = dist[v] + e[1]
                heappush(que,[dist[e[0]],e[0]])
    
    for a in dist[s+1:]:
        ans[a-1] += 1

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, X, Y = map(int, input().split())

result = []
for i, j in combinations(range(1, N+1), 2):
    if j<=X:
        result.append(j-i)
    else:
        jy = abs(Y-j)
        ix = abs(X-i)
        if (j-i)<=(jy+ix+1):
            result.append(j-i)
        else:
            result.append(jy+ix+1)
print(N)
for i in range(1, N-1):
    print(result.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations
from collections import Counter

N, X, Y = map(int, sys.stdin.readline().rstrip().split())

nodes = list(range(1, N + 1))
distance_counter = Counter()
a = Y - X - 1
p = (Y - X) // 2 + X
ans = []
for i, j in combinations(nodes, 2):
    if j - i == 1:
        distance = 1
        distance_counter[distance] += 1
        continue
    if i <= X:
        if j < Y:
            jtoX = min(Y - j + 1, j - X)
            distance = X - i + jtoX
        else:
            distance = j - i - a
    else:
        if j < Y:
            d1 = j - i
            d2 = i - X + Y - j + 1
            distance = min(d1, d2)
        else:
            itoY = min(i - X + 1, Y - i)
            distance = j - Y + itoY
    distance_counter[distance] += 1

for k in range(1, N):
    if k == 1:
        ans.append(N)
    else:
        ans.append(distance_counter.get(k, 0))

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

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = list(map(int, input().split(' ')))
X -= 1
Y -= 1
dist_map = {}

def search(origin):
  dist = []
  # X, Yの辺がない場合
  for i in range(N):
    dist.append(abs(origin - i))
  # X, Yの辺がある場合
  if dist[X] < dist[Y]:
    dist[Y] = dist[X] + 1
  elif dist[Y] < dist[X]:
    dist[X] = dist[Y] + 1
  for i in range(N):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  for i in reversed(range(N)):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  #print(*dist)
  return dist

count = [0 for i in range(N)]
for i in range(N):
  dist = search(i)
  for dis in dist:
    count[dis] += 1

for i in range(1, N):
  print(count[i]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def main():
    # n, x, y = 7, 3, 7
    n, x, y = [int(s) for s in sys.stdin.readline().strip().split()]
    score = {i: 0 for i in range(1, n)}
    total_pair = set()

    def bfs(start):
        seen = set()
        q = deque()
        q.append((0, start))
        while q:
            dist, cur = q.popleft()
            pair = (min(start, cur), max(start, cur))
            if pair in seen:
                continue
            seen.add(pair)
            if dist > 0:
                if pair not in total_pair:
                    score[dist] += 1
                    total_pair.add(pair)
            if cur < n-1:
                q.append((dist+1, cur+1))
            if cur > 0:
                q.append((dist+1, cur-1))
            if cur == x-1:
                q.append((dist+1, y-1))
            if cur == y-1:
                q.append((dist+1, x-1))

    for i in range(n-1):
        bfs(i)
    for i in range(1, n):
        print(score[i])

main()

Submission status: Time Limit Exceeded

Solution code:
# Reference: 
#   https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/?ref=lbp
#   https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/?ref=lbp

from collections import defaultdict,deque

class Graph(object):
  def __init__(self):
    self.graph = defaultdict(list)

  def addEdge(self, u, v):
    self.graph[u].append(v)
    self.graph[v].append(u)

  def search(self, v, searched, ns):
    visited = [False] * len(self.graph)

    visited[v] = True
    queue = deque([(v,0)])
    while queue:
      s,d = queue.popleft()
      k = lambda x,y: (min(x,y),max(x,y))
      s_ = [(i,d+1) for i in self.graph[s] if not visited[i]]
      queue.extend(s_)
      for i,_ in s_:
        visited[i] = True
        searched[k(v,i)] = min(searched[k(v,i)], d+1)
        
def main():
  g = Graph()
  N,X,Y = map(int, input().split())
  for i in range(N-1): g.addEdge(i,i+1)
  g.addEdge(X-1,Y-1)
  ans = defaultdict(int)
  searched = defaultdict(lambda :2*10**3)
  for i in range(N-1): g.search(i, searched, ans)
  for v in searched.values(): ans[v] += 1
  for i in range(1,N): print(ans[i])
  
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,x,y = map(int, input().split())
s = np.zeros((n,n))
t = np.zeros(n)
for i in range(0,n):
  for j in range(i,n):
    s[i][j] = abs(i-j)
x = x-1
y = y-1
s[x][y] = 1
for i in range(0,n):
  for j in range(i,n):
    a = abs(i-x)+abs(j-y)+1
    if a < s[i][j]:
      s[i][j] = a

for i in range(0,n):
  for j in range(i,n):
    for k in range(0,n):
      if k+1 == s[i][j]:
        t[k+1] += 1

for k in range(1,n):
  print(int(t[k]))

Submission status: Time Limit Exceeded

Solution code:
def item_add(dic, item):
    if item in dic.keys():
        dic[item] += 1
    else:
        dic[item] = 1
    return dic

n, x, y = map(int, input().split())

ans_dict = {}

for i in range(n-1):
    for j in range(i+1,n):
        # ショートカットできない場合
        # print(i,j)
        if j < x:
            temp = j-i
            ans_dict = item_add(ans_dict,temp)
        else:
            shortcut = abs((x-1) - i) + 1 + abs((y-1) -j )
            not_shortcut = j-i
            temp = min(shortcut,not_shortcut)
            ans_dict = item_add(ans_dict,temp)
        # print(temp)




for i in range(1,n):
    if i in ans_dict.keys():
        print(ans_dict[i])
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappush, heappop

N, X, Y = [int(i) for i in input().split()]
X -= 1
Y -= 1
G = [[] for _ in range(N)]
for i in range(N):
    if i!=0: G[i].append((i-1, 1))
    if i!=N-1: G[i].append((i+1, 1))
G[X].append((Y, 1))
G[Y].append((X, 1))

INF = 10**30
def Johnson(G, N):
    h = [0]*N

    update = 1
    for i in range(N):
        update = 0
        for v in range(N):
            d = h[v]
            for w, c in G[v]:
                if c + d < h[w]:
                    h[w] = d + c
                    update = 1
        if not update:
            break
    else:
        return None

    for v in range(N):
        d = h[v]
        g = G[v]
        for j, (w, c) in enumerate(g):
            g[j] = (w, c + d - h[w])

    D = []
    for i in range(N):
        dst = [INF]*N
        dst[i] = 0
        que = [(0, i)]
        while que:
            cost, v = heappop(que)
            if dst[v] < cost:
                continue
            for w, c in G[v]:
                if cost + c < dst[w]:
                    dst[w] = r = cost + c
                    heappush(que, (r, w))
        v = h[i]
        for j in range(N):
            if dst[j] == INF:
                dst[j] = INF
            else:
                dst[j] -= v - h[j]
        D.append(dst)

    return D
res = [0]*(N+2)
D = Johnson(G, N)
for i in range(N):
    for j in range(i+1, N):
        res[D[i][j]] += 1

for i in range(1, N):
    print(res[i])

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split(' '))

dct = {X : Y}
short = Y - X - 1

dist_list = []

for i in range(1,N):
    for j in range(i+1,N+1):
        d1 = abs(X - i) + 1 + abs(Y - j)
        d2 = j - i
        dist = min(d1,d2)
        dist_list.append(dist)

for k in range(1,N):
    print(dist_list.count(k))

Submission status: Time Limit Exceeded

Solution code:



def main():
    N, X, Y = map(int, input().split())

    G = [0]*N
    D = [0]*N
    for i in range(N):
        if i == 0:
            G[0] = [1]
        elif i == N-1:
            G[N-1] = [N-2]
        else:
            G[i] = [i-1, i+1]
        if i+1 == X:
            G[i].append(Y-1)
        if i+1 == Y:
            G[i].append(X-1)

        D[i] = [1 if j in G[i] else N for j in range(N)]

    import numpy as np
    D =np.array(D)

    for k in range(N):
        tmp = np.tile(D[:,k],(N,1))
        tmp_D = tmp + tmp.T
        D = np.min([D, tmp_D], axis=0)

    for i in range(1,N):
        tmp = (D==i).sum()
        if i ==2:
            tmp = tmp - N
        print(tmp//2)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
N,X,Y = list(map(int,input().split()))

dist= [[N for i in range(N+1)]for j in range(N+1)]

for i in range(1,N+1):

    q = queue.Queue()
    q.put(i)
    depth = [queue.Queue() for i in range(N+1)]
    d = 0
    depth[d].put(i)
    checked = []
    count = 0
    for j in range(N+100000):
        if depth[d].qsize() == 0:
            break
        #k = q.get()
        k=depth[d].get()

        
        if k in checked :
            dist[i][k] = min(dist[i][k], d)
            if depth[d].qsize() == 0:
                d += 1
        else:
            
            dist[i][k] = min(dist[i][k], d)
            checked.append(k)
            if k!=1:
                q.put(k-1)
                depth[d+1].put(k-1)
            if k!=N:

                q.put(k+1)
                depth[d+1].put(k+1)
            if k==X:
                q.put(Y)
                depth[d+1].put(Y)
            if k==Y:
                q.put(X)
                depth[d+1].put(X)
            if depth[d].qsize() == 0:

                d += 1


for i in range(N+1):
    for j in range(N+1):
        dist[i][j] = min(dist[i][j], dist[j][i])

ans =[0 for i in range(N+1)]
for i in range(N+1):
    for j in range(i+1,N+1):
        ans[dist[i][j]] += 1
for i in range(1,N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n,x,y = map(int, input().split())
x -= 1
y -= 1
ans = [0]*n
dp = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
         ans[min(abs(i-j),(abs(i-x)+abs(j-y)+1),(abs(i-y)+abs(j-x)+1))]+=1
for k in range(1,n):
    print(ans[k]//2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = list(map(int, input().split(' ')))
X -= 1
Y -= 1
dist_map = {}

def search(origin):
  dist = []
  # X, Yの辺がない場合
  for i in range(N):
    dist.append(abs(origin - i))
  # X, Yの辺がある場合
  if dist[X] < dist[Y]:
    dist[Y] = dist[X] + 1
  elif dist[Y] < dist[X]:
    dist[X] = dist[Y] + 1
  for i in range(N):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  for i in reversed(range(N)):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  #print(*dist)
  return dist


for i in range(N):
  dist_map[i] = search(i)

#print(N)
count = [0 for i in range(N)]
for i in range(N):
  #print('i='+str(i))
  #dist = dist_map[i]
  #print(*dist)
  dist = dist_map[i]
  for dis in dist:
    count[dis] += 1
for i in range(1, N):
  print(count[i]//2)

Submission status: Time Limit Exceeded

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,x,y=INTM()
    z=y-x
    sc=y-x-1
    loop=y-x+1
    maxl=(n)-(y-x)
    for i in range(1,n):
        ct=0
        if ct==0:
            for j in range(1,n):
                if j+i<=x or j>=y:
                    if j+i<=n:
                        ct+=1
                else:
                    if j<=x:
                        if j+i+sc<=n:
                            ct+=1
                        temp=i-(x-j)
                        if temp>=2:
                            if loop>temp*2:
                                ct+=2
                            elif loop==temp*2:
                                ct+=1
                        else:
                            ct+=1
                        
                    else:
                        lpmin=min(y-j,+(j-x+1))
                        if lpmin==j-x+1:
                            if lpmin==y-j:
                                if lpmin+(n-y)>=i:
                                    ct+=1
                            else:
                                if lpmin>i:
                                    ct+=1
                                elif lpmin==i:
                                    ct+=2
                                else:
                                    if lpmin+(n-y)>=i:
                                        ct+=1
                                    
                                    if loop>i*2:
                                        ct+=2
                                    elif loop==i*2:
                                        ct+=1
                        else:
                            if lpmin+(n-y)>=i:
                                ct+=1
                #print(ct)
            print(ct)        
        else:
            print(ct)
                
        
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())

distances = []
for ind1 in range(1,n+1):
    for ind2 in range(ind1+1,n+1):
        cur_dist = min(ind2-ind1, abs(x-ind1)+abs(y-ind2)+1)
        # print(ind1,ind2,cur_dist)
        distances.append(cur_dist)
    
# print(distances)
for k in range(1,n):
    print(len([x for x in distances if x == k]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
 
 
def main():
    # n, x, y = 7, 3, 7
    n, x, y = [int(s) for s in sys.stdin.readline().strip().split()]
    score = {i: 0 for i in range(1, n)}
    total_pair = set()
 
    def bfs(start):
        seen = set()
        heap = [(0, start)]
        while heap:
            dist, cur = heappop(heap)
            pair = (min(start, cur), max(start, cur))
            if pair in seen:
                continue
            seen.add(pair)
            if dist > 0:
                if pair not in total_pair:
                    score[dist] += 1
                    total_pair.add(pair)
 
            if cur < n-1:
                heappush(heap, (dist+1, cur+1))
            if cur > 0:
                heappush(heap, (dist+1, cur-1))
            if cur == x-1:
                heappush(heap, (dist+1, y-1))
            if cur == y-1:
                heappush(heap, (dist+1, x-1))
 
    for i in range(n-1):
        bfs(i)
    for i in range(1, n):
        print(score[i])
 
main()

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
ans=[0 for _ in range(n+1)]
d=[]
for i in range(n+1):
    d.append([abs(i-j) for j in range(n+1)])
#    print(d[i])
d[x][y]=1
d[y][x]=1

for i in range(1,n+1):
    for j in range(i+1,n+1):
        d[i][j]=min(d[i][j],d[i][x]+d[x][y]+d[y][j],d[i][y]+d[y][x]+d[x][j])
        ans[d[i][j]]+=1

for i in range(1,n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = [int(x) for x in input().split()]

list_adjlist = []
for i in range(N):
    if i == 0:
        list_adjlist.append([i+1])
    elif i == N-1:
        list_adjlist.append([i-1])
    else:
        list_adjlist.append([i-1, i+1])

list_adjlist[X-1].append(Y-1)
list_adjlist[Y-1].insert(0, X-1)

def FIFO(list1, node):
    if node != None:
        list1.append(node)
        return None
    return list1.pop(0)
def getShortestDistance(list_adjlist, initnode):
    # 既にスタックに入れた点かどうかをチェックするリストを初期化
    list_check = [False] * len(list_adjlist)
    #list_Dを初期化
    list_D = [-1 for _ in range(len(list_adjlist))]
    #始点の距離=0
    list_D[initnode] = 0
    #list_Tを初期化
    list_T = [-1 for _ in range(len(list_adjlist))]
    #FIFOキューを初期化
    list_FIFO = []
    # 始点の名前をFIFOキューに入れる
    FIFO(list_FIFO, initnode)
    list_T[initnode]
    list_check[initnode] = True
    #FIFOキューが空になるまで探索（ループ）
    while(len(list_FIFO)):
        v = FIFO(list_FIFO, None)
        for i in range(len(list_adjlist[v])):
            child = list_adjlist[v][i]
            if list_check[child] == False:
                FIFO(list_FIFO, child)
                list_check[child] = True
                list_T[child] = v
                list_D[child] = list_D[v] + 1
            else:
                pass
    #最短距離と最短経路を返す
    return list_D, list_T

anslist = [0 for _ in range(N)]

for i in range(N):
    list_D, list_T = getShortestDistance(list_adjlist, i)
    for k in range(N):
        anslist[k] += list_D.count(k+1)

for ans in [x//2 for x in anslist[:-1]]:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, x, y = list(map(int, input().split()))
INF = 10 ** 100
adj_mtx = [ [INF] * (N+1) for _ in range(N+1) ]

for i in range(1, N+1):
  if i != N:
    adj_mtx[i][i] = 0
    adj_mtx[i][i+1] = 1
    adj_mtx[i+1][i] = 1
adj_mtx[x][y] = 1
adj_mtx[y][x] = 1

for k in range(1, N+1):
  for i in range(1, N+1):
    for j in range(1, N+1):
      adj_mtx[i][j] = min(adj_mtx[i][j], adj_mtx[i][k] + adj_mtx[k][j])

for i in range(1, N):
  print(sum([ r.count(i) for r in adj_mtx ]) // 2)

Submission status: Time Limit Exceeded

Solution code:
# D
import numpy as np
N, X, Y = map(int, input().split())

X = X - 1
Y = Y - 1

x = np.zeros((N,N),dtype=np.int)
for i in range(N):
    x[i,i:] = np.array(range(N-i))
y = np.zeros((N,N),dtype=np.int)
for i in range(0, N):
    for j in range(i+1, N):
        y[i, j] = abs(i-X) + abs(j-Y) + 1

ans = np.minimum(x, y)

count = [0]*(N)
for i in ans.reshape(-1):
    count[i]+=1

for i in count[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int, input().split())

def bubble_sort(arr):
    change = True
    while change:
        change = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                change = True
    return arr

def put_item(table, item):
    for i in range(0, len(table)):
        if table[i][0] == item:
            table[i][1] = table[i][1] + 1
            return 
    table.append([item, 1])


def histogram(data):
    result = []
    for i in range(0, len(data)):
        put_item(result, data[i])
    return result
  
def dist(a,b):
	return min(abs(b-a),1+abs(a-X)+abs(b-Y),1+abs(b-X)+abs(a-Y))
  
List=[]
for i in range(1,N):
    for j in range(i+1,N+1):
        List.append(dist(i,j))
  
maxi = len(histogram(bubble_sort(List)))
for i in range(N-1):
    if i+1 <= maxi:
        print(histogram(bubble_sort(List))[i][1])
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop


def main():
    # n, x, y = 7, 3, 7
    n, x, y = [int(s) for s in sys.stdin.readline().strip().split()]
    score = {i: 0 for i in range(1, n)}
    total_pair = set()

    def bfs(start):
        seen = set()
        heap = [(0, start)]
        while heap:
            dist, cur = heappop(heap)
            pair = (min(start, cur), max(start, cur))
            if pair in seen:
                continue
            seen.add(pair)
            if dist > 0:
                if pair not in total_pair:
                    score[dist] += 1
                    total_pair.add(pair)

            if cur < n-1:
                heappush(heap, (dist+1, cur+1))
            if cur > 0:
                heappush(heap, (dist+1, cur-1))
            if cur == x-1:
                heappush(heap, (dist+1, y-1))
            if cur == y-1:
                heappush(heap, (dist+1, x-1))

    for i in range(n-1):
        bfs(i)
    for i in range(1, n):
        print(score[i])

main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
N, X, Y = map(int, input().split())
# 距離行列の生成
dist_matrix = [[0] * (N) for _ in range(N)] 
for i in range(N):
    if i > 0:
        dist_matrix[i][i-1] = 1
    dist_matrix[i][i] = 0
dist_matrix[X-1][Y-1] = 1

graph = csr_matrix(dist_matrix)
# ワーシャルフロイド
dist_matrix = dijkstra(csgraph=graph, directed=False)
dic = {}
for i in range(N):
    for j in range(i, N):
        item = dist_matrix[i][j]
        if item not in dic:
            dic[item] = 1
        else:
            dic[item] += 1
for i in range(1, N):
    print(dic.get(i, 0))

Submission status: Time Limit Exceeded

Solution code:
def get_target_min_index(min_index, distance, unsearched_nodes):
  start = 0
  while True:
    index = distance.index(min_index, start)
    found = index in unsearched_nodes
    if found:
      return index
    else:
      start = index + 1


n, x, y = map(int, input().split())

graph = [[0] * n for i in range(n)]
ans = [0] * n

for i in range(n - 1):
  graph[i][i + 1] = 1
  graph[i + 1][i] = 1

graph[x - 1][y - 1] = 1
graph[y - 1][x - 1] = 1
# print(graph)

for j in range(n - 1):
  node_num = len(graph)

  unsearched_nodes = list(range(node_num))
  distance = [float('inf')] * node_num
  previous_nodes = [-1] * node_num
  distance[j] = 0 

  while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
      posible_min_distance = float('inf')
      for node_index in unsearched_nodes:
          if posible_min_distance > distance[node_index]: 
              posible_min_distance = distance[node_index]
      target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes)
      unsearched_nodes.remove(target_min_index)

      target_edge = graph[target_min_index]
      for index, route_dis in enumerate(target_edge):
          if route_dis != 0:
              if distance[index] > (distance[ target_min_index] + route_dis):
                  distance[index] = distance[ target_min_index] + route_dis
                  previous_nodes[index] =  target_min_index


  del distance[:(j + 1)]

  for i in range(n - 1):
    ans[i] += distance.count(i + 1)

  # print(distance)
# print(ans)

for i in range(len(ans) - 1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int,input().split())
X -= 1
Y -= 1

nallpath = N*(N-1)//2
distance = [0] * nallpath

indx = 0
for j in range(N-1):
    for i in range(j+1,N):
        if i <= X:
            distance[indx] = i - j
        elif j >= Y:
            distance[indx] = i - j
        elif j <= X and Y<= i:
            distance[indx] = i - j - (Y-X-1)
        elif  X <= j < i <= Y:
            distance[indx] = min(i-j, (j-X)+(Y-i)+1)
        elif j <= X and X < i <= Y:
            distance[indx] = (X-j) + min(i-X, Y-i+1)
        else:
            distance[indx] = (i-Y) + min(Y-j, j-X+1)
        indx += 1
for i in range(N-1):print(distance.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
l=[]
for i in range(1,N):
  for j in range(i+1,N+1):
    if abs(X-i)+1+abs(Y-j)>j-i:
      l.append(j-i)
    else:
      l.append(abs(X-i)+1+abs(Y-j))
for i in range(1,N):
  print(l.count(i))