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:
# -*= coding: utf-8 -*-
from collections import deque

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

d = deque() # 初期化

ans = [0] * N

# BFS
for i in range(N):
  # 0 〜 N-1の各頂点からスタート
  
  cost = [-1] * N
  cost[i] = 0
  d.append(i) # 基準とする頂点をノードiにする
  
  while len(d) > 0:
    # dequeueが空でない間ループ
    
    # 現在のノードのインデックス
    current = d.popleft()
    
    if current - 1 >= 0 and cost[current - 1] == -1:
      # 1つ前のノードを登録
      
      d.append(current - 1)
      cost[current - 1] = cost[current] + 1
      
    if current + 1 < N and cost[current + 1] == -1:
      # 1つ後ろのノードを登録
      
      d.append(current + 1)
      cost[current + 1] = cost[current] + 1
      
    if current == X - 1 and cost[Y - 1] == -1:
      # XからYへのルートを登録
      
      d.append(Y - 1)
      cost[Y - 1] = cost[current] + 1
    
    if current == Y - 1 and cost[X - 1] == -1:
      # YからXへのルートを登録
      
      d.append(X - 1)
      cost[X - 1] = cost[current] + 1
      
  # この時点でcostにはノードiから各ノードへの最小コストが格納されている
  
  #print(cost)
  for j in range(N):
    ans[cost[j]] += 1

for i in range(1, N):
  print(ans[i]//2) # ノードA→Bと、逆向きのB→Aが、両方カウントされているので2分の1する

Submission status: Accepted

Solution code:
import itertools

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

# 距離が0,1,2,...,n-1のパスの本数
l = [0] * N

# 1,2,...,Nから2つを選ぶ組み合わせ
# 生成される組み合わせ(i,j)は既にi<jになっている
comb = itertools.combinations(range(1, N + 1), 2)

# (直接iとjを繋ぐ)or(特殊なパスを通る)の２種類が考えられる
# 両方計算してminを取れば欲しい距離が得られる
for v in comb:
    min_dist = min(v[1] - v[0], abs(X - v[0]) + 1 + abs(Y - v[1]))
    l[min_dist] += 1

# 距離が1,2,3,...,N-1について総数を出力
for item in l[1:]:
    print(item)

Submission status: Accepted

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

for i in range(n-1):
    for j in range(i+1,n):
        if i<j and j<=x:
            min_len=j-i
        elif i<=x and x<j and j<y:
            if j<=(x+y)//2:
                min_len=j-i
            else:
                min_len=(y-j)+1+(x-i)
        elif x<i and i<j and j<y:
            min_len=min(j-i,y-j+1+i-x)
        elif x<i and i<y and y<=j:
            if i>=(x+y)//2:
                min_len=j-i
            else:
                min_len=(j-y)+1+(i-x)
        elif y<=i and i<j:
            min_len=j-i

        elif i<=x and x<y and y<=j:
            min_len=j-y+1+x-i
        min_len-=1
        ans[min_len]+=1

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    inf = 10 ** 7
    ans = [0 for _ in range(n)]

    # See:
    # https://www.youtube.com/watch?v=zG1L4vYuGrg&feature=youtu.be
    # KeyInsight:
    # △: 全探索 + 深さ優先探索
    # ×: どのように実装すればいいか、見当がつかなかった
    for i in range(n):
        # グラフを陽に持たない場合
        # 始点からの距離を管理
        dist = [inf for _ in range(n)]  # 距離無限大で初期化
        dist[i] = 0

        # キューを用意して、頂点を管理
        d = deque()
        d.append(i)

        # BFS
        while d:
            v = d.popleft()  # 最も左側の内容(=最初に突っ込んだ値)を取り出す
            dj = dist[v]

            # 場合分け
            # 範囲外参照を回避しながら、次の頂点に移動したときの距離を計算
            if v - 1 >= 0 and dist[v - 1] == inf:
                dist[v - 1] = dj + 1
                # 次の頂点をキューに突っ込む
                d.append(v - 1)
            if v + 1 < n and dist[v + 1] == inf:
                dist[v + 1] = dj + 1
                d.append(v + 1)
            if v == x and dist[y] == inf:
                dist[y] = dj + 1
                d.append(y)
            if v == y and dist[x] == inf:
                dist[x] = dj + 1
                d.append(x)

        # 距離ごとの個数を計算
        for j in range(n):
            ans[dist[j]] += 1

    # 始点と終点を区別
    for k in range(n):
        ans[k] //= 2

    # 答えを出力
    for ii in range(1, n):
        print(ans[ii])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

inf = 10 ** 7


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

    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = [0 for _ in range(n)]

    for i in range(n):
        dist = [inf for _ in range(n)]
        dist[i] = 0

        d = deque()
        d.append(i)

        while d:
            v = d.popleft()
            dj = dist[v]

            if v - 1 >= 0 and dist[v - 1] == inf:
                dist[v - 1] = dj + 1
                d.append(v - 1)
            if v + 1 < n and dist[v + 1] == inf:
                dist[v + 1] = dj + 1
                d.append(v + 1)
            if v == x and dist[y] == inf:
                dist[y] = dj + 1
                d.append(y)
            if v == y and dist[x] == inf:
                dist[x] = dj + 1
                d.append(x)

        for j in range(n):
            if dist[j] != inf:
                ans[dist[j]] += 1

    for k in range(n):
        ans[k] //= 2

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    n, x, y = map(int, input().split())
    ans = defaultdict(int)
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            l = min(abs(i - j), abs(i - x) + abs(y - j) + 1, abs(i - y) + abs(x - j) + 1)
            ans[l] += 1
    [print(ans[i]) for i in range(1, n)]

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

k = [0] * n

for v in itertools.combinations(list(range(1,n+1)), 2):
  k[min(abs(v[1]-v[0]),abs(x-min(v))+1+abs(y-max(v)))] += 1

for item in k[1:]:
  print(item)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    # n, m = [int(x) for x in input().split()]
    n, x, y = [int(x) for x in input().split()]
    
    ans = defaultdict(int)

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

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

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

azyxwvutsrqponmlkjihgfedcb

"""

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


g = defaultdict(list)
n = 0
ans = defaultdict(int)
def bfs(x):
    q = deque([(x, 0)])
    w = set([x])
    while q:
        v, dis = q.popleft()
        if v > x:
            ans[dis] += 1
        for to in g[v]:
            if to not in w:
                w.add(to)
                q.append((to, dis + 1))
    

def solve():
    # n, m = [int(x) for x in input().split()]
    n, X, Y = [int(x) for x in input().split()]
    X -= 1
    Y -= 1
    g[X].append(Y)
    g[Y].append(X)
    for i in range(1, n):
        g[i].append(i-1)
        g[i-1].append(i)
    
    for i in range(n-1):
        bfs(i)

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

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

azyxwvutsrqponmlkjihgfedcb

"""

Submission status: Accepted

Solution code:
def main():
    n,x,y = map(int,input().split())
    dis = [0 for i in range(n+1)]
    for i in range(1,n+1):
        for j in range(i,n+1):
            tmp = min(j-i,abs(x-i)+1+abs(j-y),abs(y-i)+1+abs(j-x))
            #print(i+1,j+1,tmp)
            dis[tmp] += 1
    for i in range(1,n):
        print(dis[i])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,X,Y = (int(x) for x in input().split())
A = [0]*(N)

for i in range(1,N):
    for j in range(i+1,N+1):
        if j <= X or i >= Y:
            A[j-i] += 1
        else:
            A[min((j-i),(abs(i-X)+abs(j-Y)+1))] += 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict
dic = defaultdict(int)
n,x,y = map(int,input().split())
for i in range(1,n+1):
    for j in range(i,n+1):
        val = min(abs(i-j), abs(x-i) + abs(y-j) + 1)
        dic[val] += 1
for i in range(1,n):
    print(dic[i])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

from collections import defaultdict

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

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

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, X, Y = getNM()

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

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

distance = [0] * N
def counter(sta):
    ignore = [0] * N
    ignore[sta] = 1
    pos = deque([[sta, 0]])

    while len(pos) > 0:
        u, dis = pos.popleft()
        for i in dist[u]:
            if ignore[i] == 0:
                ignore[i] = 1
                distance[dis + 1] += 1
                pos.append([i, dis + 1])
for i in range(N):
    counter(i)
for i in distance[1:]:
    print(i // 2)

Submission status: Accepted

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

Submission status: Accepted

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

res = deque()

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

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

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import combinations

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

c = Counter()
for i, j in combinations(range(1, N + 1), r=2):
    c[min(j - i, abs(X - i) + 1 + abs(j - Y))] += 1

for n in range(1, N):
    print(c[n])

Submission status: Accepted

Solution code:
# BFS

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

pic = [[] for _ in range(n+1)] #[]:dummy
for _ in range(1,n):
    pic[_].append(_+1)
    pic[_+1].append(_)
pic[x].append(y)
pic[y].append(x)
#print(pic)

ptns = [0 for _ in range(n)] # 0:dummy

from collections import deque

for i in range(1,n+1): #'i'を開始位置として各頂点までの最短距離を探索
    queue = deque([i]) # dequeオブジェクト、初期値は開始位置の'i'のみ
    dis = [None] * (n+1) # 'i'からの最短距離を初期化, 0:dummy含む
    dis[i] = 0 # 開始位置なので'0'
    
    while queue:
        v = queue.popleft() # v:探索元のノード 
        for j in pic[v]: # pic[v]: 探索元のノードに隣接するノード
            if dis[j] is None:
                dis[j] = dis[v] + 1
                queue.append(j)
    #print(dis)
    for k in dis[1:]: # 最短距離を集約
        ptns[k] += 1

for l in ptns[1:]: # 1以上の最短距離を出力
    print(l//2) # 往復分が記録されているため2で割る

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):
    for j in range(i+1, N):
        dist[min(j-i, abs(X-i) + 1 + abs(Y-j))-1] += 1

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

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

for v in ans:
    print(v)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    X -= 1
    Y -= 1

    ans = [0] * N

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    X -= 1
    Y -= 1

    ans = [0] * N

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, X, Y = map(int, readline().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)

    count = [0] * N

    for i in range(N):
        dist = [-1] * N
        dist[i] = 0
        queue = deque([i])
        while queue:
            v = queue.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    count[dist[nv]] += 1
                    queue.append(nv)

    ans = [c // 2 for c in count[1:]]
    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
nums = [int(i) for i in input().split()]
n = nums[0]
x = nums[1]
y = nums[2]
res = [0 for i in range(2010)]

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

Submission status: Accepted

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

x -= 1
y -= 1
cnt = [0]*n

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def main():
    input = sys.stdin.buffer.readline
    n, x, y = map(int, input().split())
    k_cnt = Counter()
    for i in range(1, n):
        for j in range(i + 1, n + 1):
            if i <= x:
                if j < y:
                    dist = min(j - i, (x - i) + 1 + (y - j))
                elif y <= j:
                    dist = (x - i) + 1 + (j - y)
            elif x < i < y:
                dist = min(j - i, (i - x) + 1 + abs(j - y))
            else:
                dist = j - i
            k_cnt[dist] += 1
    for i in range(1, n):
        print(k_cnt[i])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, X, Y = map(int, input().split())
ans = [0] * N
for i in range(N-1):
    dist_list = [-1] * N
    d = deque([[i]])
    dist = 0
    while d[0]:
        tag = d.popleft()
        next_tag = []
        for t in tag:
            if dist_list[t] == -1:
                dist_list[t] = dist
            if t - 1 >= 0:
                if dist_list[t - 1] == -1:
                    next_tag.append(t-1)
            if t + 1 < N:
                if dist_list[t + 1] == -1:
                    next_tag.append(t + 1)
            if t == X-1:
                if dist_list[Y-1] == -1:
                    next_tag.append(Y-1)
            if t == Y-1:
                if dist_list[X-1] == -1:
                    next_tag.append(X-1)
        d.append(next_tag)
        dist += 1
    for j in range(i+1, N):
        ans[dist_list[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
ans = [0] * N
for i in range(N):
    for j in range(i+1, N):
        ans[ min(j - i, abs(X - i) + 1 + abs(Y - j))] += 1
for i in range(1, N):
    print(ans[i])

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):
        d = min([abs(i-j), (abs(i-X) + 1 + abs(Y-j)), (abs(i-Y) + 1 + abs(X-j))])
        cnt[d] += 1
for i in range(1, N):
    print(cnt[i])

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[i-1,i+1] for i in range(n+1)]
graph[1]=[2]
graph[n]=[n-1]
graph[0]=[0]

graph[x].append(y)
graph[y].append(x)

def bfs(start,graph2):
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[start] = 0

    d = deque()
    d.append(start)
    while d:
        v = d.popleft()
        for i in graph2[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
        
    dist = dist[start+1:]
    return dist

ans=[0 for _ in range(n-1)]
for i in range(1,n+1):
    for j in bfs(i,graph):
        ans[j-1] +=1
 
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

for i in range(1, n):
    a = i - 1
    b = i
    g[a].append(b)
    g[b].append(a)
x -= 1
y -= 1
g[x].append(y)
g[y].append(x)


ans = [0] * n
for i in range(n):
    stack = deque()
    dis = [0] * n
    seen = [False] * n
    stack = deque()
    stack.append(i)
    seen[i] = True
    while stack:
        v = stack.popleft()
        for nv in g[v]:
            if seen[nv]:
                continue
            dis[nv] = dis[v] + 1
            seen[nv] = True
            stack.append(nv)
    for j in range(n):
        ans[dis[j]] += 1

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

Submission status: Accepted

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

    x -= 1
    y -= 1
    # assume vertices are numbered [0, n)

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

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

Submission status: Accepted

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

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

for i in range(1,n+1):
    bfs(i)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

for x in ans:
    print(x)

Submission status: Accepted

Solution code:
N,X,Y=map(int, input().split())
d = [0]+list(range(N-1, 0, -1))
X,Y=min(X,Y),max(X,Y)

for i in range(1,N):
  for j in range(i+1,N+1):
    if i<= X:
      if j>= Y:
        d[j-i] -=1
        d[j-Y+X-i+1] += 1
      else:
        if j > (X+Y)/2:
          d[j-i] -=1
          d[X-i+1+Y-j] += 1
    else:
      if i-X+abs(j-Y)+1 < j-i:
        d[j-i] -= 1
        d[i-X+abs(j-Y)+1] += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

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

def cal_dis(i, j):
    return min(j-i, abs(i-X)+abs(j-Y)+1)

for i in range(1, N+1):
    for j in range(i+1, N+1):
        k = cal_dis(i, j)
        ans[k-1] += 1

print('\n'.join(map(str, ans)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

n, x, y = map(int, input().split())
x -= 1
y -= 1
ans = [0 for _ in range(n - 1)]
for i, j in itertools.combinations(range(n), 2):
    d = min(abs(i - j), abs(i - x) + abs(j - y) + 1, abs(i - y) + abs(j - x) + 1)
    ans[d - 1] += 1
for num in ans:
    print(num)

Submission status: Accepted

Solution code:
from collections import Counter
def dis(i,j, x,y):
    return min(j-i, abs(x-i)+1+abs(j-y), abs(y-i)+1+(j-x))
n, x, y = map(int, input().split())
x,y = x-1,y-1
D = []
for i in range(n-1):
    for j in range(i+1, n):
        D.append(dis(i,j, x,y))
cD = Counter(D)
for i in range(1, n):
    print(cD[i])

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
INFTY=sys.maxsize

def readinput():
    n,x,y=list(map(int,input().split()))
    return n,x,y

def dijkstra(s,n,nList):
    '''優先度付きキューを使用したダイクストラ法

    パラメーター
    s: 始点
    n: 頂点の数
    nList: [ 
        [vertex1, cost1], [vertex2, cost2], ...
        [vertex1, cost1], [vertex2, cost2], ...
        ...
    ]

    返り値
    d: 始点sから各頂点vまでの最短経路上の辺の重みの総和d[v]のリスト
    '''

    WHITE=0
    GRAY=1
    BLACK=2
    color=[WHITE]*n
    d=[INFTY]*n

    HQ=[]

    d[s]=0
    heappush(HQ,(d[s],s))

    while(len(HQ)>0):
        #print(HQ)
        du,u=heappop(HQ)
        color[u]=BLACK

        if d[u]<du:
            continue

        for v in nList[u]:
            vw=1
            if color[v]!=BLACK:
                if d[u] + vw < d[v]:
                    d[v] = d[u] + vw
                    color[v]=GRAY
                    heappush(HQ, (d[v], v))
    return d

def main(n,x,y):
    nList=[]
    #nList.append([])
    nList.append([1])
    for i in range(1,n-1):
        nList.append([i-1,i+1])
    nList.append([n-2])
    nList[x-1].append(y-1)
    nList[y-1].append(x-1)
    #print(nList)

    dList=[]
    for i in range(n):
        dList.append(dijkstra(i,n,nList))
    #print(dList)
    
    hist=[0]*n
    for i in range(n-1):
        for j in range(i+1,n):
            hist[dList[i][j]]+=1
    
    for i in range(1,n):
        print(hist[i])

def main2(n,x,y):
    hist=[0]*n
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i<=x:
                if j<=x:
                    d=j-i
                elif x<j and j<=y:
                    d=min(j-i,x-i+1+y-j)
                else:
                    d=x-i+1+j-y
            elif x<i and i<=y:
                if j<=y:
                    d=min(j-i,i-x+1+y-j)
                else:
                    d=min(j-i,i-x+1+j-y)
            else:
                d=j-i
            #print(i,j,d)
            hist[d]+=1
    for i in range(1,n):
        print(hist[i])

if __name__=='__main__':
    n,x,y=readinput()
    main2(n,x,y)

Submission status: Accepted

Solution code:
import numpy as np
N, X, Y = [int(_) for _ in input().split()]
X -= 1
Y -= 1
cnt = np.zeros(N, dtype=int)
for i in range(0, (X + Y) // 2):
    #t-i<=abs(i-X)+1+Y-t
    #2*t<=abs(i-X)+1+Y+i
    #t<= tmax = 0 - - (abs(i-X)+1+Y+i)//2
    #tmin=abs(i-X)+1
    tmin = abs(i - X) + 1
    tmax = 0 - -(abs(i - X) + 1 + Y + i) // 2
    cnt[1:tmax - i] += 1
    cnt[tmin:tmin + Y - tmax + 1] += 1
    cnt[tmin + 1:tmin + N - Y] += 1
for i in range((X + Y) // 2, N):
    cnt[1:N - i] += 1
print(*cnt[1:], sep='\n')

Submission status: Accepted

Solution code:
import numpy as np
N, X, Y = [int(_) for _ in input().split()]
X -= 1
Y -= 1
cnt = np.zeros(N, dtype=int)
for i in range(0, (X + Y) // 2):
    #t-i<=abs(i-X)+1+Y-t
    #2*t<=abs(i-X)+1+Y+i
    #t<= tmax = 0 - - (abs(i-X)+1+Y+i)//2
    #tmin=i-X+1
    tmin = abs(i - X) + 1
    tmax = 0 - -(abs(i - X) + 1 + Y + i) // 2
    cnt[1:tmax - i] += 1
    cnt[tmin:tmin + Y - tmax + 1] += 1
    cnt[tmin + 1:tmin + N - Y] += 1
for i in range((X + Y) // 2, N):
    cnt[1:N - i] += 1
print(*cnt[1:], sep='\n')

Submission status: Accepted

Solution code:
import numpy as np
N, X, Y = [int(_) for _ in input().split()]
X -= 1
Y -= 1
cnt = np.zeros(N, dtype=int)
for i in range(0, (X + Y) // 2):
    #t-i<=abs(i-X)+1+Y-t
    #2*t<=abs(i-X)+1+Y+i
    #t<= tmax = 0 - - (abs(i-X)+1+Y+i)//2
    #tmin=i-X+1
    #range(tmin,tmin+Y-tmax) + range(1,tmax-i+1) + range(tmin+1,tmin+N-Y)
    tmin = abs(i - X) + 1
    tmax = 0 - -(abs(i - X) + 1 + Y + i) // 2
    cnt[1:tmax - i] += 1
    cnt[tmin:tmin + Y - tmax + 1] += 1
    cnt[tmin + 1:tmin + N - Y] += 1
for i in range((X + Y) // 2, N):
    cnt[1:N - i] += 1
print(*cnt[1:], sep='\n')

Submission status: Accepted

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


if __name__ == '__main__':
    main()