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:
from collections import deque
def bfs(start):
    global count
    d = [float('inf') for i in range(N)]
    d[start] = 0
    que = deque()
    que.append(start)
    alr = [start]
    while que:
        q = que.popleft()
        c = d[q]
        for i in path[q]:
            if i not in alr:
                que.append(i)
                alr.append(i)
                d[i] = c+1
    for i in range(start+1,N):
        count[d[i]-1] += 1

N,X,Y = map(int,input().split())
path = [[] for i in range(N)]
path[0] = [1]
path[N-1] = [N-2]
for i in range(1,N-1):
    path[i] = [i-1,i+1]
path[X-1].append(Y-1)
path[Y-1].append(X-1)

count = [0 for i in range(N-1)]
for i in range(N-1):
    bfs(i)
for i in range(N-1):
    print(count[i])

Submission status: Time Limit Exceeded

Solution code:
[N,X,Y] = [int(s) for s in input().rstrip().split(' ')]
L = [] #L[i][j]はi,j間の最短距離(i<=j)
for i in range(N):
  L.append([10**4 for j in range(N-i)])
for i in range(N):
  L[i][0] = 0
  if i < N-1:
    L[i][1] = 1
L[X-1][Y-X] = 1
for k in range(1,N):
  a = 0
  for i in range(N):
    for j in range(N-i):
      if L[i][j] == k:
        a += 1
      elif L[i][j] > k:
        for p in range(N):
          if p < i:
            if L[p][i-p] + L[p][i+j-p] < L[i][j]:
              L[i][j] = L[p][i-p] + L[p][i+j-p]
          elif p < i+j:
            if L[i][p-i] + L[p][i+j-p] < L[i][j]:
              L[i][j] = L[i][p-i] + L[p][i+j-p]
          else:
            if L[i][p-i] + L[i+j][p-i-j] < L[i][j]:
              L[i][j] = L[i][p-i] + L[i+j][p-i-j]
  print(a)

Submission status: Time Limit Exceeded

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

X -= 1
Y -= 1

print(N)

def disdance(i, j):
    if i <= X and j >= Y:
        return X - i + j - Y + 1
    elif i >= X and j <= Y:
        return min(j - i, i - X + Y - j + 1)
    elif i >= X and j >= Y:
        return min(j - i, i - X + j - Y + 1)
    elif i <= X and j <= Y:
        return min(j - i, X - i + Y - j + 1)

for k in range(2, N):
    count = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            count += (disdance(i, j) == k)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split(' '))
d_list = []
for i in range(1, n):
    for j in range(i + 1, n + 1):
        if j <= x or y <= i:  # ok
            d_list.append(j - i)
        elif i <= x and x < j <= y:
            d_list.append(min(j - i, x - i + y - j + 1))
        elif i <= x and j > y: # ここまでok
            d_list.append(x - i + j - y + 1)
        elif x < i < y and j < y:
            d_list.append(min(j - i, i - x + y - j + 1))
        elif x < i < y and j >= y:
            d_list.append(min(j - i, i - x + j - y + 1))
for i in range(1, n):
    print(d_list.count(i))

Submission status: Time Limit Exceeded

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

cnt = [0]*N

for i in range(1, N):  # 1~N-1
    for j in range(i+1, N+1):  # 2~N
        p = []
        p += [j - i]
        if i <= X:
            if j >= Y:
                p += [X-i + j-Y + 1]
            else:
                p += [X-i + Y-j + 1]
        else:
            if j >= Y:
                p += [i-X + j-Y + 1]
            else:
                p += [i-X + Y-j + 1]
        cnt[min(p)] += 1


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def count_pair(k):
    cnt = 0
    for i in range(1, N+1):
        visited = [-1]*(N+1)
        visited[i] = 0
        s = 0
        q = deque([[i]])
        while s != k:
            p = []
            A = q.popleft()
            for a in A:
                if a == X and visited[Y] == -1:
                    p.append(Y)
                    visited[Y] = 0
                if a == Y and visited[X] == -1:
                    p.append(X)
                    visited[X] = 0
                if a+1 <=N and visited[a+1] == -1:
                    p.append(a+1)
                    visited[a+1] = 0
                if a-1 >= 1 and visited[a-1] == -1:
                    p.append(a-1)
                    visited[a-1] = 0
            q.append(p)
            s += 1
        r = q[0]
        t = 0
        for j in range(len(r)):
            if r[j] > i:
                t += 1
        cnt += t
    return cnt

N, X, Y = map(int, input().split())
for k in range(1, N):
    print (count_pair(k))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

    node = [[[] for _ in range(N)] for _ in range(N)]
    used = [[False] * N for _ in range(N)]

    for i in range(N):
        node[i][0].append(i)
        used[i][i] = True


    for k in range(1,N):
        ans = 0
        for i in range(N):
            for x in node[i][k-1]:
                if x == X-1 and (not used[i][Y -1]):
                    node[i][k].append(Y-1)
                    used[i][Y-1] = True
                    ans += 1

                if x == Y-1 and (not used[i][X -1]):
                    node[i][k].append(X-1)
                    used[i][X-1] = True
                    ans += 1

                if (x - 1 >= 0 )and (not used[i][x - 1]):
                    node[i][k].append(x - 1)
                    used[i][x - 1] = True
                    ans += 1

                if (x + 1 < N) and (not used[i][x + 1]):
                    node[i][k].append(x + 1)
                    used[i][x + 1] = True
                    ans += 1
        print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n,x,y = map(int,input().split())
graph = [[0 for i in range(n)]for j in range(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

ans = floyd_warshall(graph )

for i in range(1,n):
    print(int(np.count_nonzero(ans == i)/2))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np
n, x, y = map(int, input().split())
ans = [0] * (n - 1)
table = []
for i in range(n):
    l = [0] * n
    if i + 1 < n:
        l[i + 1] = 1
    if i - 1 > -1:
        l[i - 1] = 1
    if i == x - 1:
        l[y - 1] = 1
    if i == y - 1:
        l[x - 1] = 1
    table.append(l)
a = shortest_path(np.array(table))
a = a.flatten().tolist()
for i in range(n - 1):
    ans[i] += a.count(i + 1)
ans = list(map(lambda x: x // 2, ans))
ans[-1] = 0
for i in range(n - 1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def resolve():
    N, X, Y = map(int, input().split())
    graph = np.zeros((N + 1, N + 1), dtype=np.int64)

    for i in range(1, N):
        graph[i, i+1] += 1
        graph[i+1, i] += 1
    graph[X, Y] = 1
    graph[Y, X] = 1

    dist = dijkstra(csgraph=csr_matrix(graph)).astype(np.int64)
    dist_U = np.triu(dist[1:, 1:])
    ans = []
    for i in range(1, N):
        cnt = sum(np.where(dist_U==i))
        ans.append(len(cnt))

    for a in ans:
        print(a)
        
if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

g = Dijkstra()
n, x, y = [int(i) for i in input().split()]

for i in range(n-1):
    g.add(i+1, i+2, 1)
g.add(x, y, 1)

l = [0 for _ in range(n)]
flag = 0
for i in range(n):
    flag += 1
    for k, v in dict(g.Dijkstra_search(i+1)[0]).items():
        if k > flag:
            l[v] += 1
#         print(k, v)
# print(l)

l.pop(0)
for i in l:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

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

cost = [[float("inf") for i in range(n)] for i in range(n)] 
for i in range(n - 1):
    cost[i][i + 1] = 1
    cost[i + 1][i] = 1
cost[x - 1][y - 1] = 1
cost[y - 1][x - 1] = 1

dist = []
for i in  range(n):
    dist.append(dijkstra(i, n, n, cost))

comb = [[i,j] for i in range(0, n + 1) for j in range(i+1, n) ]\

ans = [0] * n

for c in comb:
    ans[dist[c[0]][c[1]]] += 1

for k in ans[1:]:
    print(k)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n,x,y = map(int,input().split())
to = [[] for _ in range(n)]
for i in range(n-1):
    to[i].append(i+1)
    to[i+1].append(i)
x -= 1
y -= 1
to[x].append(y)
to[y].append(x)

ans = [0]*(n-1)
d = {}
for i in range(n-1):
    Q = deque()
    Q.append((i,-1,0))
    flag = [False]*n
    flag[i] = True
    while Q:
        cur,prev,dist = Q.popleft()
        for nxt in to[cur]:
            if nxt == prev: continue
            if flag[nxt]: continue
            flag[nxt] = True
            if (i,nxt) not in d: ans[dist] += 1
            Q.append((nxt,cur,dist+1))
            d[(i,nxt)] = 1
            d[(nxt,i)] = 1

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

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] = [int(s) for s in input().rstrip().split(' ')]
L = [] #L[i][j]はi,j間の最短距離(i<=j)
for i in range(N):
  L.append([10**4 for j in range(N-i)])
for i in range(N):
  L[i][0] = 0
  if i < N-1:
    L[i][1] = 1
L[X-1][Y-X] = 1
for k in range(1,N):
  a = 0
  for i in range(N):
    for j in range(N-i):
      if L[i][j] == k:
        a += 1
      elif L[i][j] > k:
        for p in range(N):
          if p < i:
              L[i][j] = min(L[i][j],L[p][i-p] + L[p][i+j-p])
          elif p < i+j:
              L[i][j] = min(L[i][j],L[i][p-i] + L[p][i+j-p])
          else:
              L[i][j] = min(L[i][j],L[i][p-i] + L[i+j][p-i-j])
  print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

N, X, Y = map(int, input().split())
field = [[] for _ in range(N)]
for i in range(N-1):
    field[i].append(i+1)
    field[i+1].append(i)
field[X-1].append(Y-1)
field[Y-1].append(X-1)

counter = [0]*(N-1)


def bfs(current, destination, counter, paper):
    next_place = [current]
    while True:
        nn_place = []
        for current_place in next_place:
            if current_place == destination:
                return counter
            else:
                for des in field[current_place]:
                    if paper[des] == False:
                        nn_place.append(des)
                        paper[des] = True
        counter += 1
        next_place = nn_place


for i in range(N):
    for j in range(N):
        if i == j:
            continue
        else:
            paper = [False for i in range(N)]
            step = bfs(i, j, 0, paper)
            counter[step-1] += 1

answer = []
for i in range(N-1):
    answer.append(counter[i]//2)

for el in answer:
    print(str(el))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,X,Y = inputMap()
	g2 = Graph()

	for i in range(N):
		if i == 0:
			continue

		g2.add_edge(i-1, i, 1)
		if i >= X:
			g2.add_edge(i, i-1, 1)

	g2.add_edge(X-1, Y-1, 1)
	#g2.add_edge(Y-1, X-1, 1)

	for i in range(1,N):
		if i == 1:
			print(N)
			continue
		if i == N-1:
			print(0)
			continue

		ans2 = 0
		ans = []
		for ii in range(N):
			d2 = Dijkstra(g2, ii)
			for jj in range(N):
				if ii >= jj:
					continue
				tmp2 = d2.shortest_distance(jj)

				if tmp2 == i:
					###if (jj,ii) in ans:
						###continue
					#print("{} {}".format(ii+1,jj+1))
					ans2 += 1
					ans.append((ii,jj))
		print(ans2)
		#print("{} {}".format(ans,ans2))





#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
dist = [0]*N
for i in range(N):
    for k in range(i,N):
        if i == X - 1 and k == Y - 1:
            dist[1] += 1
            continue
        if X - 1 <= k <= Y - 1 and i <= X - 1:
            tmp = min(k-i,(X-1)-i+1+(Y-1-k))
            dist[tmp] += 1
            continue
        if X - 1 < i < Y - 1 and k >= Y - 1:
            tmp = min(k-i,i-(X-1)+1+k-(Y-1))
            dist[tmp] += 1
            continue
        if X - 1 <= k <= Y - 1 and X - 1 <= i <= Y - 1:
            tmp = min(k-i,i-(X-1)+1+(Y-1-k))
            dist[tmp] += 1
            continue
        if i <= X - 1 and k >= Y - 1:
            dist[k-i-(Y-X-1)] += 1
            continue
        dist[k-i] += 1
for i in range(1,N):
    print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, X, Y = map(int, input().split())
d = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    for j in range(i+1, N):
        d[i][j] = d[i][j-1] + 1
X -= 1
Y -= 1
for i in range(N-1):
    for j in range(i + 1, N):
        diff = abs(X - i) + abs(Y - j) + 1
        if diff < d[i][j]:
            d[i][j] = diff
#print(d)
ans = defaultdict(int)
for i in range(N-1):
    for j in range(i + 1, N):
        ans[d[i][j]] += 1
for k in range(1, N):
    print(ans[k])

Submission status: Time Limit Exceeded

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

def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = [[float("inf")]*N for i in range(N)]
for i in range(N-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
    d[i][i] = 0

d[X-1][Y-1] = 1
d[Y-1][X-1] = 1

warshall_floyd(d, N)
c = collections.Counter()
for i in range(N):
    c.update(d[i])

for i in range(N-1):
    print(int(c[i+1] / 2))

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
cost=[[] for _ in range(N)]

for i in range(N-1):
  cost[i].append(i+1)
for j in range(1,N):
  cost[j].append(j-1)

cost[X-1].append(Y-1)
cost[Y-1].append(X-1)
#print(cost)

def bfs(v):
    d=[-1]*N
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in cost[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
        #print(d,q)
    return d

d=dict()
for m in range(N):
  tmp=bfs(m)
  #print(tmp)
  for num in tmp:
    if num not in d:
      d[num]=1
    else:
      d[num] += 1
#print(d)

for z in range(1,N):
  if z in d:
    print(d[z]//2)
  else:
    print(0)

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
  
List=[]
for i in range(1,N):
    for j in range(i+1,N+1):
        if i<X and j <X:
           List.append(j-i)
        elif i>Y and j>Y:
            List.append(j-i)
        else:
            if i<X and j>Y:
                List.append(X+j-i-Y+1)
            else:
                if i<X and X<=j<=Y:
                    List.append(min(j-i,X-i+Y-j+1))
                else:
                    if X<=i<=Y and X<=j<=Y:
                        List.append(min(j-i,i-X+Y-j+1))
                    else:
                        List.append(min(j-i,i-X+j-Y+1))
  
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:
from collections import Counter, deque

class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, start, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [float('inf') for i in range(self.N)]
        d[start] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True, d
        return False, d
      
n, x, y = [int(i) for i in input().split()]

bf = BellmanFord(n)

for i in range(n-1):
  bf.add(i, i+1, 1)
bf.add(x-1, y-1, 1)

c = Counter([])
for i in range(n):
  c.update(bf.BellmanFord_search(i))

for i in range(1, n):
  print(c[i]//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
 
def flatten(array):
    return [item for sublist in array for item in sublist]

n, x, y = map(int, input().split())
c = [[10**4]*n for i in range(n)]
for i in range(n):
    c[i-1][i] = 1
    c[i][i-1] = 1
c[-1][0] = 10**4
c[0][-1] = 10**4
c[x-1][y-1] = 1
c[y-1][x-1] = 1
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
            c[j][j]=0

p = sorted(Counter(flatten(c)).items(), key=lambda x: x[0])[1:]
t = 0
for _, cnt in p:
    print(cnt // 2)
for _ in range(n-1-len(p)):
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
n, x, y = map(int, input().split())
x -= 1
y -= 1
GRAPH = [[0]*n for _ in range(n)]
for i in range(n-1):
    GRAPH[i][i+1] = GRAPH[i+1][i] = 1
GRAPH[x][y] = GRAPH[y][x] = 1
G = np.array(GRAPH)
sp = shortest_path(G)

ans = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        path = int(sp[i][j])-1
        ans[path] += 1
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

for i in range(1, N + 1):
    for j in range(i + 1, N + 1):
        naive_length = j - i
        short_cut_length = []
        short_cut_length.append(abs(X - i) + abs(Y - j) + 1)
        short_cut_length.append(abs(X - j) + abs(Y - i) + 1)
        min_length = min([naive_length] + short_cut_length)
        num_distances[min_length] += 1

for d in num_distances[1:]:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import collections


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

route = np.array([[0 for _ in range(n)]for _ in range(n)])
for i in range(n-1):
	route[i][i+1] = 1

route[x-1][y-1] = 1
route[y-1][x-1] = 1

#res = shortest_path(route, unweighted=False,directed=False)
res = dijkstra(route, directed=False)

tmp = []
for i in range(n):
	tmp.append(collections.Counter(res[i][i:]))


ans = [0 for _ in range(n)]
for i in range(n):
	for k in range(1,n):
		ans[k] += tmp[i][k]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

d = [[sys.maxsize for _ in range(N)] for _ in range(N)]

for i in range(N):
  d[i][i] = 0
  if i == N-1:
    pass
  else:
    d[i][i+1] = 1
    d[i+1][i] = 1

d[X-1][Y-1] = 1
d[Y-1][X-1] = 1

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

answer = [0 for _ in range(N-1)]

for h in range(N):
  for i in range(h+1, N):
    if h != i:
      answer[d[h][i]-1] += 1

for k in range(N-1):
  print(answer[k])

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n, x, y = map(int, input().split())
#    odd = True
#    if (x+y)%2 == 0:
#        odd = False
#    for q in range(1, n):
#        ans = 0
#        for i in range(1, n):
#            if i <= x:
#                if i + q <= x:
#                    ans += 1
#                else:
#                    buf = i + q - x
#                    if 1 < buf and buf <= n-y + 1:
#                        ans += 1
#                    if buf <= (y-x+1)//2:
#                        if buf == (y-x+1)//2:
#                            if odd:
#                                ans += 2
#                            else:
#                                ans += 1
#                        else:
#                            ans += 2
#            elif i <= y:
#                if q <= (y-x + 1)//2:
    x -= 1
    y -= 1
    ans = [[0]*n for _ in range(n)]
    t = [[i+1, i-1] for i in range(n)]
    t[x].append(y)
    t[y].append(x)
#    print(t)
    q = queue.Queue()
    for i in range(n):
        f = [True]*n
        f[i] = False
        q.put([i, 0])
        while not q.empty():
            a, b = q.get()
            for v in t[a]:
                if 0 < v and v < n:
                    if f[v]:
                        if i < v:
                            ans[i][b + 1] += 1
                        f[v] = False
                        q.put([v, b+1])
    for i in range(1, n):
        p = 0
        for j in range(n):
            p += ans[j][i]
        print(p)
if __name__ == "__main__":
    main()