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: Runtime Error

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

X = X - 1
Y = Y - 1

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

ans = np.minimum(x, y)

a, b = np.unique(ans, return_counts=True)
count = 1
for i in range(1,N):
    if count>=len(a):
        print(0)
        continue
    if a[count] == i:
        print(b[count])
        count += 1
    else:
        print(0)

Submission status: Runtime Error

Solution code:
K,N =map(int,input().split())
A =input()
B =A.split(" ")
B = [ int(i) for i in B]
g = B[N-1] - B[0]
print(g)

Submission status: Runtime Error

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

@numba.njit
def init(graph_arr, N, X ,Y):
    for i in range(N-1):
        graph_arr[i, i + 1] = 1
        graph_arr[i+1, i ] = 1
    graph_arr[X-1, Y-1] = 1

list_in = list(map(int, input().split()))
N = list_in[0]
X = list_in[1]
Y = list_in[2]

graph_arr = np.zeros((N,N), dtype=np.int)

init(graph_arr, N, X, Y)

result = np.triu(shortest_path(graph_arr))

for i in range(1, N):
    num_path = np.count_nonzero(result == i)
    print(num_path)

Submission status: Runtime Error

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

def warshall_floyd(d, n):
    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


def main():
    N, X, Y = list(map(int, input().split()))
    
    d = [[0] * 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[N - 1][N - 1] = 0

    d[X - 1][Y - 1] = 1
    d[Y - 1][X - 1] = 1
    d = np.array(d)

    d = shortest_path(d).astype(np.int)
    
    unique, counts = np.unique(d, return_counts=True)
    for i in range(1, N):
        if i not in unique:
            print('0')
        else:
            print((d == i).sum() // 2)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

N, X, Y = map(int, input().split())
A = csr_matrix((N, N), dtype=np.int8).toarray()
for idx in range(N - 1):
    A[idx][idx + 1] = 1
    A[idx + 1][idx] = 1

A[X - 1][Y - 1] = 1
A[Y - 1][X - 1] = 1

graph = csr_matrix(A)
dist_matrix = shortest_path(csgraph=graph, directed=False, unweighted=True, return_predecessors=False)
for k in range(1, N):
    c = np.count_nonzero(dist_matrix == k)
    print(c // 2)

Submission status: Runtime Error

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

X = X - 1
Y = Y - 1

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

ans = np.minimum(x, y)

for i in range(1,N):
    print(np.sum(ans==i))

Submission status: Runtime Error

Solution code:
from collections import Counter
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

import sys
input = sys.stdin.readline

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

n, x, y = map(int, input().split())
f_inf = float('inf')
dist = [[f_inf] * n for _ in range(n)]
for i in range(n): dist[i][i] = 0

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

dist[x-1][y-1]=1
dist[y-1][x-1]=1

G = csgraph_from_dense(dist, null_value=10**9)
dist = floyd_warshall(G)

counter = Counter(flatten_2dim(dist))
counter = sorted(counter.most_common())[1:]

for key, val in counter:
    print(val//2)
for i in range(n - len(counter)-1):
    print(0)

Submission status: Runtime Error

Solution code:
#from scipy.misc import comb
from scipy.special import comb
import itertools

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

combi = list(itertools.combinations(range(1,N+1), 2))
#print(combi)
dist = {}
for i in range(1, N):
    dist[i] = 0

for kyori in combi:
    if kyori[1] >= Y and kyori[0] <= X:
        c = (kyori[1] - Y) + 1 + (X - kyori[0])
    elif kyori[1] >= Y:
        a = kyori[1] - kyori[0]
        b = (kyori[1] - Y) + 1 + int(abs((X - kyori[0])))
        c = min([a, b])
    elif kyori[0] <= X:
        a = kyori[1] - kyori[0]
        b = int(abs(kyori[1] - Y)) + 1 + (X - kyori[0])
        c = min([a, b])
    else:
        c = kyori[1] - kyori[0]
    dist[c] += 1
    #print(c, kyori)
dist2 = sorted(dist.items())
#print(dist, dist2)
for i in range(0, N-1):
    print(dist2[i][1])

Submission status: Runtime Error

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())
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 = shortest_path(np.array(graph))
u, counts = np.unique(ans, return_counts=True)

for i in range(1,n):
    if i in u:
        print(int(counts[np.where(u==i)[0][0]]/2))
    else:print(0)

Submission status: Runtime Error

Solution code:
from collections import Counter
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

import sys
input = sys.stdin.readline

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

n, x, y = map(int, input().split())
f_inf = float('inf')
dist = [[f_inf] * n for _ in range(n)]

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

dist[x-1][y-1]=1
dist[y-1][x-1]=1

G = csgraph_from_dense(dist, null_value=10**9)
dist = floyd_warshall(G)

counter = Counter(flatten_2dim(dist))
counter = sorted(counter.most_common())[1:]

for key, val in counter:
    print(val//2)
for i in range(n - len(counter)-1):
    print(0)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, X, Y = [int(x) for x in input().strip().split()]
G = np.zeros((N, N), dtype=int)
for k in range(N):
    for k2 in range(k+1, N):
        G[k, k2] = min(k2 - k, G[min(k, X-1), max(k, X-1)]+1+abs(k2 - (Y - 1)))

for k in range(1, N):
    print(sum(sum(G == k)))

Submission status: Runtime Error

Solution code:
from itertools import tee

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall, shortest_path


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


N, X, Y = map(int, input().split())
A = [[0 for _ in range(N)] for _ in range(N)]
for idx, row in enumerate(A, start=1):
    if idx < N:
        row[idx % N] = 1

A = np.array(A) + np.array(A).transpose()
A[X-1][Y-1] = 1
A[Y-1][X-1] = 1
# print(A)
graph = csr_matrix(A)
dist_matrix  = shortest_path(csgraph=graph, directed=False, return_predecessors=False)
dist_matrix  = shortest_path(csgraph=graph, directed=False, return_predecessors=False)
# print(dist_matrix)
for k in range(1, N):
    c = np.count_nonzero(dist_matrix == k)
    print(c // 2)

Submission status: Runtime Error

Solution code:
def resolve():
    # 最短経路問題で使われるアルゴリズムの１つ。
    # グラフ上の全ての頂点間の最短経路を探す
    # 負の閉路（辺の重みの和が負になるような閉路）がない限り、負の辺があっても使える。

    # 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
    # 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
    def warshall_floyd(v_num, e_num, dist_lst):

        # 負の閉路を持つか

        # 頂点iから頂点jへの経路と、頂点kを経由した場合の経路とを比較して
        # よりコストの合計が小さい方を配列に入れる動的計画法
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

        ans=[0]*N
        for lst in dist_lst:
            for i in range(len(lst)):
                ans[lst[i]]+=1

        for j in range(1,N):
            print(int(ans[j]))

    N,X,Y=map(int,input().split())
    # 頂点の数と辺の数
    v_num, e_num = N,N

    # 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
    # a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]

    for i in range(v_num-1):
        dist_lst[i][i+1] = 1
    dist_lst[X-1][Y-1] = 1


    for v in range(v_num):
        dist_lst[v][v] = 0

    warshall_floyd(v_num, e_num, dist_lst)





resolve()

Submission status: Runtime Error

Solution code:
n, x, y = map(int, input().split())
graph = dict()
for i in range(1, n+1):
    if i not in graph.keys():
        graph[i] = set()
    if i < n:
        graph[i].add(i+1)
    if i > 1:
        graph[i].add(i-1)
graph[x].add(y)
graph[y].add(x)
dist = [[]]


def bfs(source):
    q = deque()
    q.append(source)
    d = [pow(10, 4)] * (n+1)
    d[source] = 0
    vis = [0] * (n+1)
    while len(q):
        temp = q.popleft()
        for i in graph[temp]:
            if not vis[i]:
                q.append(i)
                vis[i] = 1
            d[i] = min(d[temp]+1, d[i])
    dist.append(d)


for i in range(1, n+1):
    bfs(i)


dp = dict()
for i in range(1, n):
    for j in range(i+1, n+1):
        if dist[i][j] not in dp.keys():
            dp[dist[i][j]] = 0
        dp[dist[i][j]] += 1

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

Submission status: Runtime Error

Solution code:
# coding: utf-8

from copy import deepcopy

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

neighbor = {}
for i in range(1, X):
    neighbor[i] = [i+1]
for i in range(Y+1, N):
    neighbor[i] = [i+1]
for i in range(X+1, Y):
    neighbor[i] = [i-1, i+1]
neighbor[X] = [X+1, Y]
neighbor[Y] = [Y-1, Y+1]
neighbor[N] = [] if Y < N else [N-1]

# print(neighbor)

# neighbor = {i: [i-1, i+1] for i in range(2, N)}
# neighbor[1] = [2]
# neighbor[N] = [N-1]
# neighbor[X].append(Y)
# neighbor[Y].append(X)

appeared_st = set([])


def rec(n, dist, s, k, appeared):
    # print(appeared_st)
    if dist == k:
        if s < n and "{}.{}".format(s, n) not in appeared_st:
            appeared_st.add("{}.{}".format(s, n))

    toes = [node for node in neighbor[n] if node not in appeared]
    for to in toes:
        appeared_copy = deepcopy(appeared)
        appeared_copy.add(to)
        rec(to, dist+1, s, k, appeared_copy)

    
for k in range(1, N):
    tmp = len(appeared_st)

    for s in range(1, N+1):
        rec(s, 0, s, k, {s})

    print(len(appeared_st) - tmp)

# print(appeared_st)
# print(len(appeared_st))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, x, y;
  cin >> n >> x >> y;
  vector<vector<int>> distance(n, vector<int>(n, n));
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
      distance[i][j] = abs(i-j);
    }
  }
  
  distance[x-1][y-1] = 1;
  distance[y-1][x-1] = 1;
  
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
      if (distance[i][j] > distance[i][x-1]+distance[x-1][j]){
        distance[i][j] = distance[i][x-1]+distance[x-1][j];
      }
    }
  }
  
  
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
      if (distance[i][j] > distance[i][y-1]+distance[y-1][j]){
        distance[i][j] = distance[i][y-1]+distance[y-1][j];
      }
    }
  }
  
  vector<int> ans(n-1, 0);
  int key;
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
      if (distance[i][j] == n){
        continue;
      }
      key = distance[i][j];
      ans[key-1]++;
    }
  }
  for (int i = 0; i < n-1; i++){
    cout << ans[i]/2 << endl;
  }
  
}

Submission status: Runtime Error

Solution code:

def resolve():
    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())
    netw = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if abs(j-i) == 1:
                netw[i][j] = 1
    netw[x-1][y-1] = 1
    netw[y-1][x-1] = 1
    netw = np.array(netw)
    csr = csr_matrix(netw)
    ans = {}
    for i in range(n-1):
        a = shortest_path(csr, indices=i)
        for j in range(i+1, n):
            if a[j] in ans:
                ans[a[j]] += 1
            else:
                ans[a[j]] = 1
    for i in range(1, n):
        if i in ans:
            continue
        else:
            ans[i] =0
    for i in range(1, n):
        print(ans[i])
resolve()

Submission status: Runtime Error

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())
G = np.zeros((N, N))
for i in range(N-1):
    G[i,i+1] = 1
    G[i+1,i] = 1
G[X-1, Y-1] = 1
G[Y-1, X-1] = 1
#print(G)
spG = shortest_path(csr_matrix(G))
for i in range(1,N):
    print(int(np.count_nonzero(spG==i)/2))

Submission status: Runtime Error

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))

maxi = 0

for i in range(1, n):
    x = a[i] - a[i-1]

    maxi = max(maxi, x)

x = a[-1] - a[0]

if k - x < x:
    x = k - x

maxi = max(maxi, x)

print(k - maxi)

Submission status: Runtime Error

Solution code:
n,x,y=map(int,input().split())
ans=[0 for i in range(n-1)]
for start in range(n):
  gone=[0 for i in range(n)]
  gone[start]=1
  now ={start}
  for i in range(1,n):
    go=set()
    for s in now:
      if s!=0 and gone[s-1]==0:
        go.add(s-1)
        gone[s-1]=1
        ans[i]+=1
      if s!=n-1 and gone[s+1]==0:
        go.add(s+1)
        gone[s+1]=1
        ans[i]+=1
      if s==x-1 and gone[y-1]==0:
        go.add(y-1)
        gone[y-1]=1
        ans[i]+=1
      if s==y-1 and gone[x-1]==0:
        go.add(x-1)
        gone[x-1]=1
        ans[i]+=1
    now=go
for i in range(1,n):
  print(ans[i]//2)

Submission status: Runtime Error

Solution code:
import itertools


N, X, Y = map(int, input().split())
lst = [0] * N
for l,r in itertools.combinations(range(1,N+1),2):
    lst[min(r-l,abs(r-Y)+1+abs(l-X))] += 1
for i in range(1,N+1):
    print(lst[i])

Submission status: Runtime Error

Solution code:
def find_shortest_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest


n,x,y=map(int,input().split())
d={}
lst=list(0 for i in range(n))
for i in range(1,n):
  if i not in d:
    d[i]=[i+1]
  else:
    d[i].append(i+1)
  
  if i+1 not in d:
    d[i+1]=[i]
  else:
    d[i+1].append(i)
d[x].append(y)
d[y].append(x)


for i in range(1,n):
  for j in range(i+1,n+1):
    lst[len(find_shortest_path(d,i,j))-1]+=1


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

Submission status: Runtime Error

Solution code:
l=[0] * (n-1)
for i in range(1,n):
    for j in range(i+1,n+1):
        #print(i,j)
        index=min(abs(y-j)+abs(x-i)+1,j-i)-1
        #print(index+1)
        l[index]=l[index]+1
for i in range(len(l)):
    print(l[i])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from collections import deque
readline = sys.stdin.readline

N, X, Y = map(int, readline().split())
X -= 1
Y -= 1

a = np.ones([N, N]) * 1e9

def test(n):
    b = np.ones([N]) * 1e9
    q = deque()

    q.append((n, 0))
    while len(q) > 0:
        n, d = q.popleft()
        if b[n] == 1e9:
            b[n] = d
            if n - 1 >= 0:
                q.append((n - 1, d + 1))
            
            if n + 1 < N:
                q.append((n + 1, d + 1))
            
            if n == X:
                q.append((Y, d + 1))
            elif n == Y:
                q.append((X, d + 1))
    
    return b

for n in range(N):
    a[n] = test(n)

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

for x in ans:
    print(x)

Submission status: Runtime Error

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra, floyd_warshall
setrecursionlimit(1000000)

# INF = float('inf')
INF = int(1e10)

def input():
    return stdin.readline()[:-1]

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

    cost = [[float("inf") for _ in range(N)] for _ in range(N)]
    for i in range(N - 1):
        cost[i][i + 1] = 1
        cost[i + 1][i] = 1
    cost[X - 1][Y - 1] = cost[Y - 1][X - 1] = 1

    G = csgraph_from_dense(cost, null_value=-1)
    counter = [0] * N
    for n in range(N):
        # mat = dijkstra(n, N, N, cost)
        mat = dijkstra(G, indices=n)
        for v in mat[n+1:]:
            counter[int(v)] += 1
        # print(mat)
    for v in counter[1:]:
        print(v)
    # print(*counter, end="\n")

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, X, Y = map(int, input().split())
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")

graph = np.zeros((N, 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

shortest_paths = shortest_path(csr_matrix(graph), directed=False, method="D", unweighted=True)
ans = [0] * (N - 1)
for i in range(N):
    for j in range(N):
        if i != j:
            ans[shortest_paths[i][j]] += 1
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import heapq

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    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

def warshall_floyd(n,d):
    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





n,x,y = m()

dp = [[mod for i in range(n)] for j in range(n)]

for i in range(n):
    dp[i][i] = 0

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

dp[x-1][y-1] = 1

dp[y-1][x-1] = 1


po = dijkstra(x-1,n,n,dp)

ppo = dijkstra(y-1,n,n,dp)

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

for i in range(n):
    for j in range(n):
        on = min(dp[i][j],po[i]+po[j],ppo[i]+ppo[j],po[i]+ppo[j] + 1,ppo[i]+po[j] + 1)
            #print(i,j,on)
            #print(ppp[i][j])
        ans[on] += 1
for i in range(1,n):
    print(ans[i]//2)

Submission status: Runtime Error

Solution code:
from collections import deque
N, X, Y = map(int, input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
    edge[i].append(i + 1)
    edge[i + 1].append(i)
edge[X-1].append(Y-1)
edge[Y-1].append(X-1)

cnt = [0] * (N - 1)


def search(i):
    node = deque([i])
    seen = [-1] * N
    seen[i] = 0

    while node:
        s = node.popleft()
        d = seen[s]
        for t in edge(s):
            if seen[t] == -1:
                seen[t] = d + 1
                if s < t:
                    cnt[d] += 1
                node.append(t)


for i in range(N - 1):
    search(i)
print(*cnt, sep="\n")

Submission status: Runtime Error

Solution code:
N, X, Y = map(int, input().split())
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")

graph = np.zeros((N, 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

shortest_paths = shortest_path(csr_matrix(graph), directed=False, method="D", unweighted=True)
ans = [0] * (N - 1)
for i in range(N):
    for j in range(N):
        if i != j:
            ans[shortest_paths[i][j]] += 1

Submission status: Runtime Error

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

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

d = [[1e+10]*N for i in range(N)] 

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

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

G = csgraph_from_dense(d, null_value=1e+10)
d = floyd_warshall(G)


for k in range(1, N):
    print(np.sum(d==k) // 2)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n,x,y;
	cin >> n >> x >> y;
	vector<vector<int> > d(n, vector<int>(n,-1));
	x--;y--;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			d[i][j] = min(min(abs(i-j), abs(i-x) + abs(j-y)+1), abs(i-y)+abs(j-x)+1);
		}
	}

	vector<int> count(n,0);
	for(int i = 0; i < n;i++)
	{
		for(int j = 0; j < n; j++)
		{
				// cout << d[i][j] << " " ;
				count[d[i][j]]++;
		}
		// cout << endl;
	}

	for(int i = 1; i < n; i++)
		cout << count[i]/2 << endl;

}

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
N, X, Y = map(int, input().split())
edges = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    edges[i][i + 1] = 1
    edges[i + 1][i] = 1
X -= 1
Y -= 1
edges[X][Y] = 1
edges[Y][X] = 1
res = shortest_path(csr_matrix(edges))
ans = defaultdict(int)
for i in range(N-1):
    for j in range(i+1, N):
        ans[int(res[i][j])] += 1
for k in range(1, N):
    print(ans[k])

Submission status: Runtime Error

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

cnt={}
for i in range(1,n+1):
  for j in range(i+1,n+1):
    if i <= x and y <= j:
      cnt[(j-y)-(x-i)+1] += 1
    else:
      cnt[j-i] += 1
      
for i in range(1,n):
  print(cnt[i])