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: Accepted

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

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

ans = defaultdict(lambda:0)
for i in range(N):
    d = dijkstra(graph,N,i)

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,X,Y = LI()

X -= 1
Y -= 1
d = defaultdict(int)
for i in range(N):
    for j in range(i+1,N):
        val = min(abs(X-i)+1+abs(Y-j), abs(X-j)+1+abs(Y-i), abs(i-j))
        d[val] += 1

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    x-=1
    y-=1
    ans=[0]*(n-1)
    for i in range(n-1):
        for j in range(i+1,n):
            d=min(j-i,abs(x-i)+abs(y-j)+1,abs(y-i)+abs(x-j)+1)
            ans[d-1]+=1
    for i in range(n-1):
        print(ans[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = [0] * N

for a in range(1, N+1):
    for b in range(a+1, N+1):
        t = b - a
        t2 = abs(X-a) + abs(Y-b) + 1
        t = t if t < t2 else t2
        ans[t] += 1

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

Submission status: Accepted

Solution code:
from collections import deque


def BFS(G, V, start):
    dist = [-1] * V
    que = deque([start])
    dist[start] = 0

    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)

    return dist


N, X, Y = map(int, input().split())
G = [[] for _ 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)

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

for ans in Dist[:N-2]:
    print(ans//2)
print(0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

graph = [[] for _ in range(N)]
for i in range(N-1):
    graph[i].append(i+1)
    graph[i+1].append(i)

graph[X].append(Y)
graph[Y].append(X)

def bfs(a):
    D = [-1]*N
    D[a] = 0
    q = [a]
    while q:
        qq = []
        for p in q:
            for np in graph[p]:
                if D[np] == -1:
                    D[np] = D[p] + 1
                    qq.append(np)
        q = qq
    return D

ans = [0]*(N-1)
for n in range(N):
    D = bfs(n)
    for m in range(N):
        if m == n: continue
        ans[D[m]-1] += 1

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

Submission status: Accepted

Solution code:
from itertools import combinations
n,x,y = map(int,input().split())
x -= 1
y -= 1
ans = [0]*n
for i,j in combinations(range(n),2):
  dist = min(j-i,abs(i-x)+abs(j-y)+1)
  ans[dist-1] += 1
anss = ans[:n-1]
print(*anss,sep="\n")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N, X, Y = map(int, read().split())

dist = []
for i in range(1, N + 1):
    x = np.arange(1, N + 1)
    # 直接
    d1 = np.abs(x - i)
    # i -> X -> Y -> x
    d2 = np.abs(i - X) + np.abs(Y - x) + 1
    # i -> Y -> X -> x
    d3 = np.abs(i - Y) + np.abs(X - x) + 1
    d = np.minimum(np.minimum(d1, d2), d3)
    dist.append(d)

dist = np.concatenate(dist)
count = np.bincount(dist, minlength=N)
print('\n'.join((count[1:] // 2).astype(str)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import Counter
from itertools import combinations
import sys


def d(i: int, j: int, X: int, Y: int):
    res = min(
        abs(i - j),
        abs(i - X) + 1 + abs(Y - j),
        abs(i - Y) + 1 + abs(X - j),
    )
    return res


def solve(N: int, X: int, Y: int):
    X -= 1
    Y -= 1
    ctr = Counter(
        d(i, j, X, Y)
        for i, j in combinations(range(N), 2)
    )
    for di in range(1, N):
        print(ctr[di])


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: Accepted

Solution code:
N,X,Y = map(int,input().split())
ans = [0] * (N-1)
for i in range(1,N):
    for j in range(i+1,N+1):
        d = min(j-i, abs(X-i) + abs(j-Y) + 1)
        ans[d-1] += 1
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    if S[2]==S[3] and S[4]==S[5]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    X = I()
    ans = 0
    ans += (X//500) * 1000
    X %= 500
    ans += (X//5) * 5
    print(ans)
    return

def examC():
    K, N = LI()
    A = LI()
    L = [0]*N
    L[0] = K-A[-1] + A[0]
    for i in range(1,N):
        L[i] = A[i]-A[i-1]
    ans = sum(L) - max(L)
    #print(L)
    print(ans)
    return

def examD():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N, X, Y = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        V[i].append(i+1)
        V[i+1].append(i)
    V[X-1].append(Y-1)
    V[Y-1].append(X-1)
    #print(V)
    ans = [0]*(N-1)
    for i in range(N):
        L = bfs(N,i,V)
        for l in L:
            if l==0:
                continue
            ans[l-1] += 1
    for v in ans:
        print(v//2)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [v_to, ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        _, v_from = heappop(heap)
        for v_to in graph[v_from]:
            dist_cand = dist[v_from] + 1
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


n, x, y = map(int, input().split())
x -= 1
y -= 1
g = [[] for _ in range(n)]
for i in range(n):
    if i - 1 >= 0:
        g[i].append(i - 1)
    if i + 1 < n:
        g[i].append(i + 1)
g[x].append(y)
g[y].append(x)

d = [dijkstra(g, n, i) for i in range(n)]
# print(*d, sep='\n')

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

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

Submission status: Accepted

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

ans=[0]*N
for i in range(1,N):
    for j in range(i+1,N+1):
        num=min(j-i,abs(j-Y)+abs(i-X)+1)
        ans[num]+=1

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

Submission status: Accepted

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

x -= 1
y -= 1

k = [0] * n

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

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

Submission status: Accepted

Solution code:
from collections import deque
n, x, y = map(int, input().split())
G = [[] for _ 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)
ans = [0]*n
for i in range(n):
    que = deque([i])
    dist = [-1]*n
    dist[i] = 0
    while que:
        v = que.popleft()
        for nv in G[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                que.append(nv)
    for i in range(n):
        ans[dist[i]]+=1
for i in range(n):
    ans[i]//=2
print(*ans[1:], sep = '\n')

Submission status: Accepted

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

def dis(a, b):
    ret = abs(a - b)
    ret = min(ret, abs(a - x) + 1 + abs(b - y))
    ret = min(ret, abs(a - y) + 1 + abs(b - x))
    return ret

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

for x in ans:
    print(x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

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


def dfs(x, r):
	for v in adj[x]:
		if dist[r][v] > dist[r][x] + 1:
			dist[r][v] = dist[r][x] + 1
			dfs(v, r)
	return

dist = [[10000 for _ in range(n)] for _ in range(n)]
for i in range(n):
	dist[i][i] = 0
	dfs(i, i)

ans = [0 for _ in range(n)]
for i in range(n):
	for j in range(i+1, n):
		ans[dist[i][j]] += 1
print(*ans[1:], sep="\n")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, x, y = LI()
    dist = [[inf] * n for i in range(n)]
    edg = [[] for i in range(n)]
    for i in range(1, n):
        edg[i].append(i - 1)
        edg[i - 1].append(i)
    edg[x - 1].append(y - 1)
    edg[y - 1].append(x - 1)
    for i in range(n):
        dist[i][i] = 0
        q = [(0, i)]
        while q:
            s, p = heappop(q)
            for e in edg[p]:
                if dist[i][e] > dist[i][p] + 1:
                    dist[i][e] = dist[i][p] + 1
                    heappush(q, (dist[i][e], e))
    ans = [0] * n
    for i in range(n):
        for j in range(n):
            if dist[i][j] != inf:
                ans[dist[i][j]] += 1
    for ai in ans[1:]:
        print(ai//2)
    
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N, X, Y = map(int, input().split())
    L = Y-X+1
    ans = [0] * N
    for i in range(1, N):
        for j in range(i, N+1):
            d = min(j - i, abs(i-X) + abs(j-Y) + 1, abs(i-Y) + abs(j-X) + 1)
            ans[d] += 1
    for i in range(1, N):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,x,y = LI()
    x -= 1
    y -= 1
    ans = [0]*n
    for i in range(n):
        k = abs(x-i)
        for j in range(i+1,n):
            d = min(j-i,k+abs(j-y)+1)
            ans[d] += 1
    for i in ans[1:]:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, x, y = na()
x -= 1
y -= 1
anss = [0] * n
for i in range(n):
    for j in range(i+1, n):
        d = min(j-i, 1 + abs(x-i) + abs(j-y))
        anss[d] += 1

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

Submission status: Accepted

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

def dist(a, b):
    return min(abs(b-a), abs(X-a) + 1 + abs(b-Y), abs(Y-a) + 1 + abs(b-X))

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

for a in ANS[1:]:
    print(a)

Submission status: Runtime Error

Solution code:
from collections import deque
n,x,y = map(int,input().split())
next = [[] for i in range(n)]
next[0].append(1)
next[n-1].append(n-2)
next[x-1].append(y-1)
next[y-1].append(x-1)
for i in range(1,n-1):
  next[i].append(i-1)
  next[i].append(i+1)

ans = [0] *(n-1)

for j in range(n):
  mark = ['inf']*(n)
  que = deque([j])
  mark[j] = 0
 
  while que:
    q = que.popleft()
    for k in next[q]:
      if mark[k] == 'inf':
        mark[k] = mark[q] + 1
        que.append(k)
  
  for l in range(0,n):
    if mark[l] != 0:
      ans[mark[l]-1] += 1

import numpy as np    
arr = np.array(ans) //2
for x in arr:
  print(x)

Submission status: Runtime Error

Solution code:
from numba.np.ufunc import parallel
from numba import njit,prange


@njit(cache=True,parallel=True)
def solve(n,x,y):
    ans = [0] * (n - 1)
    for i in prange(n):
        for j in prange(n):
            c = min(abs(i - j), abs(i-x)+abs(j-y)+1,abs(i-y)+abs(j-x)+1)
            if c:
                ans[c-1] += 1
    return ans


n, x, y = map(int, input().split())
x -= 1
y -= 1
ans = solve(n,x,y)
for ai in ans:
    print(ai//2)

Submission status: Runtime Error

Solution code:
from networkx.drawing.nx_pylab import draw_networkx
import networkx as nx
import matplotlib.pyplot as plt

n,x,y = map(int,input().split())
G = nx.Graph()
G.add_nodes_from(list(range(n)))
inf = 10**10
D = [[inf]*n for i in range(n)]
for i in range(n-1):
    #G[i].append(i+1)
    #G[i+1].append(i)
    G.add_edge(i,i+1)
    D[i][i+1] = 1
    D[i+1][i] = 1
G.add_edge(x-1,y-1)
D[x-1][y-1] = 1
D[y-1][x-1] = 1

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

s = set()
ans = [0]*(n-1)
paths = nx.shortest_path(G)
for i in range(n):
    for j in range(n):
        if (min(i,j),max(i,j)) in s:
            pass
        else:
            s.add((min(i,j),max(i,j)))
            c = len(paths[i][j])-1
            if c:
                ans[c-1] += 1
for ai in ans:
    print(ai)

Submission status: Runtime Error

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

for k in range(1, N):
    count = 0
    for i, j in combinations(range(1, N+1), 2):
        if min(j - i, abs(X-i)+1+abs(Y-j)) == k:
            count += 1
    print(count)

Submission status: Runtime Error

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

    cost = [[float("inf")]*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


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

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



def dijkstra(s):
    #sは始点、usedは各頂点が使われたかどうか、dは視点から各頂点への最短距離
    d = [float("inf")]*n
    used = [False]*n
    d[s] = 0

    while True:
        #pは最短距離が確定した頂点
        p = -1
        #まだ使われていない頂点のうち距離が最小のものを探す
        for i in range(n):
            if (not used[i]) and (p==-1 or d[i]<d[p]):
                p = i
        
        if p==-1:
            break
        used[p] = True

        for i in range(n):
            d[i] = min(d[i], d[p]+cost[p][i])

    return d

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

def solve(N, X, Y):
    def bfs(v):
        q = [v]
        Distance = [-1] * (N+1)
        Distance[v] = 0
        distance = 1
        while q:
            q_new = []
            for v in q:
                u = v-1
                if u >= 1 and Distance[u] == -1:
                    Distance[u] = distance
                    q_new.append(u)
                u = v+1
                if u <= N and Distance[u] == -1:
                    Distance[u] = distance
                    q_new.append(u)
                if v == X:
                    u = Y
                    if Distance[u] == -1:
                        Distance[u] = distance
                        q_new.append(u)
                elif v == Y:
                    u = X
                    if Distance[u] == -1:
                        Distance[u] = distance
                        q_new.append(u)
            distance += 1
            q = q_new
        return Distance

    Ans = np.zeros(N, dtype=np.int64)
    for v in range(1, N+1):
        Distance = bfs(v)
        for d in Distance[v+1:]:
            Ans[d] += 1
    return Ans[1:]

numba_compile([
    [solve, "i8[:](i8,i8,i8)"]
])

N, X, Y = map(int, input().split())
Ans = solve(N, X, Y)
print("\n".join(map(str, Ans.tolist())))

Submission status: Runtime Error

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n, x, y = map(int, input().split())
    tree = [None]*n

    for i in range(1, n):
        for j in range(i+1, n+1):
            # if i <= x and j >= y:
            #     tree[i - 1][j - 1] = j-i-(y - x - 1)
            # elif i <= x and j < y:
            #     tree[i - 1][j - 1] = x - i + min(y - j + 1, j - x)
            # elif i > x and j >= y:
            #     tree[i - 1][j - 1] = j - y + min(i-x+1, y-i)
            # else:
            #     tree[i - 1][j - 1] = j-i
            tree[i - 1].append = min(j-i, abs(x-i) +
                                     1+abs(j-y), abs(y-i)+1+abs(j-x))

    for k in range(1, n):
        ans = 0
        for i in range(n):
            ans += tree[i].count(k)
        print(ans)

Submission status: Runtime Error

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time

n, x, y = map(int, input().split())
tree = [[0] * n for i in range(n)]

for i in range(1, n):
    for j in range(i+1, n+1):
        # if i <= x and j >= y:
        #     tree[i - 1][j - 1] = j-i-(y - x - 1)
        # elif i <= x and j < y:
        #     tree[i - 1][j - 1] = x - i + min(y - j + 1, j - x)
        # elif i > x and j >= y:
        #     tree[i - 1][j - 1] = j - y + min(i-x+1, y-i)
        # else:
        #     tree[i - 1][j - 1] = j-i
        tree[i - 1][j - 1] = min(j-i, abs(x-i) +
                                    1+abs(j-y), abs(y-i)+1+abs(j-x))

for k in range(1, n):
    ans = 0
    for i in range(n):
        ans += tree[i].count(k)
    print(ans)

Submission status: Runtime Error

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
#sys.setrecursionlimit(10**6)
#input = sys.stdin.readline


def main():
    n, x, y = map(int, input().split())
    tree = [[0] * n for i in range(n)]

    for i in range(1, n):
        for j in range(i+1, n+1):
            # if i <= x and j >= y:
            #     tree[i - 1][j - 1] = j-i-(y - x - 1)
            # elif i <= x and j < y:
            #     tree[i - 1][j - 1] = x - i + min(y - j + 1, j - x)
            # elif i > x and j >= y:
            #     tree[i - 1][j - 1] = j - y + min(i-x+1, y-i)
            # else:
            #     tree[i - 1][j - 1] = j-i
            tree[i - 1][j - 1] = min(j-i, abs(x-i) +
                                     1+abs(j-y), abs(y-i)+1+abs(j-x))

    for k in range(1, n):
        ans = 0
        for i in range(n):
            ans += tree[i].count(k)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
ans=[0]*n

for j in range(1,n+1):
    dict=[-1]*(n+1)
    que=deque()
    que.append(j)
    dict[j]=0
    while que:
        t=que.popleft()
        for k in map[t]:
            if dict[k]==-1:
                dict[k]=dict[t]+1
                que.append(k)
    for l in range(1,n+1):
        ans[dict[l]]+=1
for m in range(1,n):
    print(ans[m]//2)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i++)
#define repran(i, a,b) for (int i = a; i<b;i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;
using LP = pair<ll,ll>;
using P = pair<ll,int>;
ll mod = 998244353;

int main()
{
    int n, x, y;
    cin>> n >> x>>y;
    x--;y--;
    vector<int> table(n,0);
    rep(i, n) rep(j,i){
        int tmp = min(i-j, abs(x-i)+abs(y-j)+1);
        tmp = min(tmp,abs(x-j)+abs(y-i)+1);
        table[tmp]++;
    }
    repran(i, 1, n) cout << table[i] << endl;
}

Submission status: Runtime Error

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

res = deque()

for x in range(1, N):
    for y in range(x + 1, N+1):
        res.append(min([abs(x-y), 1 + abs(X-x) + abs(Y-y)))
resd = Counter(res)

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
from itertools import chain
from collections import Counter


V, X, Y = map(int, input().split())                             # V:頂点数 E:辺の数 r:始点

edge = np.array([[i,i+1,1] for i in range(1,V)] + [[X, Y,1]], dtype = np.int64).T

graph = csr_matrix((edge[2], (edge[:2] - 1)), (V, V))           # [[辺の左端],[辺の右端],[辺の距離]] の形で渡す
# graph = csr_matrix((edge[2], (edge[:2] )), (V, V))           # 番号のデクリメントが不要な場合


d = floyd_warshall(graph, directed = False)                         # 有効グラフの場合は directed = True とする。

nagativity = False                                             # 負のサイクルかどうかを判定
for i in range(V):
    if d[i][i] < 0:
        nagativity = True
if nagativity:
    print('NEGATIVE CYCLE')
else:
    d = [['INF' if i == float("inf") else int(i) for i in l ] for l in d]   # numpy.float64をintに変換し、inf をどのように記述するかを指定

res = Counter(chain.from_iterable(d))

for i in range(1,V):
    print(res.get(i,0)//2)

Submission status: Runtime Error

Solution code:
n,x,y = map(int,input().split())
cnt_l = [0]*n
from collections import deque
# 幅優先探索
def bfs(start):  
  queue = deque()
  queue.append(start)
  step_counts = [-1]*(n+1)
  step_counts[start] = 0
  while(queue):
    i = queue.popleft()
    cnt = step_counts[i]
    # 隣のグラフを取得
    if(i==x):
      nex_l = (i-1,y,i+1)
      elif(i==y):
        nex_l = (i-1,x,i+1)
      else:
        nex_l = (i-1,i+1)

      cnt += 1
      for j in nex_l:
        # 端より先だと止める
        if(j < 1 or n < j):
          continue
          # 訪問済みだと止める
          if(step_counts[j]!=-1):
            continue
            queue.append(j)
            step_counts[j] = cnt
            cnt_l[cnt] += 1


for i in range(1,n+1):
  bfs(i)
 
for i in range(1,n):
  # (a,b),(b,a)のペアがあるため//2
  print(cnt_l[i]//2)

Submission status: Runtime Error

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

t = [0] * (N - 1)
for i in range(1, N):
    for j in range(i + 1, N + 1):
        t[min(j - i, abs(X - i) + 1 + abs(Y - j)) - 1] += 1
#print('\n'.join(map(str, t)))
print(*result, sep='\n')

Submission status: Runtime Error

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

adj = [[] for i in range(N)]
for i in range(N):
    if i != 0 and i != N-1:
        adj[i].append(i-1)
        adj[i].append(i+1)
    elif i == 0:
        adj[i].append(1)
    else:
        adj[i].append(N-2)
    if i == X-1:
        adj[i].append(Y-1)
    if i == Y-1:
        adj[i].append(X-1)
ans = [0 for i in range(N-1)]
dists = [[] for i in range(N)]
for i in range(N):
    dist = [-1]*N
    q = deque([i])
    dist[i] = 0
    while q:
        l = q.popleft()
        d = dist[l]
        for w in adj[l]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            q.append(w)
    dists[i].append(dist)
for k in range(1, N):
    for d in dists:
        ans[k] += d.count(k)
for i in range(N-1):
    ans[i] = ans[i]//2
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
N = int(input())
c=list(map(int, input().split()))
c.sort()

count = 0
while count<len(c):
  for i,b in enumerate(c):
    if i == count:
      continue
      
    print(i,b)
    if b%c[count]==0:
      c.pop(i)
      print(c)
  count+=1

print(c)

Submission status: Runtime Error

Solution code:
xfrom collections import deque, defaultdict
N, X, Y = map(int, input().split())  # N個の頂点, XとYが繋がっている

graph = [[] for _ in range(N)]
for i in range(N-1):
    graph[i].append(i+1)
    graph[i+1].append(i)
X -= 1
Y -= 1
graph[X].append(Y)
graph[Y].append(X)
# print(graph)

# 最後に//2すれば良い
ans = defaultdict(int)
for i in range(N):
    q = deque()
    # 開始のノード
    q.append(i)
    visited = [False]*N
    visited[i] = True
    distant = [100000] * N
    distant[i] = 0
    while len(q):
        v = q.popleft()
        for e in graph[v]:
            if visited[e]:
                continue
            distant[e] = distant[v] + 1
            ans[distant[e]] += 1
            visited[e] = True
            q.append(e)
    # 始点iからの幅優先探索完了
# print(ans)
for i in range(1, N):
    print(ans[i]//2)

Submission status: Runtime Error

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

ans = [0] * N
 
for i in range(N-1):
  for j in range(i+1, N):
    d = min(j-i, abs(i-X) + abs(j-Y) + 1)
    ans[d] += 1

print(*ans([1:], sep='\n'))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from sys import stdin
	def input() : return stdin.readline().rstrip()
	def mips():
    	return map(int,input().split())
    sys.setrecursionlimit(10**9)
    N,X,Y = mips()
    G = dict()
    for i in range(0,N):
        G[i] = []
    for i in range(0,N-1):
        G[i].append(i+1)
        G[i+1].append(i)
    G[X-1].append(Y-1)
    G[Y-1].append(X-1)
    ans = [0 for _ in range(N)]
    #Question : for k = 1,...,N-1 : 
    #整数の組(i,j)(1≤i<j≤N)であって、Gにおいて頂点iと頂点jの最短距離がkであるようなものの数を求めてください
    def bfs(v,G,queue,dist):
        seen[v] = True
        for vertex in G[v]:
            if seen[vertex]:
                continue
            elif vertex in queue:
                continue
            queue.append(vertex)
            dist[vertex] = dist[v] + 1
        for elements in queue:
            queue.remove(elements)
            bfs(elements,G,queue,dist)
    for k in range(0,N):
        dist = [-1 for _ in range(N)]
        dist[k] = 0
        seen = [False for _ in range(N)]
        queue = []
        bfs(k,G,queue,dist)
        #print(dist)
        for j in range(1,N):
            a = dist.count(j)
            ans[j-1] += a
    for j in range(1,N):
        print(ans[j-1])
if __name__ == '__main__':
    main()