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:
#!/usr/bin/env python3
import sys


def solve(N: int, X: int, Y: int):
    ans = [0] * N
    for i in range(1, N):
        for j in range(i+1, N+1):
            a = min(j-i, abs(j-Y)+abs(X-i)+1)
            ans[a] += 1
    print(*ans[1:], sep='\n')


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, X, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

#import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




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



N,X,Y=acinput()



dist=[[-1 for j in range(N+1) ] for i in range(N+1)]


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

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

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

#print(np.array(dist))
#print(res)

Submission status: Accepted

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

for fr in range(1, N + 1):
    for to in range(fr + 1, N + 1):
        cost = min(to - fr, abs(X - fr) + abs(to - Y) + 1)
        ans[cost] += 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,X,Y=map(int,input().split())
X-=1
Y-=1
ans=[0 for i in range(0,N)]

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

for i in range(0,N):
    if i!=0:
        print(ans[i])

Submission status: Accepted

Solution code:
n, x, y = list(map(int, input().split()))
dist_cnt = (n) * [0]
x -= 1
y -= 1
for i in range(0, n - 1):
    for j in range(i + 1, n):
        dist = j - i
        if i <= x:
            if j >= y:
                dist = x - i + j - y + 1
            else:
                dist = min(dist, y - j + 1 + x - i)
        else:
            if j >= y:
                dist = min(dist, j - y + 1 + i - x)
            else:
                dist = min(dist, i - x + 1 + y - j)
        dist_cnt[dist] += 1
print( '\n'.join(map(str, dist_cnt[1:])))

Submission status: Accepted

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

A = [0]*(N-1)

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

for e in A:
    print(e)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
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)

for i in range(1, n):
    edges[i].append(i-1)

edges[x-1].append(y-1)
edges[y-1].append(x-1)

count = defaultdict(int)


def bfs(start):
    dist = [10**4] * n
    dist[start] = 0
    todo = deque([])
    for to in edges[start]:
        todo.append([1, to])

    while todo:
        d, node = todo.popleft()
        if d >= dist[node]:
            continue

        dist[node] = d
        for to in edges[node]:
            todo.append([d+1, to])
    return dist


for start in range(n):
    dist = bfs(start)
    for d in dist:
        count[d] += 1

for k in range(1, n):
    res = count[k] // 2
    print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

def solve(N: int, X: int, Y: int):
    l = [0] * (N-1)
    for i in range(N):
        for j in range(i+1,N):
            cost = min(j-i,1+abs(Y-j-1)+abs(X-i-1))-1
            l[cost] += 1
    for ll in l:
        print(ll)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, X, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
n, x, y = map(int, input().split())

edges = defaultdict(lambda: [])
for i in range(1, n):
    edges[i].append(i+1)
    edges[i+1].append(i)
edges[x].append(y)
edges[y].append(x)

# 幅優先
counter = [0 for i in range(n)]
for i in range(1, n+1):
    d = deque()
    is_checked = [False for _ in range(n+1)]
    dist = [-1 for _ in range(n+1)]
    dist[i] = 0
    d.append((i, 0))
    while len(d) > 0:
        e, pre_dist = d.popleft()
        if is_checked[e]:
            continue
        else:
            is_checked[e] = True
            dist[e] = pre_dist + 1
            for next_e in edges[e]:
                if not is_checked[next_e]:
                    d.append((next_e, pre_dist+1))
    for j in range(i+1, n+1):
        counter[dist[j]-1] += 1
print("\n".join(list(map(str, counter[1:]))))

Submission status: Accepted

Solution code:
###############################################################
#ダイクストラ法
#計算量O(logV*(V+E)) （V=頂点の個数 E=辺の個数）
#辺の重みが負である場合には使えない
n,x,y=map(int,input().split())
graph={i:{} for i in range(1,n+1)}


#graphの隣接行列表示
for i in range(1,n):
    graph[i][i+1]=1
    graph[i+1][i]=1
    
graph[x][y]=1
graph[y][x]=1

#graph表示完成
import heapq
def dijkstra(s,graph,n):
    #ｓからのグラフの最短最短距離をまとめたデータを返す
    dist=[10**20 for i in range(n+1)]
    dist[s]=0
    pq=[]
    heapq.heapify(pq)
    #全ての接点を一度優先度付きキューに挿入する
    heapq.heappush(pq,(0,s))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for point in graph[node].keys():
            w=graph[node][point]
            #nodeからpointに対して伸びる辺の長さ
            newlen=dist[node]+w
            if newlen<dist[point]:
                heapq.heappush(pq,(newlen,point))
                dist[point]=newlen

    return dist

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

for i in range(1,n+1):
    sub=dijkstra(i,graph,n)
    for j in range(1,n+1):
        dis=sub[j]
        ans_dis[dis]+=1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3

import itertools


def summarize_dists(n, x, y):
    if x > y:
        x, y = y, x
    # notice: ignore table[0]
    table = [0 for _ in range(n)]
    for i, j in itertools.combinations(range(n), 2):
        if i <= x and y <= j:
            dist = x - i + 1 + j - y
        elif i <= x:
            dist = x - i + min(j - x, 1 + y - j)
        elif y <= j:
            dist = min(i - x + 1, y - i) + j - y
        else:
            dist = min(j - i, i - x + 1 + y - j)
        table[dist] += 1
    return table


def main():
    n, x0, y0 = (int(z) for z in input().split())
    x = x0 - 1
    y = y0 - 1
    table = summarize_dists(n, x, y)
    print(*table[1:], sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(n):
    for j in range(i):
        swit=0
        if (i<=x and j<=x) or (i>=y and j>=y):
            answer[abs(i-j)]+=1
        elif j<=x and y<=i:
            answer[i-y+1+x-j]+=1
        elif x<=j and j<=y and x<=i and i<=y:
            answer[min(i-j, j-x+1+y-i)]+=1
        elif j<=x and x<=i and i<=y:
            answer[min(i-j, x-j+1+y-i)]+=1
        elif x<=j and j<=y and y<=i:
            answer[min(i-j, j-x+1+i-y)]+=1
            swit=5
        #print(i, j, answer, swit)

for an in range(len(answer)):
    if an!=0:
        print(answer[an])

Submission status: Accepted

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

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

for i in range(n):
    if i == 0:
        roots[i].append(1)
    elif i == n - 1:
        roots[i].append(n-2)
    else:
        roots[i].append(i-1)
        roots[i].append(i+1)

roots[x-1].append(y-1)
roots[y-1].append(x-1)
ans = [0] * (n-1)

for i in range(n):
    hq = []
    dis = [-1]* n
    dis[i] = 0
    heapq.heappush(hq, (0,i))
    while hq:
        dis1, place = heapq.heappop(hq)
        for j in roots[place]:
            if dis[j] == -1 or dis[j] > dis1 + 1:
                dis[j] = dis1 + 1
                heapq.heappush(hq, (dis1+1, j))
    for j in dis:
        if j > 0:
            ans[j-1] += 1

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

Submission status: Accepted

Solution code:
def solve(n, x, y):
    res_list = [0] * n
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = min(j - i, abs(i - x + 1) + abs(j - y + 1) + 1)
            res_list[d] += 1
    # print(res_list)
    return res_list[1:]


def main():
    n, x, y = map(int, input().split())
    res_list = solve(n, x, y)
    for res in res_list:
        print(res)


def test():
    assert solve(5, 2, 4) == [5, 4, 1, 0]
    assert solve(3, 1, 3) == [3, 0]
    assert solve(7, 3, 7) == [7, 8, 4, 2, 0, 0]


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
def main():
    N, X, Y = map(int, input().split())
    X = X - 1
    Y = Y - 1
    d = {}
    for i in range(X):
        for j in range(i+1, X+1):
            if (j - i) in d:
                d[j - i] += 1
            else:
                d[j - i] = 1
        for j in range(X+1, Y+1):
            t = min(j - i, Y - j + 1 + X - i)
            if t in d:
                d[t] += 1
            else:
                d[t] = 1
        for j in range(Y+1, N):
            t = (j - Y + 1 + X - i)
            if t in d:
                d[t] += 1
            else:
                d[t] = 1
    for i in range(X, Y):
        for j in range(i+1, Y+1):
            t = min(j - i, i - X + 1 + Y - j)
            if t in d:
                d[t] += 1
            else:
                d[t] = 1
        for j in range(Y+1, N):
            t = min(j - i, i - X + 1 + j - Y)
            if t in d:
                d[t] += 1
            else:
                d[t] = 1
    for i in range(Y, N):
        for j in range(i+1, N):
            if (j - i) in d:
                d[j - i] += 1
            else:
                d[j - i] = 1
    for i in range(1, N):
        if i not in d:
            print(0)
        else:
            print(d[i])
main()

Submission status: Accepted

Solution code:
N,X,Y = map(int,input().rstrip().split())
ans = [0 for _ in range(N)]
dis = [0,0]
xycent = (X + Y) / 2
for i in range(1 , N):
  for i2 in range(i + 1,N + 1):
    dis[0] = i2 - i
    dis[1] = abs(i - X) + abs(i2 - Y) + 1
    if dis[0] > dis[1]:
      ans[dis[1]] += 1
    else:
      ans[dis[0]] += 1
for i in range(1,N):
  print(ans[i])

Submission status: Accepted

Solution code:
class lheapq:
    def __init__(self, p):
        self.l = []
        if p:
            for sp in p:
                self.heappush(sp)

    def heappush(self, a):
        n = len(self.l)
        self.l.append(a)
        t = n
        while t != 0:
            if self.l[t][1] < self.l[(t - 1) // 2][1]:
                self.l[t], self.l[(t - 1) // 2] = self.l[(t - 1) // 2], self.l[t]
                t = (t - 1) // 2
            else:
                break

    def heappop(self):
        n = len(self.l)
        if n == 0:
            return [-1, 0]
        if n == 1:
            return self.l.pop()
        ret = self.l[0]
        self.l[0] = self.l.pop()
        n -= 1
        t = 0
        while t < n:
            child1 = t * 2 + 1
            child2 = t * 2 + 2
            if child1 >= n:
                break
            elif child2 >= n:
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t], self.l[child1] = self.l[child1], self.l[t]
                    t = child1
                else:
                    break
            else:
                if self.l[child2][1] < self.l[child1][1]:
                    child1, child2 = child2, child1
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t], self.l[child1] = self.l[child1], self.l[t]
                    t = child1
                elif self.l[t][1] > self.l[child2][1]:
                    self.l[t], self.l[child2] = self.l[child2], self.l[t]
                    t = child2
                else:
                    break
        return ret

    def isnotblank(self):
        if self.l:
            return True
        else:
            return False


def dijkstra(s, g, n):
    # グラフgの点0から点n-1までの最短距離を求める。
    # グラフは隣接行列で[[[目的地、辺の重み],[目的地、辺の重み]],[],...]
    f = [-1 for _ in range(n)]
    f[s] = 0
    q = lheapq(g[s])
    while True:
        kakutei = q.heappop()
        if kakutei[0] == -1:
            return f
        while f[kakutei[0]] != -1:
            kakutei = q.heappop()
            if kakutei[0] == -1:
                return f
        s = kakutei[0]
        f[s] = kakutei[1]
        for sg, sl in g[s]:
            if f[sg] == -1:
                q.heappush([sg, sl + f[s]])


def main():
    N, X, Y = map(int, input().split())
    g = [[] for _ in range(N)]
    for i in range(N - 1):
        g[i].append([i + 1, 1])
        g[i + 1].append([i, 1])
    g[X - 1].append([Y - 1, 1])
    g[Y - 1].append([X - 1, 1])
    res = [0 for _ in range(N)]
    for i in range(N):
        tres = dijkstra(i, g, N)
        for stres in tres:
            res[stres] += 1

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


main()

Submission status: Accepted

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

ans = [0]*n
from collections import deque

def bfs(num):
    q = deque()
    d = [-1]*n
    q.append(num)
    d[num]=0
    while q:
        p = q.popleft()
        for i in G[p]:
            if d[i]==-1:
                d[i] = d[p] + 1
                ans[d[i]] += 1
                q.append(i)

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 for i in range(n)]

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

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

Submission status: Accepted

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

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

cnt = [0]*(n-1)

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

print(*cnt,sep="\n")

Submission status: Accepted

Solution code:
# どうやってもN^2かかるんだが
# n^2通るじゃん...

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

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

from collections import deque
ans = [0]*(n-1)
def dfs(i):
    q = deque()
    q.append([i, 0])
    used = [0]*n
    while q:
        cur,d = q.popleft()
        if used[cur]:
            continue
        used[cur] = 1
        if d > 0:
            ans[d-1] += 1
        for to in G[cur]:
            if used[to]:
                continue
            q.append([to, d+1])

for i in range(n):
    dfs(i)
ans = [i//2 for i in ans]
print(*ans, sep="\n")

Submission status: Accepted

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

dist_count = {}
for i in range(n-1):
	for j in range(i+1, n):
		dist_simple = j - i
		dist_bridge1 = abs(i-x) + 1 + abs(j-y)
		dist_bridge2 = abs(i-y) + 1 + abs(j-x)
		res_dist = min(dist_simple, dist_bridge1, dist_bridge2)
		dist_count[res_dist] = dist_count.get(res_dist, 0) + 1


for dist in range(1, n):
	print(dist_count.get(dist, 0))

Submission status: Accepted

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

import heapq
INF = 10 ** 18
def dijkstra(n, edges, s):
    """
    input
        n : 頂点数
        edges : リスト(始点, 終点, コスト)
        s : 始点
    output
        d : 始点からの最短距離
    """
    d = [INF] * n
    used = [False] * n
    d[s] = 0
    used[s] = True
    edgelist = []
    # 初期のやつ
    for v, c in edges[s]:
        # print("v{},c{}".format(v,c))
        # コストを前にしてpushしておく(そこから最小値を取り出すので)
        heapq.heappush(edgelist, (c, v))
    # 空になるまで
    while len(edgelist):
        # コスト最小値を取り出す
        c_min, v_min = heapq.heappop(edgelist)
        # そのエッジがすでに確定していたら終わり
        if used[v_min]:
            continue
        # 確定していなければ、そこから派生するエッジをコスト付与して与える
        d[v_min] = c_min
        used[v_min] = True
        for v, c in edges[v_min]:
            if not used[v]:
                heapq.heappush(edgelist, (c+c_min, v))
    return d

ans = [0] * N
for i in range(N):
    d = dijkstra(N,edges,i)
    # print(d)
    for j in range(i+1,N):
        ans[d[j]] += 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

def calc(s):
	queue = [s]
	distance = [N + 1] * N
	distance[s] = 0
	while queue:
		cur = queue.pop()
		dist = distance[cur] + 1
		if cur > 0 and distance[cur - 1] > dist:
			queue.append(cur - 1)
			distance[cur - 1] = dist
		
		if cur < N - 1 and distance[cur + 1] > dist:
			queue.append(cur + 1)
			distance[cur + 1] = dist
		
		if cur == X and distance[Y] > dist:
			queue.append(Y)
			distance[Y] = dist
		
		if cur == Y and distance[X] > dist:
			queue.append(X)
			distance[X] = dist
	
	return distance

d_list = [calc(i) for i in range(N)]

#print(d_list)

d_table = [0] * N

for l in d_list:
	for d in l:
		d_table[d] += 1

for k in range(1, N):
	print(d_table[k] // 2)

Submission status: Accepted

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

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

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

def bfs(st, graph):
    INF = 10 ** 18
    dist = [INF] * len(graph)
    dist[st] = 0
    stack = [st]
    while stack:
        s = stack.pop()
        for t in graph[s]:
            if dist[t] > dist[s] + 1:
                dist[t] = dist[s] + 1
                stack.append(t)
    return dist

answer = [0] * (N + 1)
for i in range(1, N + 1):
    dist = bfs(i, graph)
    #print(dist)
    for j in range(1, N + 1):
        answer[dist[j]] += 1

for i in range(1, N):
    print(answer[i] // 2)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

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

Submission status: Accepted

Solution code:

import heapq as hq

def D_stra(N,connections,st):
    mxc=2**29
    cost =[mxc for i in range(N)]
    visited =[False for i in range(N)]
    cost[st]=0
    q=[]

    hq.heappush(q,(0,st))

    while q:
        c,node=hq.heappop(q)

        if visited[node]:
            continue
        visited[node]=True

        for connection in connections[node]:

            target,mc=connection
            if cost[target]>c+mc:
                cost[target]=c+mc
                hq.heappush(q,(c+mc,target))
    
    return cost



def resolve():
    N , X, Y = map(int,input().split())
    conections =[[[1,1]]]
    for i in range(1,N-1):
        conections.append([[i-1,1],[i+1,1]])
    conections.append([[N-2,1]])
    conections[X-1].append([Y-1,1])
    conections[Y-1].append([X-1,1])

    dist = [0 for i in range(N)]
    for i in range(N):
        cost = D_stra(N,conections,i)
        for j in cost[i:]:
            dist[j] += 1
    for i in dist[1:]:
        print(i)






if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys

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

res = {}

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

		#print(i, j, d)

		if d in res:
			res[d] += 1
		else:
			res[d] = 1

for k in range(1, n):
	if k in res:
		print(res[k])
	else:
		print(0)

Submission status: Accepted

Solution code:
def main():
    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):
            if j <= X or Y <= i:
                tmp = j - i
            elif i <= X and j <= Y:
                tmp = (X - i) + min(j - X, Y - j + 1)
            elif i <= X and Y <= j:
                tmp = (X - i) + (j - Y) + 1
            elif i <= Y and Y <= j:
                tmp = (j - Y) + min(Y - i, i - X + 1)
            else:
                tmp = min(j - i, i - X + Y - j + 1)

            ans[tmp - 1] += 1

    print(*ans, sep="\n")


main()

Submission status: Accepted

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

dist = [0] * n

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

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,x,y = get_nums_l()

x,y = (min(x,y), max(x,y))

by_cost = [0] * (n+1)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
f = [0] * N
for i in range(1, N):
    for j in range(i + 1, N + 1):
        if j <= X or Y < i:
            d = j - i
        elif i <= X and j <= Y:
            d = min(j - i, Y - j + 1 + X - i)
        elif i <= X and Y < j:
            d = X - i + 1 + j - Y
        elif X < i and Y < j:
            d = min(j - i, j - Y + 1 + i - X)
        elif X < i and j <= Y:
            d = min(j - i, i - X + 1 + Y - j)
        f[d] += 1
for i in range(1, N):
    print(f[i])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, X, Y = LI()
    X-=1
    Y-=1
    G = [[N+1 for _ in range(N)] for __ in range(N)]
    dists = []
    for i in range(N):
        for j in range(i, N):
            if i == j:
                continue
            # i->X->Y->j
            # i->j
            route = abs(X-i) + 1 + abs(Y-j)
            G[i][j] = min(abs(i-j), route)
            dists.append(G[i][j])
    c_dists = collections.Counter(dists)
    for i in range(1, N):
        print(c_dists[i])

main()

Submission status: Accepted

Solution code:
n,x,y=map(int,input().split())
x-=1
y-=1
d=[[0]*n for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        d[i][j]=min(j-i,abs(x-i)+abs(y-j)+1)
        
# for i in d:
#     print(i)
ans=[0]*(n+1)
for i in range(n):
    for j in range(n):
        ans[d[i][j]]+=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):
    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:
#create date: 2020-03-28 21:18

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, x, y = na()
    r = y-x
    ans = [0] * (n-1)
    for i in range(1, n):
        for j in range(i+1, n+1):
            l = min(j-i, abs(i-x)+1+abs(j-y))
            ans[l-1] += 1
    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,x,y = l_in()
d = [0 for _ in range(n)]

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import itertools
N,X,Y = map(int,input().split())
C = list(itertools.combinations(range(1,N+1),2))
ansdic = {i:0 for i in range(1,N)}
#print(C)
for i in C:
    a = i[0]
    b = i[1]
    tmpxy = abs(X - a) + 1 + abs(Y - b)
    tmp = b - a
    #print(a,b,min(tmpxy,tmp))
    ansdic[min(tmpxy,tmp)] += 1
    #print(ansdic)
for i in ansdic.keys():
    print(ansdic[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):
    if j <= x or i >= y:
      k = j-i
    elif i <= x and j >= y:
      k = x-i+j-y+1
    elif i <= x and j <= y:
      k = min(j-i,x-i+1+y-j)
    elif i >= x and j >= y:
      k = min(j-i,j-y+1+i-x)
    else:
      k = min(j-i,y-j+1+i-x)
    ans[k] += 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
l=[0]*(N-1)
for i in range(N-1):
    for j in range(i+1,N):
        l[min(j-i,abs(X-i)+abs(Y-j)+1)-1]+=1
print(*l,sep="\n")

Submission status: Accepted

Solution code:
def inputs(): return [int(x) for x in input().split()]
from collections import defaultdict
n,x,y = inputs()
ans = defaultdict(int)
for i in range(1,n):
    ans[i]=0
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if i<=x and y<=j:
            a = x-i+1+j-y
            ans[a]+=1
        else:
            if i<=x:
                a=min(j-i,x-i+1+y-j)
            elif y<=j:
                a = min(j-i,i-x+1+j-y)
            elif x<i and j<y:
                a = min(j-i,i-x+1+y-j)
            ans[a]+=1
for i in ans.keys():
    print(ans[i])