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 collections import deque

def breadth_first_search(start):
    work_q = deque([])
    visited = set()
    work_q.append(start)
    visited.add(start)
    cnt_array = [0] * (n+1)
    while work_q:
        here = work_q.popleft()
        for i in edge[here]:
            if i not in visited:
                work_q.append(i)
                visited.add(i)
                cnt_array[i] = cnt_array[here] + 1
    return cnt_array

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

ans = [0] * n
for i in range(1, n+1):
    a = breadth_first_search(i)
    for j in range(len(a)):
        ans[a[j]] += 1
for i in range(1,n):
    print(ans[i]//2)

Submission status: Accepted

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

Submission status: Accepted

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

x = X-1
y = Y-1

a = [0]*N

for i in range(N):
    for j in range(N-i-1):
        #print i, j
        p = i+j+1
        c = min(abs(p-i), abs(x-i)+1+abs(y-p))
        a[c]+=1
        #print "c=",c

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

Submission status: Accepted

Solution code:
import itertools
import collections

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

pos = [i for i in range(1,N+1)]
ways = list(itertools.combinations(pos,2))

dist_l = [min(abs(i-j), abs(i - X) + 1 + abs(Y - j)) for i,j in ways]

dic = collections.Counter(dist_l)
for i in range(1,N):
    print(dic[i])

Submission status: Accepted

Solution code:
from collections import deque
n,x,y = map(int,input().split())
cnt = [0]*n
for i in range(n):
    d = [float('inf')]*n
    que = deque([(i, 0)])
    while que:
        idx, c = que.popleft()
        if d[idx]!=float('inf'):
            d[idx] = min(d[idx], c)
            continue
        else:
            d[idx] = min(d[idx], c)
            if idx!=0:
                que.append((idx-1, c+1))
            if idx!=n-1:
                que.append((idx+1, c+1))
            if idx==x-1:
                que.append((y-1, c+1))
            if idx==y-1:
                que.append((x-1, c+1))
    for j in range(i+1, n):
        cnt[d[j]] += 1
for c in cnt[1:]:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    n,x,y = map(int,input().split())
    cnt = [0]*n
    for i in range(n):
        d = [float('inf')]*n
        que = deque([(i, 0)])
        while que:
            idx, c = que.popleft()
            if d[idx]!=float('inf'):
                d[idx] = min(d[idx], c)
                continue
            else:
                d[idx] = min(d[idx], c)
                if idx!=0:
                    que.append((idx-1, c+1))
                if idx!=n-1:
                    que.append((idx+1, c+1))
                if idx==x-1:
                    que.append((y-1, c+1))
                if idx==y-1:
                    que.append((x-1, c+1))
        for j in range(i+1, n):
            cnt[d[j]] += 1
    for c in cnt[1:]:
        print(c)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
dist = [[N+10 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(i+1, N+1):
        dist[i][j] = min(j-i, abs(X-i)+abs(Y-j)+1)
ans = [0 for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(i+1, N+1):
        ans[dist[i][j]] += 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())
x,y = x-1 ,y-1
g = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    que = deque([(i, 0)])
    while que:
        node, cost = que.popleft()
        if g[i][node]!=float('inf'):
            continue
        else:
            g[i][node] = cost
            if node>0:
                que.append((node-1, cost+1))
            if node<n-1:
                que.append((node+1, cost+1))
            if node==x:
                que.append((y, cost+1))
            if node==y:
                que.append((x, cost+1))
cnt = [0]*n
for i in range(n):
    for j in range(i+1, n):
        cnt[g[i][j]] += 1
for c in cnt[1:]:
    print(c)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from collections import Counter
def key(x, y):
    return str(x)+str(y)
def main2():
    # TLE
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    M = {}
    for i in range(N):
        for j in range(i, N):
            M[key(i, j)] = j - i
    
    def helper(x, y, from_cost):
        if 0 <= x <= N-1 and 0 <= y <= N-1:
            if M[key(x,y)] > from_cost+1:
                M[key(x,y)] = from_cost + 1
                cost = from_cost + 1

                helper(x-1,y, cost)
                helper(x+1,y, cost)
                helper(x,y-1, cost)
                helper(x,y+1, cost)
        
    helper(X, Y, 0)

    cost_list = Counter(list(M.values()))
    for k in range(N-1):
        print(cost_list[k+1])

from collections import deque
INF = 1e10


def main3():
    # official TLE
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    ans = [0 for _ in range(N)]
    for sv in range(N):
        dist = [INF for _ in range(N)]
        q = deque([])

        def push(v, d):
            if dist[v] != INF: return
            dist[v] = d
            q.append(v)

        push(sv, 0)

        while q:
            sv = q.popleft()
            d = dist[sv]
            if sv > 0:
                push(sv-1, d+1)
            if sv < N-1:
                push(sv+1, d+1)
            if sv == X:
                push(Y, d+1)
            if sv == Y:
                push(X, d+1)

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

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    dist = [0 for _ in range(N)]
    for i in range(N-1):
        for j in range(i+1, N):
            d = min(abs(X-i)+1+abs(j-Y), abs(i-j), abs(Y-i)+1+abs(j-Y))
            dist[d] += 1
    
    for k in range(1, N):
        print(dist[k])
 

main()

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools
from fractions import gcd
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**4
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))
N,X,Y = LI()

c = [0 for _ in range(N+1)]

for k in range(1,N):
    j = 1
    m = [0 for _ in range(N+1)]
    j = 1
    for i in range(k+1,N+1):
        m[i] = j
        j += 1
    if k <= X:
        j = X - k + 1
        a = 0
        while j + a < m[Y - a]:
            m[Y -a] = j + a
            a += 1
        a = 1
        if Y + a <= N:
            while j + a < m[Y + a]:
                m[Y + a] = j + a
                a += 1
                if Y + a > N : break
    elif k <= Y:
        j = k - X + 1
        a = 0
        while j + a < m[Y - a]:
            m[Y -a] = j + a
            a += 1
        a = 1
        if Y + a <= N:
            while j + a < m[Y + a]:
                m[Y + a] = j + a
                a += 1
                if Y + a > N : break
    for i in range(k+1,N+1):
        c[m[i]] += 1
for k in range(1,N):
    print (c[k])

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    n,x,y = map(int,input().split())
    ans = [0]*(n)
    E = [[] for i in range(n)]
    E[0].append(1)
    E[n-1].append(n-2)
    for i in range(1,n-1):
        E[i].append(i-1)
        E[i].append(i+1)
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    ans = [0]*(n)
    d = [[float("INF")]*n for i in range(n)]
    def search(x):
        d[x][x] = 0
        q = deque([])
        q.append((x,0))
        while q:
            bef,l = q.pop()

            for nex in E[bef]:
                if d[x][nex] > l+1:
                    d[x][nex] = l+1
                    q.append((nex,l+1))
        
        
    for i in range(n-1):
        search(i)
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i][j] != float("INF"):
                ans[d[i][j]] += 1

    for i in ans[1:]:
        print(i)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
def set_heapq(que, edge, used, v, add_dist=0):
    '''
    確定地点vからつながる辺を全てqueに設定し、返却する

    Parameters
    que : heapque(touple or list)
        辺を管理するキュー (距離、次の行き先)のtopuleまたはlistにて管理
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    v : int
        グラフ上のノード ダイクストラでは確定したノードがvにあたる
    add_dist : int
        確定した地点に足し合わせる距離 スタート地点以外では何かしらの値が追加されることになる

    Returns
    que : heapque(touple or list)
        引数queにvからつながる辺を追加したキュー
    '''
    for a,b in edge[v]:
        if used[b]:
            heapq.heappush(que,(a+add_dist,b))
    return que

def dijkstra_heap(n, s, edge):
    '''
    ダイクストラ法でsで指定された地点からの全てのノードまでの最短距離を返却
    
    Parameters
    n : int
        ノードの数
    s : int
        スタート地点
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている

    Returns
    d : list
        スタート地点から全てのノードの最短距離のリスト
    '''
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s], used[s] = 0, False
    edgelist = set_heapq([], edge, used, s)
    while len(edgelist):
        a, b = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[b]:
            continue
        d[b], used[b] = a, False
        # 確定地点vからつながる辺を全て優先度付きキューに入れる
        edgelist = set_heapq(edgelist, edge, used, b, d[b])
    return d

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

edge[X].append((1, Y))
edge[Y].append((1, X))

tmp = []
for i in range(N):
    tmp.append(dijkstra_heap(N, i, edge))

#print(tmp)
ans = []
for i in range(N):
    for j in range(i+1,N):
        ans.append(tmp[i][j])

from collections import Counter
c = Counter(ans)
for i in range(1, N):
    print(c[i])

Submission status: Accepted

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

out = [0] * (N)

for i in range(1,N):
    for j in range(i+1,N+1):
        # i,jの距離を求める ３パーターンのうち一番短いパターン
        # i→jパターン abs(j-i)
        # i→x→y→jパターン abs(i-x)+1+abs(j-y)
        # i→y→x→jパターン abs(i-y)+1+abs(j-x)
        dist = min(abs(j-i), abs(i-x)+1+abs(j-y), abs(i-y)+1+abs(j-x))
        out[dist] += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(n-1):
    b[i].append(i+1)
    b[i+1].append(i)

b[x-1].append(y-1)
b[y-1].append(x-1)
ans=[0]*(n-1)
# グラフでのbfs
import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1
                    ans[dis[y]-1]+=1
        return dis
    return bfs()


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

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

Submission status: Accepted

Solution code:
from collections import Counter
N,X,Y = map(int, input().split())
X -= 1
Y -= 1
L = []
for i in range(N-1):
  for j in range(i+1,N):
    L.append(min(abs(i-j),abs(X-i)+abs(Y-j)+1,abs(Y-i)+abs(X-j)+1))
D = Counter(L)
for k in range(1,N):
  print (D[k])

Submission status: Accepted

Solution code:
def resolve():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    from collections import defaultdict, deque
    matrix = defaultdict(list)
    for i in range(N-1):
        matrix[i].append(i+1)
        matrix[i+1].append(i)
    matrix[X].append(Y)
    matrix[Y].append(X)

    ans = [0] * N
    for i in range(N):
        queue = deque([(i, 0)])
        d = [float('inf')] * N
        while queue:
            node, dist = queue.popleft()
            if d[node] != float('inf'):
                continue
            d[node] = dist
            for adj in matrix[node]:
                queue.append([adj, dist+1])
        for j in range(N):
            ans[d[j]] += 1
    for i in range(1, N):
        print(ans[i]//2)
resolve()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline


    def bfs(v):
        dist = [f_inf for _ in range(n)]
        dist[v] = 0
        q = deque()
        q.append(v)
        while q:
            u = q.popleft()
            for nv in tree[u]:
                if dist[nv] == f_inf:
                    dist[nv] = dist[u] + 1
                    q.append(nv)
        for d in dist:
            res[d] += 1


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

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

    f_inf = float("inf")
    res = [0 for _ in range(n)]
    for i in range(n):
        bfs(i)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N,X,Y = map(int, input().split())
D = dd(int)
for i in range(1,N):
  for j in range(i+1,N+1):
    D[min(abs(i-j),abs(X-i)+abs(Y-j)+1,abs(Y-i)+abs(X-j)+1)] += 1 
for k in range(1,N):
  print (D[k])

Submission status: Accepted

Solution code:
import heapq
import sys
from collections import defaultdict

input = sys.stdin.readline

def dijkstra_heap(s,edge,n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        edge[i].append((1,i+1))
        edge[i+1].append((1,i))
    
    edge[X].append((1,Y))
    edge[Y].append((1,X))
    d = []
    for i in range(N):
        tmp = dijkstra_heap(i, edge, N)
        d.append(tmp)

    e = defaultdict(int)
    for i in range(N):
        for j in range(i,N):
            if i == j:
                continue
            e[d[i][j]] += 1

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.buffer.readline

def bfs(v):
    dist = [-1 for _ in range(n)]
    dist[v] = 0
    q = deque()
    q.append(v)

    while len(q) > 0:
        u = q.popleft()
        for nv in g[u]:
            if dist[nv] == -1:
                dist[nv] = dist[u] + 1
                q.append(nv)
    for d in dist:
        ans[d] += 1
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):
    bfs(i)
for i in range(1,n):
    print(ans[i]//2)

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

Submission status: Accepted

Solution code:
n,x,y=map(int,input().split())
G=[[i,i+2] for i in range(n)]
G[0],G[-1]=[2],[n-1]
G[x-1].append(y)
G[y-1].append(x)
#print(G)
ans=[0]*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        temp1=j-i
        temp2=abs(x-(i+1))+1+abs(y-(j+1))
        dis=min(temp1,temp2)
        ans[dis-1]+=1
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
# Problem D - Line++

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

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

# graph search
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)))
        # abs((Y-1)-i)+1+abs(j-(X-1))

# 個数の数え上げ
for i in range(N):
    for j in range(i+1, N):
        kyori = kyori_graph[i][j]
        kosu_list[kyori-1] += 1

# output
for k in kosu_list:
    print(k)

Submission status: Accepted

Solution code:
n,x,y=map(int,input().split())
G=[[i,i+2] for i in range(n)]
G[0],G[-1]=[2],[n-1]
G[x-1].append(y)
G[y-1].append(x)
#print(G)
ans=[0]*(n-1)
#X,Yのショートカットに気を付けて上から見ていく
for i in range(n-1):
    for j in range(i+1,n):
    #i+1<=XかつY<=j+1の時ショートカットするのが最短
        temp1=j-i
        temp2=abs(x-(i+1))+1+abs(y-(j+1))
        dis=min(temp1,temp2)
        ans[dis-1]+=1
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
# Problem D - Line++

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

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

# graph search
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)), abs((Y-1)-i)+1+abs(j-(X-1)))

# 個数の数え上げ
for i in range(N):
    for j in range(i+1, N):
        kyori = kyori_graph[i][j]
        kosu_list[kyori-1] += 1

# output
for k in kosu_list:
    print(k)

Submission status: Accepted

Solution code:
# Problem D - Line++

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

# initialization
INF = N
kyori_graph = [[INF]*N for i in range(N)]
kosu_list = [0]*(N-1)
for i in range(N):
    for j in range(i+1, N):
        if j==i+1:
            kyori_graph[i][j] = 1
        else:
            kyori_graph[i][j] = INF
kyori_graph[X-1][Y-1] = 1

# graph search
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)), abs((Y-1)-i)+1+abs(j-(X-1)))

# 個数の数え上げ
for i in range(N):
    for j in range(i+1, N):
        kyori = kyori_graph[i][j]
        kosu_list[kyori-1] += 1

# output
for k in kosu_list:
    print(k)

Submission status: Accepted

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

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

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

csr = csr_matrix(([1]*n, (v, u)), shape=(n, n))
result = shortest_path(csr, method='D', directed=False).astype(int)
ans = np.bincount(result.ravel(), minlength=n) // 2
print(*ans[1:], sep='\n')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,x,y = map(int,input().split())
 
root = [[] for i in range(n)]
for i in range(1,n):
    root[i-1].append(i)
    root[i].append(i-1)
root[x-1].append(y-1)
root[y-1].append(x-1)
memo = [0]*(n-1)
for j in range(n):
    stack=[j]
    check = [-1]*n
    check[j] = 0
    while len(stack):
        v = stack.pop(0)
        for i in root[v]:
            if check[i] == -1:
                check[i]=check[v]+1
                memo[check[i]-1]+=1
                stack.append(i)
for i in memo:
    print(i//2)

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
Graph = [[] for _ in range(N)]
for i in range(N):
    if i < N - 1:
        Graph[i].append(i + 1)
        Graph[i + 1].append(i)
    if X == i:
        Graph[X - 1].append(Y - 1)
        Graph[Y - 1].append(X - 1)
# print(Graph)
ans = [0] * (N - 1)
from collections import deque
for i in range(N):
    dist = [-1]*N
    que = deque([i])
    dist[i] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in Graph[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
    # print(dist)
    for d in dist:
        if d > 0:
            ans[d - 1] += 1
for a in ans:
    print(a // 2)

Submission status: Accepted

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

count = {k:0 for k in range(1, n)}
for i in range(1, n+1):
    for j in range(1, i):
        k = min(abs(i-j), abs(x-i) + 1 + abs(j-y),abs(y-i) + 1 + abs(x-j))
        count[k] += 1
for i in count.values():
    print(i)

Submission status: Accepted

Solution code:
import collections

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

distance_list = []

for i in range(1, N + 1):
    
    for j in range(i + 1, N + 1):
        
        dis_xy = abs(i - X) + 1 + abs(j - Y)
        dis = min(j - i, dis_xy)
        
        distance_list.append(dis)

count = collections.Counter(distance_list)


for i in range(1, N):
    cnt = count[i]
    print(cnt)

Submission status: Accepted

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

for p in range(1, N):
  for q in range(p, N+1):
    p2X = abs(p-X)
    q2Y = abs(q-Y)
    
    distance = min(q-p, p2X+q2Y+1)
    k_list[distance] += 1
    
for k in range(1, N):
  print(k_list[k])

Submission status: Accepted

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

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

mindcnt = [0] * N
for i in range(N):
    for j in range(i+1, N):
        d = mind[i][j]
        mindcnt[d] += 1

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

Submission status: Accepted

Solution code:
import itertools
 
N, X, Y = map(int, input().split())
 
n_iter = itertools.combinations(list(range(1,N+1)), 2)
 
count_list = [0]*(N-1)
 
for i, j in n_iter:
  #1. abs(X - i) + abs(Y - j) + 1
  #2. abs(Y - i) + abs(X - j) + 1
  #3. abs(j - i)
  x = min(
    abs(X - i) + abs(Y - j) + 1,
    abs(j - i)
  )
  count_list[x-1] += 1
 
for i in count_list:
  print(i)

Submission status: Accepted

Solution code:
n,x,y = map(int,input().split())
dist = [0]*(n-1)
for i in range(1,n):
  for j in range(i+1,n+1):
    dist[min(abs(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(dist[i])

Submission status: Accepted

Solution code:
import itertools

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

n_iter = itertools.combinations(list(range(1,N+1)), 2)

count_list = [0]*(N-1)

for i, j in n_iter:
  #1. abs(X - i) + abs(Y - j) + 1
  #2. abs(Y - i) + abs(X - j) + 1
  #3. abs(j - i)
  x = min(
    abs(X - i) + abs(Y - j) + 1,
    abs(Y - i) + abs(X - j) + 1,
    abs(j - i)
  )
  count_list[x-1] += 1

for i in count_list:
  print(i)

Submission status: Accepted

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

Submission status: Accepted

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

dist = [0]*n

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

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

Submission status: Accepted

Solution code:
n, x, y = map(int, input().split())
a = [0 for i in range(n-1)]
for ii in range(n):
	for jj in range(ii+1,n):
		i = ii+1
		j = jj+1
		if i < x and j < x:
			b = j-i
		elif i < x and j >= x and j <= y:
			b = min(j-i, y-j+1+x-i)
		elif i < x and j > y:
			b = j-i-(y-x)+1
		elif i >= x and i <= y and j >= x and j <= y:
			b = min(j-i,i-x+y-j+1)
		elif i >= x and i <= y and j > y:
			b = min(j-i,i-x+1+j-y)
		else:
			b = j-i
		#print (i,j,b)
		a[b-1] += 1
for i in a:
	print (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):
     dis=min(abs(i-j),abs(x-i)+1+abs(y-j))-1
     ans[dis]+=1
for i in ans:
    print(i)

Submission status: Accepted

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

ans = [0] * n

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

print( "\n".join( [str(d) for d in ans][1:] ))

Submission status: Accepted

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

Submission status: Accepted

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

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

print(*C)

Submission status: Accepted

Solution code:
# D問題
from collections import deque
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    inf = 10**5
    ans = [0]*n
    q = deque()
    for i in range(n):
        dist = [inf]*n
        q.appendleft(i)
        dist[i] = 0
        while q:
            v = q.pop()
            d = dist[v]
            if v-1 >= 0 and dist[v-1] == inf:
                q.appendleft(v-1)
                dist[v-1] = d+1
            if v+1 <= n-1 and dist[v+1] == inf:
                q.appendleft(v+1)
                dist[v+1] = d+1
            if v == x and dist[y] == inf:
                q.appendleft(y)
                dist[y] = d + 1
            if v == y and  dist[x] == inf:
                q.appendleft(x)
                dist[x] = d + 1
        for di in dist:
            ans[di] += 1
    for a in ans[1:]:
        print(a//2)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

print('\n'.join(map(str,ans[1:])))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse
N,X,Y = (int(x) for x in input().split())
lil = scipy.sparse.lil_matrix((N, N), dtype = int)
for i in range(N-1):
    lil[i, i+1] = 1
    lil[i+1, i] = 1
lil[X-1, Y-1] = 1
lil[Y-1, X-1] = 1
lil2 = scipy.sparse.csgraph.dijkstra(lil, directed = False).astype(int)
ans = np.bincount(lil2.ravel(), minlength = N) // 2
for i in range(1,N):
    print(ans[i])