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())
count=[0]*n

def push(a,b,q,distance):
    if distance[a-1]==-1:
        distance[a-1]=b
        q.append(a)

    return (q,distance)

for i in range (1,n+1):
    distance=[-1]*n
    q=[]
    q.append(i)
    distance[i-1]=0
    while len(q) > 0:
        a=q.pop(0)
        if a>=2:
            q,distance=push(a-1,distance[a-1]+1,q,distance)
        if a<=n-1:
            q, distance = push(a + 1, distance[a-1] + 1, q, distance)
        if a==x:
            q, distance = push(y, distance[a-1] + 1, q, distance)
        if a==y:
            q, distance = push(x, distance[a-1] + 1, q, distance)

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N, X, Y = map(int, input().split())
list = []
for i in range(1,N):
    for j in range(i+1,N+1):
        list.append(min(j-i, abs(X-i)+1+abs(Y-j)))
for k in range(1,N):
    print(list.count(k))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N, X, Y = map(int, input().split())
list = []
for i in range(1,N):
    for j in range(2,N+1):
        list.append(min(j-i, abs(X-i)+1+abs(Y-j)))
for k in range(1,N):
    print(list.count(k))

Submission status: Time Limit Exceeded

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

def count(k):
    ans=0
    for i in range(1,N):
        for j in range(i+1,N+1):
            if min(abs(j-i),abs(X-i)+abs(Y-j)+1)==k:
                ans+=1
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

sys.setrecursionlimit(10 ** 9)

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())
ma = [[0]*n for _ in range(n)]
for i in range(n-1):
    ma[i][i+1] = 1
    ma[i+1][i] = 1

ma[x-1][y-1] = 1
ma[y-1][x-1] = 1
a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)
ans = [0]*(n-1)
for i in range(n):
  l = b[i]
  for num in l:
    if int(num) != 0:
    	ans[int(num)-1] += 1

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

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())
ma = [[0]*n for _ in range(n)]
for i in range(n-1):
    ma[i][i+1] = 1
    ma[i+1][i] = 1

ma[x-1][y-1] = 1
ma[y-1][x-1] = 1
a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)
ans = [0]*(n-1)
for i in range(n):
  l = b[i]
  for num in l:
    if int(num) != 0:
    	ans[int(num)-1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def push(q, tmp, d, D):
    if D[tmp] == -1:
        D[tmp] = d + 1
        q.append(tmp)

ans = [0] * N
for i in range(N):
    D = [-1] * N
    D[i] = 0
    q = deque()
    q.append(i)
    while len(q) > 0:
        tmp = q.popleft()
        d = D[tmp]
        if tmp < N-1:
            push(q, tmp+1, d, D)
        if 0 < tmp:
            push(q, tmp-1, d, D)
        if tmp == X-1:
            push(q, Y-1, d, D)
        if tmp == Y-1:
            push(q, X-1, d, D)

    for j in range(N):
        ans[D[j]] += 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())

def BFS(s, D):
    D[s] = 0
    q = deque()
    q.append(s)
    while len(q) > 0:
        tmp = q.popleft()
        d = D[tmp]
        if tmp < N-1:
            push(q, tmp+1, d, D)
        if 0 < tmp:
            push(q, tmp-1, d, D)
        if tmp == X-1:
            push(q, Y-1, d, D)
        if tmp == Y-1:
            push(q, X-1, d, D)
            
def push(q, tmp, d, D):
    if D[tmp] == -1:
        D[tmp] = d + 1
        q.append(tmp)

ans = [0] * N
for i in range(N):
    D = [-1] * N
    BFS(i, D)
    for j in range(N):
        ans[D[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import queue

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

def BFS(s, D):
    D[s] = 0
    q = queue.Queue()
    q.put(s)
    while not q.empty():
        tmp = q.get()
        if tmp < N-1:
            push(q, tmp+1, D[tmp], D)
        if 0 < tmp:
            push(q, tmp-1, D[tmp], D)
        if tmp == X-1:
            push(q, Y-1, D[tmp], D)
        if tmp == Y-1:
            push(q, X-1, D[tmp], D)
            
def push(q, tmp, d, D):
    if D[tmp] == -1:
        D[tmp] = d + 1
        q.put(tmp)

ans = [0] * N
for i in range(N):
    D = [-1] * N
    BFS(i, D)
    for j in range(N):
        ans[D[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import queue

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

G = [[i-1, i+1] for i in range(N)]
G[0].remove(-1)
G[N-1].remove(N)
G[X-1].append(Y-1)
G[Y-1].append(X-1)

def BFS(s, G, D):
    D[s] = 0
    q = queue.Queue()
    q.put(s)
    while not q.empty():
        tmp = q.get()
        for i in range(len(G[tmp])):
            tmp1 = G[tmp][i]
            if D[tmp1] == -1:
                D[tmp1] = D[tmp] + 1
                q.put(tmp1)

ans = [0] * (N)
for i in range(N):
    D = [-1] * N
    BFS(i, G, D)
    for j in range(N):
        ans[D[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import queue

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

G = [[i-1, i+1] for i in range(N)]
G[0].remove(-1)
G[N-1].remove(N)
G[X-1].append(Y-1)
G[Y-1].append(X-1)

def BFS(s, G, D):
    D[s] = 0
    already = []
    already.append(s)
    q = queue.Queue()
    q.put(s)
    while not q.empty():
        tmp = q.get()
        for i in range(len(G[tmp])):
            tmp1 = G[tmp][i]
            if not tmp1 in already:
                D[tmp1] = D[tmp] + 1
                q.put(tmp1)
                already.append(tmp1)

ans = [0] * (N)
for i in range(N):
    D = [-1] * N
    BFS(i, G, D)
    for j in range(N):
        ans[D[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())

dis_list = [0] * (n - 1)

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

for i in dis_list:
    print(i)

Submission status: Time Limit Exceeded

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

dis_list = [0] * (n - 1)

for i in range(0, n):
    for j in range(i + 1, n):
        dis = min(abs(j - i), abs(x - i - 1) + 1 + abs(y - j - 1), abs(y - i - 1) + 1 + abs(x - j - 1))
        # print(dis)
        dis_list[dis - 1] += 1

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

Submission status: Time Limit Exceeded

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

node = list(range(1, n + 1))

dis_list = []

for i in node:
    for j in node:
        if j != i:
            dis = min(abs(j - i), abs(x - i) + 1 + abs(y - j), abs(y - i) + 1 + abs(x - j))
            dis_list.append(dis)

for dis in range(1, n):
    print(len([i for i in dis_list if i == dis]) // 2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
 
 
def solve(N: int, X: int, Y: int):
    cst = [0 for _ in range(N)]
    nodes = [Node(i, N, X, Y) for i in range(N)]
    for i in range(N):
        for n in nodes:
            n.done = False
            n.cost = -1
        # nodes = []
        # for j in range(N):
        #     nodes.append(Node(j, N, X, Y))
        # nodes = [Node(i, N, X, Y) for i in range(N)]
        nodes[i].cost = 0
        while True:
            doneNode = Node(N, N, X, Y)
            for n in nodes:
                if n.done or n.cost < 0:
                    pass
                elif doneNode.num == N or n.cost < doneNode.cost:
                    doneNode = n
            if doneNode.num == N:
                break
            
            doneNode.done = True
            for i in doneNode.edges:
                if nodes[i].cost < 0 or doneNode.cost + 1 < nodes[i].cost:
                    nodes[i].cost = doneNode.cost + 1
        
        for n in nodes:
            cst[n.cost] += 1
    
    for i in range(1, len(cst)):
        print(int(cst[i] / 2))
        
 
 
 
class Node:
    def __init__(self, i, N, X, Y):
        self.num = i
        self.edges = set()
        if i == 0:
            self.edges.add(i+1)
        elif i == N - 1:
            self.edges.add(i-1)
        else:
            self.edges.add(i+1)
            self.edges.add(i-1)
        if i == X - 1:
            self.edges.add(Y - 1)
        elif i == Y - 1:
            self.edges.add(X - 1)
        self.done = False
        self.cost = -1
 
            
            
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, X, Y)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

# スパース行列の作成
data = [1]*N

row = [int(x) for x in range(N-1)]
row.append(X-1)

col = [int(x+1) for x in range(N-1)]
col.append(Y-1)

S_Mat = csr_matrix((data, (row, col)), shape=(N,N)).toarray()
S_Mat += S_Mat.T

# 最短経路行列の取得
SP_Mat = dijkstra(S_Mat, directed=False, unweighted=True)

for k in range(N-1):
    print(int(np.sum(SP_Mat == k+1)/2))

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

# スパース行列の作成
data = [1]*N

row = [int(x) for x in range(N-1)]
row.append(X-1)

col = [int(x+1) for x in range(N-1)]
col.append(Y-1)

S_Mat = csr_matrix((data, (row, col)), shape=(N,N)).toarray()
S_Mat += S_Mat.T

# 最短経路行列の取得
SP_Mat = shortest_path(S_Mat, directed=False, unweighted=True)

for k in range(N-1):
    print(int(np.sum(SP_Mat == k+1)/2))

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
dis = [[0 for _ in range(n)]for p in range(n)]
dis[0][1] = 1
dis[n-1][n-2] = 1
dis[x-1][y-1] = 1
dis[y-1][x-1] = 1
for i in range(1,n-1):
    dis[i][i-1] = 1
    dis[i][i+1] = 1

def bfs(start):
    queue = [start]
    disq = [0]
    searched = [start]
    while(len(queue)):
        now = queue.pop(0)
        dnow = disq.pop(0)
        for goal in range(n):
            if not goal in searched:
                if dis[now][goal] == 1:
                    queue.append(goal)
                    disq.append(dnow + 1)
                    if dis[start][goal] == 0:
                        dis[start][goal] = dnow + 1
                    else:
                        dis[start][goal] = min(dnow + 1,dis[start][goal])
                    searched.append(now)

for i in range(n):
    bfs(i)

dissum = [0 for _ in range(n-1)]

for i in range(n):
    for j in range(i):
        dissum[dis[i][j]-1] += 1

for i in range(len(dissum)):
    print(dissum[i])

Submission status: Time Limit Exceeded

Solution code:
[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
array=[[-1 for _ in range(N)]for _ in range(N)]
for i in range(N):
    for j in range(i,N):
        array[i][j]=min(abs(i-j),abs(i-X)+1+abs(Y-j),abs(i-Y)+1+abs(X-j))
#print(array)

count=[0 for _ in range(N)]
for i in range(N):
    for j in range(i,N):
        count[array[i][j]]+=1
for i in range(1,N):
        print(count[i])

#print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n, x, y = map(int, input().split())
    cnt = [0]*n
    x -= 1
    y -= 1
    q = deque()
    
    for i in range(n):
        q.appendleft(i)
        dist = [None]*n
        dist[i] = 0
        while q:
            j = q.pop()
            d = dist[j]
            cnt[d] += 1
            if j > 0 and dist[j-1] is None:
                dist[j-1] = d+1
                q.appendleft(j-1)
            if j < n-1 and dist[j+1] is None:
                dist[j+1] = d+1
                q.appendleft(j+1)
            if j == x and dist[y] is None:
                dist[y] = d+1
                q.appendleft(y)
            elif j == y and dist[x] is None:
                dist[x] = d+1
                q.appendleft(x)
    for i in range(1, n):
        print(cnt[i]//2)
                

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n, x, y = map(int, input().split())
    cnt = [0]*n
    q = deque()
    
    for i in range(n):
        q.appendleft([i, 0])
        dist = [None]*n
        dist[i] = 0
        while q:
            j, d = q.pop()
            cnt[d] += 1
            if j > 0 and dist[j-1] is None:
                dist[j-1] = d+1
                q.appendleft([j-1, d+1])
            if j < n-1 and dist[j+1] is None:
                dist[j+1] = d+1
                q.appendleft([j+1, d+1])
            if j == x-1 and dist[y-1] is None:
                dist[y-1] = d+1
                q.appendleft([y-1, d+1])
            elif j == y-1 and dist[x-1] is None:
                dist[x-1] = d+1
                q.appendleft([x-1, d+1])
    for i in range(1, n):
        print(cnt[i]//2)
                

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n, x, y = map(int, input().split())
    dist = [[None]*n for _ in range(n)]
    cnt = [0]*n
    q = deque()
    
    for i in range(n):
        q.appendleft([i, 0])
        dist[i][i] = 0
        while q:
            j, d = q.pop()
            cnt[d] += 1
            if j > 0 and dist[i][j-1] is None:
                dist[i][j-1] = d+1
                q.appendleft([j-1, d+1])
            if j < n-1 and dist[i][j+1] is None:
                dist[i][j+1] = d+1
                q.appendleft([j+1, d+1])
            if j == x-1 and dist[i][y-1] is None:
                dist[i][y-1] = d+1
                q.appendleft([y-1, d+1])
            elif j == y-1 and dist[i][x-1] is None:
                dist[i][x-1] = d+1
                q.appendleft([x-1, d+1])
    for i in range(1, n):
        print(cnt[i]//2)
                

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import Counter
[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
gyoretu=np.full((N,N),2000)
gyoretu[0][0]=0
gyoretu[0][1]=1
for i in range(1,N-1):
    gyoretu[i][i-1]=1
    gyoretu[i][i]=0
    gyoretu[i][i+1]=1
gyoretu[N-1][N-2]=1
gyoretu[N-1][N-1]=0

gyoretu[X][Y]=1
gyoretu[Y][X]=1

G=csgraph_from_dense(gyoretu)
#print(G)
d=floyd_warshall(G)
#print(d)
#for k in range(N):
#    for i in range(N):
#        for j in range(N):
#            if gyoretu[i][j]> gyoretu[i][k] + gyoretu[k][j]:
#                gyoretu[i][j] =gyoretu[i][k] + gyoretu[k][j]
array=[]
for i in range(N):
        #array += gyoretu[i][i:]
        array += list(d[i][i:])
c=Counter(array)
for i in range(1, N):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import Counter
[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
gyoretu=[]
for i in range(N):
    row=[]
    for j in range(N):
        if i == j:
            row.append(0)
        elif abs(i - j) == 1 or i == X and j == Y or i == Y and j == X:
            row.append(1)
        else:
            row.append(2000)
    gyoretu.append(row)
G=csgraph_from_dense(gyoretu)
#print(G)
d=floyd_warshall(G)
#print(d)
#for k in range(N):
#    for i in range(N):
#        for j in range(N):
#            if gyoretu[i][j]> gyoretu[i][k] + gyoretu[k][j]:
#                gyoretu[i][j] =gyoretu[i][k] + gyoretu[k][j]
array=[]
for i in range(N):
        #array += gyoretu[i][i:]
        array += list(d[i][i:])
c=Counter(array)
for i in range(1, N):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
gyoretu=[]
for i in range(N):
    row=[]
    for j in range(N):
        if i == j:
            row.append(0)
        elif abs(i - j) == 1 or i == X and j == Y or i == Y and j == X:
            row.append(1)
        else:
            row.append(2000)
    gyoretu.append(row)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if gyoretu[i][j]> gyoretu[i][k] + gyoretu[k][j]:
                gyoretu[i][j] =gyoretu[i][k] + gyoretu[k][j]
array=[]
for i in range(N):
        array+=gyoretu[i][i:]
c=Counter(array)
for i in range(1, N):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
gyoretu=[]
for i in range(N):
    row=[]
    for j in range(N):
        if i == j:
            row.append(0)
        elif abs(i - j) == 1 or i == X and j == Y or i == Y and j == X:
            row.append(1)
        else:
            row.append(2000)
    gyoretu.append(row)
for k in range(N):
    for i in range(N):
        for j in range(N):
            gyoretu[i][j] = gyoretu[i][j] if gyoretu[i][j]< gyoretu[i][k] + gyoretu[k][j] else gyoretu[i][k] + gyoretu[k][j]
array=[]
for i in range(N):
        array+=gyoretu[i][i:]
c=Counter(array)
for i in range(1, N):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
gyoretu=[]
for i in range(N):
    row=[]
    for j in range(N):
        if i == j:
            row.append(0)
        elif abs(i - j) == 1 or i == X and j == Y or i == Y and j == X:
            row.append(1)
        else:
            row.append(2000)
    gyoretu.append(row)
for k in range(N):
    for i in range(N):
        for j in range(N):
            gyoretu[i][j] = min([gyoretu[i][j], gyoretu[i][k] + gyoretu[k][j]])
array=[]
for i in range(N):
        array+=gyoretu[i][i:]
c=Counter(array)
for i in range(1, N):
    print(c[i])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, x, y = map(int,input().split())
ans = np.zeros(n-1, dtype=np.int)

for i in range(1,n):
    for j in range(i+1,n+1):
        if j <= x or y <= i:
            dist = j - i
        else:
            dist = j - i
            short = abs(x - i) + 1 + abs(y - j)
            if short < dist:
                dist = short
        ans[dist-1] = ans[dist-1] + 1

for k in ans:
    print(k)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
D=[]
X-=1;Y-=1
for i in range(N-1):
  for j in range(i+1,N):
    if i<=X:
      if j<=X:
        d=j-i
      elif X<j<Y:
        d=min(j-i,X-i+1+Y-j)
      else:
        d=X-i+1+j-Y
    elif X<i<Y:
      if X<j<Y:
        d=min(j-i,i-X+1+Y-j)
      else:
        d=min(j-i,i-X+1+j-Y)
    else:
      d=j-i
    #print(i,j,d)
    D.append(d)
for i in range(1,N):
  print(D.count(i))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, x, y = map(int,input().split())
ans = np.zeros(n-1)

for i in range(1,n):
    for j in range(i+1,n+1):
        if j <= x or y <= i:
            dist = j - i
        else:
            dist = j - i
            short = abs(x - i) + 1 + abs(y - j)
            if short < dist:
                dist = short
        ans[dist-1] = ans[dist-1] + 1

for k in ans:
    print(int(k))

Submission status: Time Limit Exceeded

Solution code:
import queue
n,x,y = map(int,input().split())
ans = {}
for i in range(1,n):
    dist = [-1]*n
    q = queue.Queue()
    dist[i-1] = 0
    q.put(i)
    while True:
        if q.empty():
            break
        else:
            a = q.get()
            if a > 1 and dist[a-2] == -1:
                dist[a-2] = dist[a-1]+1
                q.put(a-1)
            if a < n and dist[a] == -1:
                dist[a] = dist[a-1]+1
                q.put(a+1)
            if a == x and dist[y-1] == -1:
                dist[y-1] = dist[a-1]+1
                q.put(y)
            if a == y and dist[x-1] == -1:
                dist[x-1] = dist[a-1]+1
                q.put(x)
    for j in range(i,n):
        s = dist[j]
        if s in ans.keys():
            ans[s] += 1
        else:
            ans[s] = 1
for k in range(1,n):
    if k in ans.keys():
      print(ans[k])
    else:
      print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, X, Y = map(int, input().split())
 
res = np.zeros(N - 1, dtype=int)
for i in range(1, N):
    for j in range(i + 1, N + 1):
        r1 = j - i
        r2 = np.abs(X - i) + 1 + np.abs(j - Y)
        dist = min(r1, r2)
        res[dist - 1] += 1
_ = [print(d) for d in res]

Submission status: Time Limit Exceeded

Solution code:
import collections
def bfs(s, n, x, y):
    q = collections.deque()
    INF = 1001001001
    distances = [INF for _ in range(n)]
    #initialized
    distance = 0
    q.append(s)
    distances[s] = distance
    while len(q):
        pos = q.popleft()
        distance = distances[pos]+1
        if 0 <= pos-1:
            if distances[pos-1] == INF:
                q.append(pos - 1)
                distances[pos-1] = distance
        if n > pos +1:
            if distances[pos+1] == INF:
                q.append(pos + 1)
                distances[pos+1] = distance
        if pos == x:
            if distances[y] == INF:
                q.append(y)
                distances[y] = distance
        if pos == y:
            if distances[x] == INF:
                q.append(x)
                distances[x] = distance
    return distances
    
def solve(n, x, y):
    ans = [0 for _ in range(n)]
    for i in range(n):
        distances = bfs(i, n, x, y)
        for j in distances:
            ans[j] += 1
    ans = list(map(lambda x:x//2, ans))
    return ans

def main():
    n, x, y = map(int,input().split())
    x, y = x-1, y-1
    ans = solve(n, x, y)
    print(*ans[1:],sep = '\n')

def test():
    n, x, y = map(int,input().split())
    ans = bfs(0,n, x, y)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

E=[[] for i in range(N)]

for i in range(N-1):
  E[i].append(i+1)
  E[i+1].append(i)
  
E[X-1].append(Y-1)
E[Y-1].append(X-1)

INF=10**4

ans=[0 for i in range(N)]
from collections import deque
for i in range(N):
  score=[INF for i in range(N)]
  q=deque([[i,0]])
  while q:
    v,dist=q.pop()
    if score[v]>dist:
      score[v]=dist
    else:
      continue
    for child in E[v]:
      q.append([child,dist+1])
  for s in score:
    ans[s]+=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())
k_mins=[]
for i in range(1,n):
    for j in range(i+1,n+1):
        k_mins.append(min(j-i,abs(x-i)+1+abs(y-j),abs(x-j)+1+abs(y-i)))
ret=[]
k_mins.sort(reverse=True)
for i in range(1,n):
    c=0
    while len(k_mins) > 0 and k_mins[len(k_mins)-1]==i:
        k_mins.pop() 
        c+=1
    ret.append(c)
for r in ret:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
"""
"""
n,x,y=map(int,input().split())
k_mins=[]
for i in range(1,n):
    for j in range(i+1,n+1):
        k_mins.append(min(j-i,abs(x-i)+1+abs(y-j),abs(x-j)+1+abs(y-i)))

ret=[]
for i in range(1,n):
    #[i for i in l if not i % 2 == 0]
    ret.append(len([ki for ki in k_mins if ki == i]))
for r in ret:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
dists = [0]*(n)
for i in range(n):
    for j in range(i):
        dist = min(abs(i-j),abs(i+1-x)+1+abs(j+1-y),abs(j+1-x)+1+abs(i+1-y))
        dists[dist] = dists[dist]+1
    
for i in range(len(dists) - 1):
    print(dists[i+1])

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
dists = []
for i in range(n):
    for j in range(i):
        dist = min(abs(i-j),abs((i+1)-x)+1+abs((j+1)-y),abs((j+1)-x)+1+abs((i+1)-y))
        dists.append(dist)
    
for i in range(n-1):
    print(sum([1 for dist in dists if dist == i+1]))

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
dists = [0]*(n)
for i in range(n):
    for j in range(i):
        dist = min(abs(i-j),abs((i+1)-x)+1+abs((j+1)-y),abs((j+1)-x)+1+abs((i+1)-y))
        dists[dist] = dists[dist]+1
    
for i in range(len(dists) - 1):
    print(dists[i+1])

Submission status: Time Limit Exceeded

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

dists = [0]*(n)
for p in ps:
    dist = min(abs(p[0]-p[1]),abs(p[0]-x)+1+abs(p[1]-y),abs(p[1]-x)+1+abs(p[0]-y))
    dists[dist] = dists[dist]+1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y = map(int,input().split())
to = [[] for _ in range(n)]
x -= 1
y -= 1
for i in range(n-1):
    to[i].append(i+1)
    to[i+1].append(i)
to[x].append(y)
to[y].append(x)
ans = [0]*(n-1)
Q = deque()
dist = [-1]*n
for i in range(n):
    Q.clear()
    Q.append(i)
    for j in range(n): dist[j] = -1
    dist[i] = 0
    while Q:
        cur = Q.popleft()
        for nxt in to[cur]:
            if dist[nxt] != -1: continue
            Q.append(nxt)
            dist[nxt] = dist[cur]+1
            ans[dist[cur]] += 1
print("\n".join(map(str,map(lambda x:x//2,ans))))

Submission status: Time Limit Exceeded

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


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

route_map = [dict() for _ in range(n)]
route_map[x-1][y-1]=1
route_map[y-1][x-1]=1
for i in range(n-1):
    route_map[i][i+1] = 1
    route_map[i+1][i]=1    
lst=[]
for i in range(n):
    lst+=Dijkstra(route_map,i).execute()        
Lst=list(collections.Counter(lst).items())
Key=list(collections.Counter(lst).keys())
m=max(Key)
for i in range(1,m+1):
    print(Lst[i][1]//2)
for i in range(m+1,n):
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, x, y = map(int, input().split())

def push(v, d):
    if Dist[v] == -1:   #距離未更新
        Dist[v] = d
        Queue.append(v)
    else:   #距離が更新済み
        pass
    return 0
    
Ans = [0] * n
for i in range(n):
    Queue = deque([i])
    Dist = [-1] * n
    Dist[i] = 0 
    while len(Queue) != 0:
        v = Queue[0]
        d = Dist[v]
        #辺を通して次の頂点へ

        #-方向
        if v-1 >= 0:
            push(v-1, d+1)
        else:
            pass

        #+方向
        if v+1 < n:
            push(v+1, d+1)
        else:
            pass

        #XとYの間
        if v == x-1 :
            push(y-1, d+1)
        elif v == y-1:
            push(x-1, d+1)
        else:
            pass
        Queue.popleft()
    for i in Dist:
        Ans[i] += 1

for i in range(len(Ans)):
    Ans[i] *= 0.5

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