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:
n, x, y = map(int, input().split())
array = []

for i in range(1, n+1):
    for j in range(i+2, n+1):
        array.append(min(j-i, abs(x-i)+1+abs(y-j), abs(y-i)+1+abs(x-j)))

print(n)
for k in range(2, n):
    print(array.count(k))

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
#a<b
def dis(a,b):
    return min (b-a,abs(a-x)+1+abs(b-y))

for k in range(1,n):
  count=0
  #i<j
  for i in range(1,n):
    for j in range(i+1,n+1):
      if dis(i,j)==k:
        count+=1
  print(count)

Submission status: Time Limit Exceeded

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

for i in range(1, n+1):
    for j in range(i+1, n+1):
        array.append(min(j-i, abs(x-i)+1+abs(y-j), abs(y-i)+1+abs(x-j)))

for k in range(1, n):
    print(array.count(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())
g = dict()
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1, i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)
# print(g)
distance = [0]*(n-1)
# 1番ノードから各ノードへの最短距離を求めていく.
for i in range(n):
    queue = deque()
    visited = [0]*n
    # まず処理される予定のノードが格納されているqueueに最初のノードを格納する
    queue.append(i)
    while queue:
        target = queue.popleft()
        for j in g[target]:
                if visited[j] == 0 or visited[j] > visited[target] + 1:
                    visited[j] = visited[target] + 1
                    queue.append(j)
    for k in range(len(visited)):
        if k > i:
            if visited[k] >= 1:
                distance[visited[k]-1] += 1
    # print(f"{i}番ノードからの各ノードへの最短距離は{visited}である")
for l in distance:
    print(l)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, x, y = map(int, input().split())
g = dict()
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1, i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)
distance = [0]*(n-1)
for i in range(n):
    queue = deque()
    visited = [0]*n
    queue.append(i)
    while queue:
        target = queue.popleft()
        for j in g[target]:
                if visited[j] == 0 or visited[j] > visited[target] + 1:
                    visited[j] = visited[target] + 1
                    queue.append(j)
    for k in range(len(visited)):
        if k > i:
            if visited[k] >= 1:
                distance[visited[k]-1] += 1
for l in distance:
    print(l)

Submission status: Time Limit Exceeded

Solution code:
import heapq


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

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

    D[s]=0

    H=[(0,s)]
    heapq.heapify(H)

    while len(H)>=1:
        u=heapq.heappop(H)[1]
        if color[u]=="black":continue
        color[u]="black"

        V=[(i,j) for i,j in M[u] if color[j]!="black"]
        while len(V)!=0:
            for i,j in V:
                if D[u]+i<D[j]:
                    D[j]=D[u]+i
                    color[j]="gray"
                    heapq.heappush(H,(D[j],j))
            break
    return D


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

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

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    N, X, Y = map(int, input().split())
    dp = [[float("inf") for i in range(N)] for j in range(N)]
    heap = []
    heapq.heapify(heap)
    for i in range(N - 1):
        dp[i][i + 1] = 1
        dp[i + 1][i] = 1
        heapq.heappush(heap, (1, i, i + 1))
    dp[X - 1][Y - 1] = 1
    dp[Y - 1][X - 1] = 1
    heapq.heappush(heap, (1, X - 1, Y - 1))
    while True:
        if len(heap) == 0:
            break
        else:
            cost, a, b = heapq.heappop(heap)
            # xを動かす
            for i in [-1, 1]:
                if (a + i) < 0 or (a + i) >= N or (a + i) == b:
                    continue
                if dp[a+i][b] != float("inf"):
                    continue
 
                dp[a + i][b] = (cost + dp[a][a + i])
                dp[b][a + i] = (cost + dp[a][a + i])
                heapq.heappush(heap, (dp[a + i][b], a + i, b))
            for i in [-1, 1]:
                if (b + i) < 0 or (b + i) >= N or (b + i) == a:
                    continue
                if dp[a][b + i] != float("inf"):
                    continue
                dp[a][b + i] = (cost + dp[b][b + i])
                dp[b + i][a] = (cost + dp[b][b + i])
                heapq.heappush(heap, (dp[b + i][a], a, b + i))
 
    ans = [0 for i in range(N - 1)]
    for i in range(N):
        for j in range(N):
            if dp[i][j] == float("inf"):
                pass
            else:
                ans[dp[i][j] - 1] += 1
    for i in range(N - 1):
        print(ans[i] // 2)
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

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


for i in range(1, N+1):
  for j in range(i, N+1):
    dist[i][j] = min(abs(X-i) + 1 + abs(Y-j), abs(X-j)+1+abs(Y-i), abs(i-j))
    distnum[dist[i][j]] += 1

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

Submission status: Time Limit Exceeded

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

ans = [0] * (N - 1)
for i in range(N):
    for j in range(i + 1, N):
        dist = min(abs(i - j), abs((X - 1) - i) + abs((Y - 1) - j) + 1, abs((Y - 1) - i) + abs((X - 1) - j) + 1)
        ans[dist - 1] += 1
        # print("i:{}, j:{}, dist:{}".format(i, j, dist))
for k in ans:
    print(k)

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

N, X, Y = map(int,input().split())
l = [[0]*(N) for _ in range(N)]
for i in range(N-1):
    l[i][i+1] = 1
    l[i+1][i] = 1
l[X-1][Y-1] = 1
l[Y-1][X-1] = 1
csr = csr_matrix(l)
step = np.array(np.ravel(floyd_warshall(csr, unweighted=True)), dtype=int)
memo = np.bincount(step)
ma = np.max(step)
for i in range(1,ma+1):
    print(memo[i]//2)
for i in range(ma+1, N):
    print(0)

Submission status: Time Limit Exceeded

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

inf = 1000000000
edges = [[inf] * n for _ in range(n)]
for i in range(n - 1):
    edges[i][i + 1] = 1
    edges[i + 1][i] = 1

edges[x - 1][y - 1] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            edges[i][j] = min(edges[i][j], edges[i][k] + edges[k][j])

cnts = [0] * (n - 1)
for i in range(n - 1):
    for j in range(i + 1, n):
        cnts[edges[i][j] - 1] += 1

for x in cnts:
    print(x)

Submission status: Time Limit Exceeded

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

for i in range(1,n):
    for j in range(i+1,n+1):
        dist.append(min(j - i,abs(i-x) + 1 + abs(y-j),abs(y-i)+ 1 + abs(j-x)))

for i in range(1,n):
    print(dist.count(i))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def breadth_first_search(start):
    work_q = deque([])
    visited = set()
    work_q.append(start)
    visited.add(start)
    cnt_array = [0] * (n+1)
    while work_q:
        here = work_q.popleft()
        for i in edge[here]:
            if i not in visited:
                work_q.append(i)
                visited.add(i)
                cnt_array[i] = cnt_array[here] + 1
    return cnt_array

n,x,y = map(int,input().split())
edge = []
for i in range(n+1):
    edge.append([])
for i in range(1,n+1):
    if i != n:
        edge[i].append(i+1)
    if i != 1:
        edge[i].append(i-1)
edge[x].append(y)
edge[y].append(x)

ans = [0] * n
for i in range(1, n+1):
    a = breadth_first_search(i)
    for j in range(len(a)):
        ans[a[j]] += 1
for i in range(1,n):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

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

for i in range(1,n):
    for j in range(i+1,n+1):
        dist.append(min(j - i,abs(i-x) + 1 + abs(y-j)))
for i in range(1,n):
    print(dist.count(i))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, x, y = map(int, input().split())
x -= 1
y -= 1
list1 = [0] * (n * n)

for i in range(n):
    for j in range(n):
        if list1[n * j + i]  != 0:
            continue
        
        list1[n * i + j] = min([abs(j - i), abs(x - i) + 1 + abs(j - y), abs(y - i) + 1 + abs(x - j)])
        
#list2 = list(itertools.chain.from_iterable(list1))

for k in range(1,n):
    print(list1.count(k))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

pos = [i for i in range(1,N+1)]
ways = list(itertools.combinations(pos,2))

dist_l = [min(abs(i-j), abs(i - X) + 1 + abs(Y - j)) for i,j in ways]

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, x, y = map(int, input().split())
x -= 1
y -= 1
list1 = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        if list1[j][i] != 0:
            continue
        
        num = min([abs(j - i), abs(x - i) + 1 + abs(j - y), abs(y - i) + 1 + abs(x - j)])
        list1[i][j] = num

list2 = list(itertools.chain.from_iterable(list1))

for k in range(1,n):
    print(list2.count(k))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
count = [0 for i in range(N)]
dist = [[-1 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        dist[i][j] = min(abs(j - i), abs(X - 1 - i) + 1 + abs(Y - 1 - j))
        count[dist[i][j]] += 1
for i in range(1, N):
    print(count[i])

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, x, y = map(int, input().split())
x -= 1
y -= 1
list1 = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        num = min([abs(j - i), abs(x - i) + 1 + abs(j - y), abs(y - i) + 1 + abs(x - j)])
        list1[i][j] = num

list2 = list(itertools.chain.from_iterable(list1))

for k in range(1,n):
    print(list2.count(k) // 2)

Submission status: Time Limit Exceeded

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

for i in range(1,n):
    for j in range(i+1,n+1):
        name = "{}-{}".format(i,j)
        if i <= x and j < y:
            dist[name] = min(j - i,x-i + 1 + y-j)
        elif i <= x and j >=  y:
            dist[name] = x-i + 1 + j-y
        elif i > x:
            dist[name] = min(j - i,i-x + 1 + abs(y-j))

for i in range(1,n):
    print(list(dist.values()).count(i))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import Counter
import numpy as np
n,x,y = map(int,input().split())
x,y = x-1 ,y-1
g = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    que = deque([(i, 0)])
    while que:
        node, cost = que.popleft()
        if g[i][node]!=float('inf'):
            continue
        else:
            g[i][node] = cost
            if node>0:
                que.append((node-1, cost+1))
            if node<n-1:
                que.append((node+1, cost+1))
            if node==x:
                que.append((y, cost+1))
            if node==y:
                que.append((x, cost+1))
array = np.array(g).flatten().tolist()
cnt = Counter(array)
for i in range(1, n):
    print(cnt[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
g=[[]*n for i in range(n)]
for i in range(n-1):
    g[i].append(i+1)
    g[i+1].append(i)
g[x-1].append(y-1)
g[y-1].append(x-1)

from collections import deque
distance=[]

for i in range(n):
    option=deque()
    option.append(i)
    completed=[False]*n
    memo=[0]*n
    while option:
        now=option.popleft()
        completed[now]=True
        for j in g[now]:
            if completed[j]==False and j not in option:
                memo[j]=memo[now]+1
                option.append(j)
    distance.append(memo)

ans=[0]*n
for i in range(n-1):
    for j in range(i+1,n):
        ans[distance[i][j]-1]+=1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
infty = 10 ** 4

def BFS(G, D, u):
    queue = deque()
    queue.append(u)
    visit = [False for k in range(len(D))]
    d = 0
    L = 1
    visit[i] = True
    while queue:
        add_v = 0
        while L > 0:
            v = queue.popleft()
            D[v] = d
            L -= 1
            for j in G[v]:
                if not visit[j]:
                    queue.append(j)
                    visit[j] = True
                    add_v += 1
        d += 1
        L = add_v
    return D

N, X, Y = map(int, input().split())
G = [[1]]
for i in range(1, N - 1):
    G.append([i - 1, i + 1])
G.append([N - 2])
G[X - 1].append(Y - 1)
G[Y - 1].append(X - 1)
dist = [[infty for j in range(N)] for i in range(N)]
for i in range(N):
    dist[i] = BFS(G, dist[i], i)
count = [0 for i in range(N)]
for i in range(N):
    for j in range(N):
        count[dist[i][j]] += 1
for i in range(N - 1):
    print(count[i + 1] // 2)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

pos = [i for i in range(1,N+1)]
ways = list(itertools.combinations(pos,2))

dist_l = []
for way in ways:
    i, j = way
    dists = [abs(i-j), abs(i - X) + 1 + abs(Y - j), abs(i - Y) + 1 + abs(X - j)]
    dist_l.append(min(dists))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from collections import Counter
def key(x, y):
    return str(x)+str(y)
def main2():
    # TLE
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    M = {}
    for i in range(N):
        for j in range(i, N):
            M[key(i, j)] = j - i
    
    def helper(x, y, from_cost):
        if 0 <= x <= N-1 and 0 <= y <= N-1:
            if M[key(x,y)] > from_cost+1:
                M[key(x,y)] = from_cost + 1
                cost = from_cost + 1

                helper(x-1,y, cost)
                helper(x+1,y, cost)
                helper(x,y-1, cost)
                helper(x,y+1, cost)
        
    helper(X, Y, 0)

    cost_list = Counter(list(M.values()))
    for k in range(N-1):
        print(cost_list[k+1])

from collections import deque
INF = 1e10


def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    ans = [0 for _ in range(N)]
    for sv in range(N):
        dist = [INF for _ in range(N)]
        q = deque([])

        def push(v, d):
            if dist[v] != INF: return
            dist[v] = d
            q.append(v)

        push(sv, 0)

        while q:
            sv = q.popleft()
            d = dist[sv]
            if sv > 0:
                push(sv-1, d+1)
            if sv < N-1:
                push(sv+1, d+1)
            if sv == X:
                push(Y, d+1)
            if sv == Y:
                push(X, d+1)

        for d in dist:
            ans[d] += 1
    
    for k in range(1, N):
        print(ans[k] // 2)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from collections import Counter
def key(x, y):
    return str(x)+str(y)
def main2():
    # TLE
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    M = {}
    for i in range(N):
        for j in range(i, N):
            M[key(i, j)] = j - i
    
    def helper(x, y, from_cost):
        if 0 <= x <= N-1 and 0 <= y <= N-1:
            if M[key(x,y)] > from_cost+1:
                M[key(x,y)] = from_cost + 1
                cost = from_cost + 1

                helper(x-1,y, cost)
                helper(x+1,y, cost)
                helper(x,y-1, cost)
                helper(x,y+1, cost)
        
    helper(X, Y, 0)

    cost_list = Counter(list(M.values()))
    for k in range(N-1):
        print(cost_list[k+1])

from collections import deque
INF = 1e10


def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    ans = []
    for sv in range(N):
        dist = [INF for _ in range(N)]
        q = deque([])

        def push(v, d):
            if dist[v] != INF: return
            dist[v] = d
            q.append(v)

        push(sv, 0)

        while q:
            sv = q.popleft()
            d = dist[sv]
            if sv > 0:
                push(sv-1, d+1)
            if sv < N-1:
                push(sv+1, d+1)
            if sv == X:
                push(Y, d+1)
            if sv == Y:
                push(X, d+1)
        ans += dist
    
    for k in range(1, N):
        print(ans.count(k) // 2)


main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    from collections import defaultdict, deque
    matrix = [[0]*N for _ in range(N)]
    for i in range(N-1):
        matrix[i][i+1] = matrix[i+1][i] = 1
    matrix[X][Y] = matrix[Y][X] = 1

    ans = [0] * N
    for i in range(N):
        queue = deque([(i, 0)])
        d = [float('inf')] * N
        while queue:
            node, dist = queue.popleft()
            if d[node] != float('inf'):
                continue
            d[node] = dist
            for adj in range(N):
                if matrix[node][adj]:
                    queue.append([adj, dist+1])
        for j in range(N):
            ans[d[j]] += 1
    for i in range(1, N):
        print(ans[i]//2)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.buffer.readline


def bfs(v):
    dist = [f_inf for _ in range(n)]
    dist[v] = 0
    q = deque()
    q.append(v)
    while q:
        u = q.popleft()
        for nv in tree[u]:
            if dist[nv] == f_inf:
                dist[nv] = dist[u] + 1
                q.append(nv)
    for d in dist:
        res[d] += 1


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

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

f_inf = float("inf")
res = [0 for _ in range(n)]
for i in range(n):
    bfs(i)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,X,Y = map(int, input().split())
X -= 1
Y -= 1
D = np.zeros((N,N))
for i in range(N-1):
  for j in range(i+1,N):
    D[i][j] = min(abs(i-j),abs(X-i)+abs(Y-j)+1,abs(Y-i)+abs(X-j)+1) 
for k in range(1,N):
  print (np.count_nonzero(D == k))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    from collections import defaultdict, deque
    ans = [0] * N
    for i in range(N):
        queue = deque([(i, 0)])
        d = [float('inf')] * N
        while queue:
            node, dist = queue.popleft()
            if d[node] != float('inf'):
                continue
            d[node] = dist
            if node == X:
                queue.append([Y, dist+1])
            if node == Y:
                queue.append([X, dist+1])
            if node + 1 < N:
                queue.append([node+1, dist+1])
            if node - 1 >= 0:
                queue.append([node-1, dist+1])
        for j in range(N):
            ans[d[j]] += 1
    for i in range(1, N):
        print(ans[i]//2)
resolve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from collections import Counter
import itertools


n, x, y = map(int,input().split())
edges = [[] for _ in range(n)]

def dijkstra(s, edges):
    d = [float('inf')] * n
    d[s] = 0
    heap = [(0, s)]
    while heap:
        c, node = heappop(heap)
        for cost, v in edges[node]:
            if c + cost < d[v]:
                d[v] = c + cost
                heappush(heap, (d[v], v))
    return d

for i in range(n-1):
    u, v = i, i+1
    edges[u].append([1,v])
    edges[v].append([1,u])
edges[x-1].append([1, y-1])
edges[y-1].append([1, x-1])

ans = []

for s in range(n):
    ans.append(dijkstra(s, edges))

f_ans = []
for i in range(n):
    f_ans.append(ans[i][i+1:])
f_ans = list(itertools.chain.from_iterable(f_ans))
f_ans = Counter(f_ans)

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from collections import Counter
import itertools


n, x, y = map(int,input().split())
edges = [[] for _ in range(n)]

def dijkstra(s, edges):
    d = [float('inf')] * n
    d[s] = 0
    heap = [(0, s)]
    while heap:
        c, node = heappop(heap)
        for cost, v in edges[node]:
            if c + cost < d[v]:
                d[v] = c + cost
                heappush(heap, (d[v], v))
    return d

for i in range(n-1):
    u, v = i, i+1
    edges[u].append([1,v])
    edges[v].append([1,u])
edges[x-1].append([1, y-1])
edges[y-1].append([1, x-1])

ans = []

for s in range(n):
    ans.append(dijkstra(s, edges))

f_ans = []
for i in range(n):
    f_ans.append(ans[i][i+1:])
f_ans = Counter(list(itertools.chain.from_iterable(f_ans)))

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

Submission status: Time Limit Exceeded

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

Ans=[]

i=1
while i<=N:
    j=i+1
    while j<=N:
        Ans.append(min(j-i,abs(X-i)+1+abs(j-Y)))
        j=j+1
    i=i+1

Ans=tuple(Ans)
k=1
while k<=N-1:
    print(Ans.count(k))
    k=k+1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, X, Y = map(int, input().split())
X, Y = X - 1, Y - 1
ans = [0] * N
for sv in range(N):
    dist = [float("inf")] * N
    q = deque([sv])

    def push(v, d):
        if dist[v] != float("inf"):
            return
        dist[v] = d
        q.append(v)

    push(sv, 0)
    while len(q):
        v = q.popleft()
        d = dist[v]
        if v - 1 >= 0:
            push(v - 1, d + 1)
        if v + 1 < N:
            push(v + 1, d + 1)
        if v == X:
            push(Y, d + 1)
        if v == Y:
            push(X, d + 1)
    for i in range(N):
        ans[dist[i]] += 1
for i in range(1, N):
    print(ans[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, X, Y = map(int, input().split())
X, Y = X - 1, Y - 1
ans = [0] * N
for sv in range(N):
    dist = [float("inf")] * N
    q = deque([sv])

    def push(v, d):
        if dist[v] != float("inf"):
            return
        dist[v] = d
        q.append(v)

    push(sv, 0)
    while len(q):
        v = q.popleft()
        d = dist[v]
        if v - 1 >= 0:
            push(v - 1, d + 1)
        if v + 1 < N:
            push(v + 1, d + 1)
        if v == X:
            push(Y, d + 1)
        if v == Y:
            push(X, d + 1)
    for i in range(N):
        ans[dist[i]] += 1
for i in range(N):
    ans[i] //= 2
for i in range(1, N):
    print(ans[i])

Submission status: Time Limit Exceeded

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

Ans=[]

i=1
while i<=N:
    j=i+1
    while j<=N:
        Ans.append(min(j-i,abs(X-i)+1+abs(j-Y)))
        j=j+1
    i=i+1

k=1
count=0
while k<=N-1:
    A=Ans.count(k)
    print(A)
    k=k+1
    if A==0:
        while k<=N-1:
            print(0)
            k=k+1
        break

Submission status: Time Limit Exceeded

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

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

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

csr = csr_matrix(([1]*n, (v, u)), shape=(n, n))
result = shortest_path(csr, method='D', directed=False)

for k in range(1, n):
    answer = np.sum(result==k) // 2
    print(answer)

Submission status: Time Limit Exceeded

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

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

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

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

matrix[x-1][y-1] = 1
matrix[y-1][x-1] = 1

matrix = np.array(matrix)
csr = csr_matrix(matrix)
result = shortest_path(csr, method='D')

for k in range(1, n):
    answer = np.sum(result==k) // 2
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
Graph = [[] for _ in range(N)]
for i in range(N):
    if i < N - 1:
        Graph[i].append(i + 1)
        Graph[i + 1].append(i)
    if X == i:
        Graph[X - 1].append(Y - 1)
        Graph[Y - 1].append(X - 1)
# print(Graph)
ans = [0] * (N - 1)
from collections import deque, Counter

for i in range(N):
    dist = [-1] * N
    que = deque([i])
    dist[i] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in Graph[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
    # print(dist)
    dist_Counter = Counter(dist)
    for key, val in dist_Counter.items():
        if key != 0:
            ans[key - 1] += val

for a in ans:
    print(a // 2)

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())

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

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

matrix[x-1][y-1] = 1
matrix[y-1][x-1] = 1

matrix = np.array(matrix)
result = shortest_path(matrix, method='D')

for k in range(1, n):
    answer = np.sum(result==k) // 2
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
# TODO: P4 Fix TLE (probably the answer itself is correct)

import sys
# sys.stdin = open('input.txt')

from collections import deque

class Node:
    def __init__(self, num=None):
        self.num = num
        self.next = []

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

nodes = []
q = deque()
ans = [0] * n

x -= 1
y -= 1

for i in range(n):
    node = Node(i)
    nodes.append(node)

# 無向グラフ
for i in range(n):
    node = nodes[i]
    if i == 0:
        node.next.append(nodes[i+1])
    elif i == n-1:
        node.next.append(nodes[i-1])
    else:
        node.next.append(nodes[i-1])
        node.next.append(nodes[i+1])
    if i == x:
        node.next.append(nodes[y])
    elif i == y:
        node.next.append(nodes[x])

# Select the initial node
for i in range(n):
    # Initialize
    dist = [0] * n
    visited = [False] * n

    # add the initial node
    q.append(nodes[i])

    # BFS
    while len(q) > 0:
        node = q.popleft()
        visited[node.num] = True

        if node.next is not None:
            for next_node in node.next:
                if not visited[next_node.num]:
                    dist[next_node.num] = dist[node.num] + 1
                    visited[next_node.num] = True
                    q.append(next_node)
    for i in range(n):
        ans[i] += dist.count(i)

#  Remove duplications -(1,2), (2,1)
for i in range(1,n):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
Graph = [[] for _ in range(N)]
for i in range(N):
    if i < N - 1:
        Graph[i].append(i + 1)
        Graph[i + 1].append(i)
    if X == i:
        Graph[X - 1].append(Y - 1)
        Graph[Y - 1].append(X - 1)
# print(Graph)
ans = [0] * (N - 1)
from collections import deque
for i in range(N):
    dist = [-1]*N
    que = deque([i])
    dist[i] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in Graph[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
    # print(dist)
    for d in dist:
        if d > 0:
            ans[d - 1] += 1
for a in ans:
    print(a // 2)

Submission status: Time Limit Exceeded

Solution code:
# TODO: P4 Fix TLE (probably the answer itself is correct)

import sys
# sys.stdin = open('input.txt')

from collections import deque

class Node:
    def __init__(self, num=None):
        self.num = num
        self.next = []
        self.visited = False

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

nodes = []
q = deque()
ans = [0] * n

x -= 1
y -= 1

for i in range(n):
    node = Node(i)
    nodes.append(node)

# 無向グラフ
for i in range(n):
    node = nodes[i]
    if i == 0:
        node.next.append(nodes[i+1])
    elif i == n-1:
        node.next.append(nodes[i-1])
    else:
        node.next.append(nodes[i-1])
        node.next.append(nodes[i+1])
    if i == x:
        node.next.append(nodes[y])
    elif i == y:
        node.next.append(nodes[x])

# Select the initial node
for i in range(n):
    # Initialize
    dist = [0] * n
    visited = [False] * n

    # add the initial node
    q.append(nodes[i])

    # BFS
    while len(q) > 0:
        node = q.popleft()
        visited[node.num] = True

        if node.next is not None:
            for next_node in node.next:
                if not visited[next_node.num]:
                    dist[next_node.num] = dist[node.num] + 1
                    visited[next_node.num] = True
                    q.append(next_node)
    for i in range(n):
        ans[i] += dist.count(i)

#  Remove duplications -(1,2), (2,1)
for i in range(i):
    ans[i] //= 2

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

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())

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

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


matrix[x-1][y-1] = 1
matrix[y-1][x-1] = 1

matrix = np.array(matrix)

result = shortest_path(matrix)

for k in range(1, n):
    answer = np.sum(result==k) // 2
    print(answer)