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:
N,X,Y = map(int,input().split())
cnt = [0] * N
for i in range(1,N):
    for j in range(i+1,N+1):
        min0 = min(j-i,abs(X-i)+1+abs(j-Y))
        cnt[min0] += 1
for num,i in enumerate(cnt):
    if num == 0:continue
    else:print(i)

Submission status: Accepted

Solution code:
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):
        ans[min(abs(i-j) , abs(i-x)+1+abs(j-y)) ]+=1
        
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

Solution code:
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):
        ans[min(abs(i-j) , abs(i-x)+1+abs(j-y), abs(i-y)+1+abs(j-x)) ]+=1
        
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *

input = lambda: sys.stdin.readline().rstrip()

N, X, Y = map(int, input().split())
data = [[] for i in range(N + 1)]
for i in range(1, N):
    a = i
    b = i + 1
    data[a].append(b)
    data[b].append(a)
data[X].append(Y)
data[Y].append(X)

dic = defaultdict(int)
for i in range(1,N+1):
    stack=deque([[i,0]])
    visited=set()
    visited.add(i)
    count=set()
    while stack:
        now, dist=stack.popleft()
        for j in data[now]:
            if not j in visited:
                #print(stack)
                visited.add(j)
                stack.append([j,dist+1])
                dic[dist+1]+=1
for k in range(1,N):
    print(dic[k]//2)

Submission status: Accepted

Solution code:
def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N,X,Y=map(int,input().split())
    V, E= N,N
    g = [[] for i in range(V)]

    for i in range(N-1):
        g[i].append((1, i+1))
        g[i+1].append((1, i))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
    g[X-1].append((1, Y-1))
    g[Y-1].append((1, X-1))

    INF = 10 ** 10
    ans = [0] * N

    for r in range(N):
        for i in dijkstra(V, g, r):
            if i<INF:
                ans[i]+=1

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


resolve()

Submission status: Accepted

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

Submission status: Accepted

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

ans = [0]*n
for i in range(1, n+1):
  for j in range(i, n+1):
    m = min(j-i,  abs(x-i) + 1 + abs(j-y))
    ans[m] += 1
      
print(*ans[1:], sep = '\n')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# D - Line++
# 標準入力の取得
N,X,Y = list(map(int, input().split()))

# 求解
# (i, j)間の最短距離はmin{|j-i|, |X-i|+1+|j-Y|, |Y-i|+1+|j-X|}であるため、
# (i, j)が決まれば、最短距離はO(1)で決まる。したがって、全(i, j)について、最短距離を求める。
k_list = [0 for i in range(1,N)]
for i in range(1, N):
    diff_X_i = abs(X - i)
    diff_Y_i = abs(Y - i)
    for j in range(i+1, N+1):
        diff_j_i = abs(j - i)
        diff_j_X = abs(j - X)
        diff_j_Y = abs(j - Y)
        min_path = min([diff_j_i, diff_X_i+1+diff_j_Y, diff_Y_i+1+diff_j_X])
        k_list[min_path-1] += 1

# 結果出力
for k in k_list:
    print(k)

Submission status: Accepted

Solution code:
import sys
import math
import numpy

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

k = [0] * (n-1)

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

[print(p) for p in k]

Submission status: Accepted

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

# for k in range(1,n):
#   count=0
#   #i<j
#   for i in range(1,n):
#     for j in range(i+1,n+1):
#       if dis(i,j)==k:
#         count+=1
#   print(count)
ans=[0]*(n-1)
#i<j
for i in range(1,n):
  for j in range(i+1,n+1):
    ans[dis(i,j)-1]+=1
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
n, x, y = map(int, input().split())
x -= 1
y -= 1
GRAPH = [[0]*n for _ in range(n)]

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

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

Submission status: Accepted

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

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

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

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

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
# ABC160_D
from collections import deque,Counter
n,x,y=map(int,input().split())
G=[[] for i in range(n)]
dist=[-1]*n
for i in range(n-1):
    a=i
    b=i+1
    G[a].append([b,1])
    G[b].append([a,1])
G[x-1].append([y-1,1])
G[y-1].append([x-1,1])


ans=[]
for i in range(n-1):
    q=deque()
    q.append(i)
    dist=[-1]*n
    dist[i]=0
    while q:
        cur=q.popleft()
        for nx,nx_dist in G[cur]:
            if dist[nx]==-1:
                dist[nx]=dist[cur]+nx_dist
                q.append(nx)
    for j in range(i+1,n):
        ans.append(dist[j])

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

Submission status: Accepted

Solution code:
def dij(n,x,y,i,j):
#    d=min((j-i),(abs(x-i)+1+abs(j-y)),(abs(x-j)+1+abs(i-y)))
    d=min((j-i),(abs(x-i)+1+abs(j-y)))
    return d

n,x,y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき

c=[0]*(n+1)

for i in range(1,n):
    for j in range(i+1,n+1):
        d=dij(n,x,y,i,j)
        c[d]=c[d]+1
        
for i in range(1,n):
    print(c[i])

Submission status: Accepted

Solution code:
N, X, Y= map(int, input().split()) 
Count = [0]*(N-1)
  

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:

import collections


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

    inf = 10**9

    # 頂点=v 距離=d
    def pus(v, d, dist, q):
        if dist[v] == inf:
            dist[v] = d
            q.append(v)
        return 0

    ans = [0]*N

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

g = [[]  for i in range(N)]
for i in range(N):
    u = i
    v = i + 1
    if v < N:
        g[u].append(v)
        g[v].append(u)

g[X - 1].append(Y - 1)
g[Y - 1].append(X - 1)

from collections import deque
dis = [[float('Inf')] * N for _ in range(N)]
count = [0] * (N - 1)
def bfs(i):
    d = [False] * N
    que = deque()
    #for j in g[i]:
    que.append(i)
    d[i] = True
    dis[i][i] = 0
    #pre = i
    while que:
        p = que.popleft()

        for k in g[p]:
            if d[k]:
                continue
            else:
                d[k] = True
                que.append(k)
                dis[i][k] = dis[i][p] + 1
                #dis[k][i] = dis[i][p] + 1
                count[dis[i][k] - 1] += 1 
                #count[dis[k][i] - 1] += 1
        #pre = p

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

for i in range(N - 1):
    print(count[i] // 2)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    n, x, y = map(int, input().split())
    g = dict()
    for i in range(n):
        if i == 0:
            g[i] = [i+1]
        elif i == n-1:
            g[i] = [i-1]
        else:
            g[i] = [i-1, i+1]
    g[x-1].append(y-1)
    g[y-1].append(x-1)
    distance = [0]*(n-1)
# 1番ノードから各ノードへの最短距離を求めていく.
    for i in range(n):
        queue = deque()
        visited = [0]*n
    # まず処理される予定のノードが格納されているqueueに最初のノードを格納する
        queue.append(i)
        while queue:
            target = queue.popleft()
            for j in g[target]:
                if visited[j] == 0 or visited[j] > visited[target] + 1:
                    visited[j] = visited[target] + 1
                    queue.append(j)
        for k, a in enumerate(visited):
            if k > i:
                if a >= 1:
                    distance[a-1] += 1
    # print(f"{i}番ノードからの各ノードへの最短距離は{visited}である")
    for l in distance:
        print(l)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

g = [[] for _ in range(N)]
for i in range(N - 1):
    u = i
    v = i + 1
    g[u].append(v)
    g[v].append(u)
g[X - 1].append(Y - 1)
g[Y - 1].append(X - 1)

from collections import deque
dis = [[0] * N for _ in range(N)]
def bfs(i):
    visited = [False] * N
    que = deque([i])
    dis[i][i] = 0
    visited[i] = True
    
    while que:
        p = que.popleft()
        for new in g[p]:
            if visited[new]:
                continue
            else:
                visited[new] = True
                que.append(new)
                dis[i][new] = dis[i][p] + 1
                count[dis[i][new] - 1] += 1

count = [0] * (N - 1)
for i in range(N):
    bfs(i)

for i in range(N - 1):
    print(count[i] // 2)

Submission status: Accepted

Solution code:
from _collections import deque
N,X,Y=map(int,input().split())
X-=1
Y-=1
inf=pow(10,9)
answers=[0]*N
def bfs(n):
    visited_point=[inf for _ in range(N)]
    visited_point[n]=0
    stack=deque([n])
    while len(stack)>0:
        x=stack.pop()
        if x==X and visited_point[Y]==inf:
            visited_point[Y]=visited_point[x]+1
            stack.appendleft(Y)
        if x==Y and visited_point[X]==inf:
            visited_point[X]=visited_point[x]+1
            stack.appendleft(X)
        for nx in (1,-1):
            new_n=x+nx
            if new_n<0 or new_n>=N:
                continue
            if visited_point[new_n]==inf:
                visited_point[new_n]=visited_point[x]+1
                stack.appendleft(new_n)
    for i in visited_point:
        answers[i]+=1
for a in range(N):
    bfs(a)
for b in range(1,N):
    print(answers[b]//2)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque
# import sys
# input = sys.stdin.readline
n, x, y = map(int, input().split())
g = dict()
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1, i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)
# print(g)
distance = [0]*(n-1)
# 1番ノードから各ノードへの最短距離を求めていく.
for i in range(n):
    queue = deque()
    visited = [0]*n
    # まず処理される予定のノードが格納されているqueueに最初のノードを格納する
    queue.append(i)
    while queue:
        target = queue.popleft()
        for j in g[target]:
                if visited[j] == 0 or visited[j] > visited[target] + 1:
                    visited[j] = visited[target] + 1
                    queue.append(j)
    for k, a in enumerate(visited):
        if k > i:
            if a >= 1:
                distance[a-1] += 1
    # print(f"{i}番ノードからの各ノードへの最短距離は{visited}である")
for l in distance:
    print(l)

Submission status: Accepted

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

a=X-1
b=N-Y
c=Y-X+1

for k in range(1,N):
    #print('--k={}--'.format(k))
    ans=0
    #A
    if a < k:
        pass
    else:
        ans+=a-k+1
    #print('a')
    #print(ans)
    #B
    if b < k:
        pass
    else:
        ans+=b-k+1
    #print('b')
    #print(ans)
    #c
    if c/2 < k:
        pass
    elif c%2==0 and c//2 == k:
        ans+=c//2
    else:
        ans+=c
    #print('c')
    #print(ans)
    #ABC
    if a!=0 and b!=0 and 3<=k<=a+b+1:
        suba=(k-3)-(a-1) if (k-3)-(a-1)>0 else 0 
        subb=(k-3)-(b-1) if (k-3)-(b-1)>0 else 0
        ans += k-2-suba-subb
    #print('abc')
    #print(ans)
    #AC
    if a!=0 and 2<=k<=a+c//2:
        aa=a-1
        cc=c//2
        suba=(k-2)-(aa) if (k-2)-(aa)>0 else 0 
        subc=(k-1)-(cc) if (k-1)-(cc)>0 else 0
        ans += (k-1-suba-subc)*2
        #print('suba={},subc={},{}'.format(suba,subc,k-c//2))
        if c%2==0 and 0<k-c//2:
            ans-=1

    #print('ac')
    #print(ans)
    #print(suba)
    #print(subc)
    #BC
    if b!=0 and 2<=k<=b+c//2:
        bb=b-1
        cc=c//2
        subb=(k-2)-(bb) if (k-2)-(bb)>0 else 0 
        subc=(k-1)-(cc) if (k-1)-(cc)>0 else 0
        ans += (k-1-subb-subc)*2

        if c%2==0 and 0<k-c//2:
            ans-=1
    #print('bc')
    #print(ans)
    print(ans)

Submission status: Accepted

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

ret = [0] * (n-1)
for i in range(1, n):
    for j in range(i+1, n+1):
        p1 = j-i
        p2 = abs(i - x) + 1 + abs(j - y)
        p3 = abs(i - y) + 1 + abs(j - x)
        if p1 > p2:
            p1 = p2
        if p1 > p3:
            p1 = p3
        ret[p1-1] += 1

for data in ret:
    print(data)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#そもそもO(N^2)の意識がなかった
#無理やり最短距離を求めようとして数え忘れたパターンがあった
#このパターンはしっかりサンプル見て実験していれば避けれていた
#自分の考察に自信を持つ姿勢はいいけど、詰まったら疑って実験する
n,x,y=map(int,input().split())
ans=[[1000000]*n for i in range(n)]
for i in range(n-1):
    ans[i][i+1]=1
ans[x-1][y-1]=1
for i in range(n-1):
    for j in range(i+1,n):
        ans[i][j]=min(j-i,abs(x-1-i)+1+abs(y-1-j))
_ans=[0]*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        _ans[ans[i][j]-1]+=1
for i in range(n-1):
    print(_ans[i])

Submission status: Accepted

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

from collections import deque, defaultdict

def bfs(s,es):
    d=[-1]*n
    d[s]=0
    que=deque()
    que.append(s)
    while que:
        p=que.popleft()
        cnt=d[p]+1
        for e in es[p]:
            if d[e]!=-1:
                continue
            que.append(e)
            d[e]=cnt
    return d

x=[]

for i in range(n):
    x+=bfs(i,es)[i:]
    
x=sorted(x)
#print(x)
from bisect import bisect_left, bisect_right

for i in range(1,n):
    l=bisect_left(x,i)
    r=bisect_right(x,i)
    print(r-l)

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
ans = [0] * N

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

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

Submission status: Accepted

Solution code:
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = [0]*(n-1)
    for i in range(n):
        for j in range(i+1, n):
            if i < x and y < j:
                dist = j-i-(y-x)+1
            elif j < x or y < i:
                dist = j-i
            elif i <= x and j <= y:
                dist = min(j-i, x-i+1+y-j)
            elif x <= i and y <= j:
                dist = min(j-i, j-y+1+i-x)
            else:
                dist = min(j-i, y-x-(j-i)+1)
            ans[dist-1] += 1
    for i in ans:
        print(i)


main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


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

    color[s-1]="gray"
    D[s-1]=0
    queue=deque([s-1])

    while len(queue)!=0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return D


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

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

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

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

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

Submission status: Accepted

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

ans = [0] * (n+10)

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

Submission status: Accepted

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

Submission status: Accepted

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

print(*d[1:],sep="\n")

Submission status: Accepted

Solution code:
import heapq


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

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

    D[s]=0

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

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

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


inf=10**7
n,x,y=map(int,input().split())

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

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)


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

    color[s-1]="gray"
    D[s-1]=0
    queue=deque([s-1])

    while len(queue)!=0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return D


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

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

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

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

Submission status: Accepted

Solution code:
# Problem Line++

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

# initialization
kyori_graph = [[N]*N for i in range(N)]
kosu_list = [0]*(N-1)

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

# output
for i in range(N):
    for j in range(i+1, N):
        kyori = kyori_graph[i][j]
        kosu_list[kyori-1] += 1
for k in kosu_list:
    print(k)

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):
        dist = min(j-i,abs(x-i)+1+abs(j-y))
        ans[dist-1] += 1
print(*ans,sep="\n")

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

distnum = [0 for i in range(N)]


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

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

Submission status: Accepted

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

ans = [0] * (n)
#グラフを0-indexで使用するため、デクリメントする
x -= 1
y -= 1

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

for x in range(1, len(ans)):
    print(ans[x])

Submission status: Accepted

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


min_dist = [0] * n

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

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

Submission status: Accepted

Solution code:
def distance(i,j,X,Y):
    return min([abs(i-j), abs(X-i)+1+abs(Y-j), abs(Y-i)+1+abs(X-j)])

N,X,Y=[int(e) for e in input().split(' ')]
cnt=[0]*(N-1)

for i in range(1,N):
    for j in range(i+1,N+1):
        #print('i={},j={}'.format(i,j))
        d=distance(i,j,X,Y)
        cnt[d-1]+=1
for c in cnt:
    print(c)

Submission status: Accepted

Solution code:

from itertools import combinations
from collections import Counter
N, X, Y = map(int, input().split())
X, Y = X-1, Y-1
ans = []
for i, j in combinations(range(N), 2):
    ans.append(min(j-i, 1+abs(i-X)+abs(j-Y)))
c = Counter(ans)
for i in range(1,N):
    print(c[i])

Submission status: Accepted

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

X -= 1
Y -= 1

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

Submission status: Accepted

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

#output
dp = [0] * N
for i in range(N-1):
    for j in range(i+1, N):
        temp = min(j-i, abs(X-1-i)+abs(Y-1-j)+1, abs(Y-1-i)+abs(X-1-j)+1)
        dp[temp] += 1

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

Submission status: Accepted

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

for i in kyori.values():
    print(i)

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().strip().split())
# dist=[[0]*N for _ in range(N)]
X-=1
Y-=1
ans=[0]*(N-1)
for i in range(N):
    for j in range(i):
        # if i==j:
        #     continue
        # dist[i][j]=min(abs(i-j),abs(i-X)+1+abs(j-Y))
        dist=min(abs(i-j),abs(i-Y)+1+abs(j-X))
        ans[dist-1]+=1
# print(dist)
# output
[print(v) for v in ans]

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

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

edges = [[] for _ in range(N)]

for i in range(N-1):
    edges[i].append(i+1)
    edges[i+1].append(i)


edges[X-1].append(Y-1)
edges[Y-1].append(X-1)

ans = [0] * (N-1)

queue = deque([])

def bfs(start):
    queue.extend(edges[start])
    visited = [False] *  N
    visited[start] = True
    i = 0
    while queue:
        length = len(queue)
        for l in range(length):
            current = queue.popleft()
            if not visited[current]:
                ans[i] += 1
                if edges[current]:
                    queue.extend(edges[current])
                visited[current] = True    
        i += 1

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

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

Submission status: Accepted

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

for x in ans[1:]:
    print(x)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def main():
  N,X,Y = map(int,input().split())
  V = [[] for _ in range(N)]
  
  for i in range(N-1):
    V[i].append(i+1)
    V[i+1].append(i)
  X -= 1
  Y -= 1
  V[X].append(Y)
  V[Y].append(X)
  #print(V)
  
  ans = [0 for _ in range(N)]
  INF = float('INF')
  for s in range(N):
    D = [INF for _ in range(N)]
    q = [s]
    d = 0
    while(q):
      q2 = []
      for v in q:
        D[v] = min(D[v],d)
        for u in V[v]:
          if D[u] == INF:
            q2.append(u)
      q = q2[:]
      d += 1
      #print(q,d,D)
    for i in range(N):
      ans[D[i]] += 1
  for i in range(1,N):
    print(ans[i]//2)

main()

Submission status: Accepted

Solution code:
n,x,y = map(int,input().split())
dist = [[0] for i in range(n)]

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
res = [0] * N
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)
        res[d] += 1

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