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 scipy.sparse.csgraph import dijkstra
import sys
def main():
	input = sys.stdin.readline

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

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

	route[x-1][y-1] = 1
	route[y-1][x-1] = 1
	route = tuple(route)
	#res = shortest_path(route, unweighted=False,directed=False)
	res = tuple(dijkstra(route, directed=False))

	ans = [0 for _ in range(n)]
	for i in range(n):
		for j in range(i,n):
			ans[int(res[i][j])] += 1

	for i in range(1,n):
		print(ans[i])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

for s in range(n - 1):
    for e in range(s+1, n):
        d = e-s
        if (e <= x)or(s >= y):
            kl[d - 1] += 1
        else:
            kl[min(d, abs(s-x)+abs(e-y)+1)-1] += 1

for i in kl:
    print(i)

Submission status: Accepted

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

lis = [0]*(n-1)
for i in range(n):
    disxi = min(abs(x-1-i), abs(y-1-i))
    for j in range(i+1, n):
        a = j-i
        if a == 1:
            dist = 1
        else:
            b = disxi + 1 + min(abs(y-1-j), abs(x-1-j))
            dist = min(a, b)
        lis[dist-1] += 1

for i in lis:
    print(i)

Submission status: Accepted

Solution code:
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)

ans_list = [0] * N
# 各頂点からの最短経路長を計算
for i in range(N):
    queue = g[i]
    seen = [False] * N
    length = 0
    while queue:
        length += 1
        add = []
        for qi in queue:
            if seen[qi] == False:
                if i < qi:
                    ans_list[length] += 1
                seen[qi] = True
                add += g[qi]
        queue = list(set(add))

# 答えの出力
for k in range(1, N):
    print(ans_list[k])

Submission status: Accepted

Solution code:
def resolve():
    N, X, Y = map(int, input().split())
    X, Y = X-1, Y-1
    S = [0]*(N-1)
    for i in range(N):
        for j in range(i+1, N):
            if i <= X and Y <= j:
                diff = X-i+j-Y+1
            elif i > X and j >= Y:
                diff = min(j-i, i-X+j-Y+1)
            elif i <= X and j < Y:
                diff = min(j-i, X-i+Y-j+1)
            else:
                diff = min(j-i, i-X+Y-j+1)
            S[diff-1] += 1

    for dc in S:
        print(dc)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
#print(N)
dlist = [0]*N
for k in range(1, N):
    for i in range(N-k):
        j = i + k
        usek = abs(X -i)+1+abs(j-Y)
        curk = min(k, usek)
        dlist[curk] += 1

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict

N,X,Y=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]	#隣接リスト

for i in range(1,N):
    al[i].append(i+1)
    al[i+1].append(i)

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

#カウント
C=defaultdict(lambda: 0)

for start in range(1,N+1):
    #距離
    d=[ float("inf") for _ in range(N+1) ]
    d[start]=0

    #スタートからBFS
    #訪問した頂点
    Visit=[ 0 for _ in range(N+1) ]
    q=deque()
    q.append(start)
    Visit[start]=1

    while q:
        fro=q.popleft()
        for to in al[fro]:
            if Visit[to]==0:
                Visit[to]=1	#訪問済みVisitに1をセットする。4行上のpopleftの直後でVisitをセットすると同じ頂点がqに入り、TLEする
                q.append(to)
                d[to]=min(d[to],d[fro]+1)

    for i in range(start+1,N+1):
        C[d[i]]+=1

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

n, x, y = map(int, input().split())
ans = [0]*(n)

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


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

Submission status: Accepted

Solution code:
n, x, y = list(map(int, input().split()))
cnt = []
for i in range(n-1):
  cnt.append(0)
for i in range(1,n):
  for j in range(i+1, n+1):
    if i <= x and y <= j:
      cnt[x-i+j-y] += 1
    elif i <= x:
      a = min(j-i-1, x-i+y-j)
      cnt[a] += 1
    elif y <= j:
      a = min(j-i-1, i-x+j-y)
      cnt[a] += 1
    else: 
      a = min(j-i-1, i-x+y-j) 
      cnt[a] += 1
for i in range(n-1):
  print(cnt[i])

Submission status: Accepted

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

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):
        ans[min(j-i,1+abs(i-x)+abs(j-y))-1]+=1

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

Submission status: Accepted

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

d = {}

for i in range(1, N):
    for j in range(i + 1, N + 1):
        if j >= Y and i <= X:
            d[(i, j)] = min(j - i - (Y - X) + 1, j - i)    
        elif i <= X:
            d[(i, j)] = min(j - i, X - i + 1 + Y - j)    
        elif j >= Y:
            d[(i, j)] = min(j - i, i - X + 1 + j - Y)    
        else:
            d[(i, j)] = min(j - i, i - X + 1 + Y - j)

ans = [0] * (N - 1)

for k, v in d.items():
    ans[v - 1] += 1

for v in ans:
    print(v)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque

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

d = defaultdict(set)
for i in range(N-1):
    d[i].add(i+1)
    d[i+1].add(i)
d[X-1].add(Y-1)
d[Y-1].add(X-1)


cost = [[N]*N for _ in range(N)]

q = deque()

for i in range(N):
    q.append((i, 0))
    cost[i][i] = 0

    while q:
        u, st = q.popleft()

        for v in d[u]:
            if v != u and cost[i][v] > st+1:
                cost[i][v] = st+1
                q.append((v, st+1))

res = Counter()
for i, c in enumerate(cost):
    res += Counter(c[:i])

for i in range(N - 1):
    print(res[i + 1])

Submission status: Accepted

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


nums = [None] + [0 for _ in range(n-1)]
## A
#numa = x-1
#if numa >= 2:
#    for i in range(1, numa):
#        nums[i] = numa - i
#
## B
#numb = n-y+1
#if numb >= 2:
#    for i in range(1, numb):
#        nums[i] = numb - i
#
## C
#numc = y - x + 1
#if numc % 2 == 0:
#    nums[numc//2] += (1 * numc) // 2
#
#for i in range(1, (numc+1)//2):
#    nums[i] += (2 * numc) // 2
#
## AB

# X
numx = n - (y-x-1)
if numx >= 2:
    for i in range(1, numx):
        nums[i] = numx - i

x1 = x + 1
y2 = y - 1
# c1+c2
for i in range(x1, y2+1):
    for j in range(i+1, y2+1):
        d = min(j-i, y-j + 1 + i-x)
        #print(i, j, d)
        nums[d] += 1

# x1+c1+c2
for i in range(1, x+1):
    for j in range(x1, y2+1):
        d = min(j-i,x-i+1+y-j)
        #print(i, j, d)
        nums[d] += 1

# x2+c1+c2
for i in range(y, n+1):
    for j in range(x1, y2+1):
        #print(i, j, i-j, i-y+1+j-x)
        d = min(i-j, i-y+1+j-x)
        #print(i, j, d)
        nums[d] += 1

nums = nums[1:]
for num in nums:
    print(num)

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
r = X - 1
l = N - Y
m = Y - X + 1
for i in range(1, N):
    ans = 0
    # mid ok 
    if i * 2 == m:
        ans += i
    elif i * 2 < m:
        ans += m
    # right
    ans += max(0, r + 1 - i)
    for j in range(1, r+1):
        if j >= i:
            continue
        diff = i - j
        # circle
        if diff * 2 == m:
            ans += 1
        elif diff * 2 < m:
            ans += 2
        # outer
        if diff - 1  >= 1 and diff - 1 <= l:
            ans += 1
    # left
    ans += max(0, l + 1 - i)
    for j in range(1, l+1):
        if j >= i:
            continue
        diff = i - j
        # circle
        if diff * 2 == m:
            ans += 1
        elif diff * 2 < m:
            ans += 2
    print(ans)

Submission status: Accepted

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

lists = [0 for i in range(N-1)]
for i in range(1,Y):
    for j in range(i+1,N+1):
        if i <= X and Y <= j:
            pro = j-i-dis+1
            lists[pro-1] += 1
        elif i <= X and X <= j <= Y:
            pro = X+Y-i-j+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        elif X <= i <= Y and Y <= j:
            pro = i+j-X-Y+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        elif X <= i <= Y and X <= j <= Y:
            pro = i-j-X+Y+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        else:
            lists[j-i-1] += 1

for i in range(1,N-Y+1):
    lists[i-1] += N-Y-i+1
    
for i in lists:
    print(i)

Submission status: Accepted

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

l = [[] for _ in range(n)]

for i in range(n):
    if (i != n - 1):
        l[i].append(i + 1)
    if (i == x - 1):
        l[i].append(y - 1)

kl = [0] * (n - 1)

for s in range(n - 1):
    for e in range(s+1, n):
        d = e-s
        if (e <= x)or(s >= y):
            kl[d - 1] += 1
        else:
            kl[min(d, abs(s-x)+abs(e-y)+1)-1] += 1

for i in kl:
    print(i)

Submission status: Accepted

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
from collections import Counter

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

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

# l = [[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0],[0,1,1,0,1],[0,0,0,1,0]]

l = [[0]*n for i 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
# l.append([x,y])

a = np.array(l)
ans = shortest_path(a,method ="D")
ans_counter = Counter(flatten_2dim(ans))
# values = ans_counter.values()
# print(l)
# print(ans)
for i in range(1,n):
    print(int(ans_counter[i]/2))

# print(ans_counter[1])
# print(values)

Submission status: Accepted

Solution code:
n,x,y = map(int,input().split())
x -= 1
y -= 1
dis = y-x
a = [0 for _ in range(n-1)]
for i in range(n-1):
  for j in range(i+1,n):
    if(i<j<=x or y<=i<j):
      a[j-i-1] += 1
    elif i<=x and y<=j:
      a[j-i-dis] += 1
    elif i<x and x<=j<y:
      a[min(j,y-(j-x)+1)-i-1] += 1
    elif x<i<=y and y<j:
      a[j-max(i,y-(i-x)+1)] += 1
    elif x<=i<=y and x<=j<=y:
      a[min(j-i,i+(y-x)-j+1)-1] += 1
for i in a:
  print(i)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
5 2 4
'''

def solve(n,x,y):
	adj = [[] for i in range(n+1)]
	adj[x].append(y)
	adj[y].append(x)
	for i in range(1,n):
		adj[i].append(i+1)
		adj[i+1].append(i)
	# print(adj)
	ans = []
	d = {}
	for i in range(1,n):
		d[i] = 0
	for k in range(1,n+1):
		q = [k]
		dis = [maxsize]*(n+1)
		dis[k] = 0
		while(q):
			src = q.pop()
			for nn in adj[src]:
				# if(nn > k or nn == X or nn == Y):
				if(dis[nn] > dis[src]+1):
					# if(src == 4):
						# print('src:',src,'nn:',nn)
					dis[nn] = dis[src] + 1
					q.append(nn)
				# else:
				# 	dis[nn] = 
			# if(k == 3):
			# 	print('src:',src)
			# 	print('dis:',dis)
		curr = 0
		# if(k == 3):
		# print('k:',k,dis)
		for ii in range(k+1,n+1):
			d[dis[ii]] += 1
	return d

N,X,Y = list(map(int, stdin.readline().rstrip().split()))
ans = solve(N,X,Y)
for i in range(1,N):
	print(ans[i])

Submission status: Accepted

Solution code:
n,x,y=map(int,input().split())
ans=[0]*n #0はダミー
for i in range(1,n):
    for j in range(n+1):
        if j<=i:
            continue
        a=j-i
        b=abs(x-i)+1+abs(y-j)
        aa=min(a,b)
        ans[aa]+=1

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

Submission status: Accepted

Solution code:
import numpy as np
n, x, y =  list(map(int, input().split()))

# n, x, y = 6, 1, 6

r = y - x - 1
left = x
right = n - y + 1
base = left + right
arr = np.array([0] * (n - 1))
for k in range(base):
    arr[k] += base - k - 1
    
r += 2
if r % 2 == 0:
    arr_r = [r] * ((r // 2) - 1) + [r // 2]
else:
    arr_r = [r] * (r // 2)
    
r -= 2
for k in range(len(arr_r)):
    arr[k] += arr_r[k]

#print(arr_r)
# for k in range(r):
#     arr[k] += r - k - 1

if r % 2 == 0:
    arr_r = [1] + [2] * ((r // 2) - 1)  + [1]
else:
    arr_r = [1] + [2] *(r // 2)
    
#print(arr_r)

arr = np.array(arr)
if right > 1:
    for k in range(1, right):
        arr[k : k + len(arr_r)] += arr_r
if left > 1:
    for k in range(1, left):
        arr[k : k + len(arr_r)] += arr_r
arr[0] -= 1
for a in arr:
    print(a)

Submission status: Accepted

Solution code:
import sys

from collections import Counter, defaultdict, deque

input = sys.stdin.readline

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


def bfs(source):
    q = deque([source])
    dist = {source: 0}
    while q:
        i = q.popleft()
        d = dist[i]
        nbr = []
        if i - 1 >= 1:
            nbr.append(i - 1)
        if i + 1 <= N:
            nbr.append(i + 1)
        if i == X:
            nbr.append(Y)
        if i == Y:
            nbr.append(X)
        for j in nbr:
            if j not in dist:
                q.append(j)
                dist[j] = d + 1
    return dist


count = Counter()
for i in range(1, N + 1):
    dist = bfs(i)
    assert len(dist) == N
    for j, d in dist.items():
        if i < j:
            count[d] += 1

ans = []
for k in range(1, N):
    ans.append(str(count[k]))
print('\n'.join(ans))

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
result = [0] * (N)
for i in range(1, N):
    for j in range(i + 1, N + 1):
        if i <= X:
            if j <= X:
                len = j - i
            elif X < j < Y:
                if (j - X) < (Y - j + 1):
                    len = j - i
                else:
                    len = (X - i) + (Y - j + 1)
            elif Y <= j:
                len = (X - i) + 1 + (j - Y)
        elif X < i < Y:
            if j < Y:
                if (j - i) < (i - X) + 1 + (Y - j):
                    len = j - i
                else:
                    len = (i - X) + 1 + (Y - j)
            elif Y <= j:
                if (i - X + 1) < (Y - i):
                    len = (i - X) + 1 + (j - Y)
                else:
                    len = j - i
        elif Y <= i:
            len = j - i
        result[len] += 1
for i in range(1, N):
    print(result[i])

Submission status: Accepted

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

def dist(i, j):
  return min(j - i, abs(i-x) + abs(j-y) + 1)

distList = [0] * (n-1)

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

for distItem in distList:
  print(distItem)

Submission status: Accepted

Solution code:
nxy = input().split()
n = int(nxy[0])
x = int(nxy[1])
y  = int(nxy[2])
r = [0 for i in range(1,n)] 


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

Submission status: Accepted

Solution code:
def main():
    import sys
    import collections
    
    N, X, Y = map(int, sys.stdin.readline().split())
    
    dist_list = []
    
    if X == 1 and Y == N:
        for i in range(1, N):
            for j in range(i + 1, N + 1):
                dist = min(j - i, N - j + i)
                dist_list.append(dist)
        
        c = collections.Counter(dist_list)
        for i in range(1, N):
            print(c[i])
    
    else:
        for i in range(1, N):
            for j in range(i + 1, N + 1):
                if j <= X or i >= Y:
                    dist_list.append(j - i)
                else:
                    dist = min(j - i, abs(X - i) + abs(j - Y) + 1)
                    dist_list.append(dist)
                    
        
        c = collections.Counter(dist_list)
        for i in range(1, N):
            print(c[i])
            
if __name__ == '__main__':
    main()

Submission status: Accepted

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

sets=[]
for i in range(n-1):
  sets.append([])

for i in range(n):
  for j in range(i+1,n):
    a=abs(x-(i+1))
    b=abs(y-(j+1))
    c=a+b+1
    if c>=(j-i):
      sets[j-i-1].append(1)
    else:
      sets[c-1].append(1)

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

Submission status: Accepted

Solution code:
import queue
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = [0]*n
    t = [[i+1, i-1] for i in range(n)]
    t[x].append(y)
    t[y].append(x)
    for i in range(n):
        for j in range(i+1, n):
            if j <= x:
                ans[j-i] += 1
            elif j <= y:
                buf = min(j-i, abs(i-x) + 1 + (y-j))
                ans[buf] += 1
            else:
                buf = min(y-i, abs(x-i)+1)
                ans[buf + (j-y)] += 1
    for i in range(1, n):
        print(ans[i])
if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = dict()
for k in range(1, N):
    ans[k] = 0
for i in range(1, N):
    for k in range(i+1, N+1):
        dif1 = k - i
        dif2 = abs(X-i) + 1 + abs(Y-k)
        dif = min([dif1, dif2])
        ans[dif] += 1
for k, v in ans.items():
    print(v)

Submission status: Accepted

Solution code:
inputNumbers=input()
N=int(inputNumbers.split(" ")[0])
X=int(inputNumbers.split(" ")[1])
Y=int(inputNumbers.split(" ")[2])

result = []
for k in range(1,N):
    result.append(0)

allBranchLength=[]

for i in range(1, N+1):
    for j in range(i+1,N+1):

        if i <= X:
            if j <= X:
                length = j - i
                result[length - 1] += 1

            if j > X and j < Y:
                length = X - i + min(j-X, Y-j+1)
                result[length - 1] += 1

            if j >= Y:
                length = (X - i) + 1 + (j - Y)
                result[length - 1] += 1

        if i > X and i < Y:
            if j > X and j < Y:
                length = min( (i - X) + 1 + (Y - j) , j - i )
                result[length - 1] += 1

            if j >= Y:
                length = min( (i - X) + 1 + (j - Y) , j - i )
                result[length - 1] += 1
                
        if i >= Y:
            if j >= Y:
                length = j - i
                result[length - 1] += 1


#for i in range(len(allBranchLength)):
#    result[allBranchLength[i][1] - 1] += 1

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

Submission status: Accepted

Solution code:
n, x, y = map(int, input().split(' '))
d_dict = {i:0 for i in range(1, n)}
for i in range(1, n):
    for j in range(i + 1, n + 1):
        if j <= x or y <= i:
            d_dict[j - i] += 1
        elif i <= x and x < j <= y:
            d_dict[min(j - i, x - i + y - j + 1)] += 1
        elif i <= x and j > y:
            d_dict[x - i + j - y + 1] += 1
        elif x < i < y and j < y:
            d_dict[min(j - i, i - x + y - j + 1)] += 1
        elif x < i < y and j >= y:
            d_dict[min(j - i, i - x + j - y + 1)] += 1
for i in range(1, n):
    print(d_dict[i])

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter
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)]
l[X-1][Y-1] = 1
l[Y-1][X-1] = 1
for i in range(1, N):
    l[i-1][i] = 1
    l[i][i-1] = 1

csr = np.array(l)
s = shortest_path(csr, directed=False).astype(np.int16)
arr = s.flatten()
c = Counter(arr)
for i in range(1, N):
    print(c[i]//2)

Submission status: Accepted

Solution code:
n,a,b = list(map(int,input().split()))
output_list = [0] * n
def d1(x,y,a,b):
    return y - x
def d2(x,y,a,b):
    if x <= a and b <= y:
        return a - x + y - b + 1
    if x <= a and y < b:
        return a - x + b - y + 1
    if a < x and b <= y:
        return x - a + y - b + 1
    if a < x and y < b:
        return x - a + b - y + 1
def d(x,y,a,b):
    return min(d1(x,y,a,b),d2(x,y,a,b))
for x in range(1,n):
    for y in range(x + 1,n + 1):
        output_list[d(x,y,a,b)] += 1
for k in range(1,n):
    print(output_list[k])

Submission status: Accepted

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

count = [0]*n

for i in range(1, n):
  for j in range(i+1, n+1):
    if i<=x and j>=y:   # out,out
      d = (x-i)+(j-y)+1
    elif i<=x and j<y:  # out, in
      if (y-j)<(j-x):
        d = (x-i)+(y-j)+1
      else:
        d = (x-i)+(j-x)
    elif i>x and j>=y:  # in, out
      if (y-i)>(i-x):
        d = (i-x)+(j-y)+1
      else:
        d = (y-i)+(j-y)
    else:               # in, in
      if (j-i)>((i-x)+(y-j)):
        d = (i-x)+(y-j)+1
      else:
        d = j-i
    #print(i, j, d)
    count[d] += 1

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

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
dist_dict = {k:0 for k in range(1, N)}

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


for i in range(1, N):
  for j in range(i+1, N+1):    
    dist = calc_dist(i,j)
    dist_dict[dist] += 1

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

Submission status: Accepted

Solution code:
from collections import Counter

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d
      
n, x, y = [int(i) for i in input().split()]

dij = Dijkstra(n)

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

c = Counter([])
for i in range(n):
  c.update(dij.shortest_path(i))

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

Submission status: Accepted

Solution code:
n, x, y = map(int, input().split())
l=[0]*n
hr=(y-x+1)/2

for i in range(1, n):
  if i<x:
    for j in range(i+1, n+1):
      if j < x + hr:
        l[j-i]+=1
      elif j<y:
        l[x-i+1+y-j]+=1
      else:
        l[x-i+1+j-y]+=1
  else:
    for j in range(i+1, n+1):
      if j<y:
        if j < i + hr:
          l[j-i]+=1
        else:
          l[i-x+1+y-j]+=1
      else:
        if y < i+hr:
          l[j-i]+=1
        else:
          l[i-x+1+j-y]+=1
for i in range(1, n):
  print(l[i])

Submission status: Accepted

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

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

# input
N, X, Y = [int(i) for i in readline().split()]

# graph
Graph = np.array([[0] * N for i in range(N)])
for i in range(N):
    if i-1 < 0:
        Graph[i, i+1] = 1
    elif N <= i+1:
        Graph[i, i-1] = 1
    else:
        Graph[i, i-1] = 1
        Graph[i, i+1] = 1

Graph[X-1, Y-1] = 1
Graph[Y-1, X-1] = 1

#print(Graph)

spath = shortest_path(Graph)
spathu = np.triu(spath)

#c = collections.Counter()
#for j in range(N-1):
#    c += collections.Counter(spath[j, j+1:])

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

c = collections.Counter(flatten_2dim(spathu))

#print(tmp)
#count = collections.Counter(tmp)

for i in range(1, N):
    print(c.get(i, 0))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N, X, Y = MII_split()

dist_counts = {}
for start_node in range(N - 1):
    back_s = abs(start_node - (X - 1))
    for i in range(start_node, N):
        dist_t = back_s + 1 + abs(Y - 1 - i)
        dist = min(dist_t, i - start_node)
        if dist in dist_counts:
            dist_counts[dist] += 1
        else:
            dist_counts[dist] = 1

for k in range(1, N):
    print(dist_counts[k] if k in dist_counts else 0)

Submission status: Accepted

Solution code:
from collections import Counter

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

    counter = Counter()
    for i in range(1,N):
        for j in range(i+1,N+1):
            d = min(j-i,abs(X-i)+abs(Y-j)+1)
            counter[d]+=1
    for i in range(1,N):
        print(counter[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

p = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if j<=X:
            p.append(j-i)
        elif j<=Y:
            if i <= X:
                p.append(min(j-i, X-i+1+Y-j))
            else:
                p.append(min(j-i, i-X+1+Y-j))
        else:
            if i <= X:
                p.append(j-i-(Y-X)+1)
            elif i <=Y:
                p.append(min(j-i, i-X+1+j-Y))
            else:
                p.append(j-i)
    
import collections
c = collections.Counter(p)
for k in range(1,N):
    print(c[k])