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 itertools import combinations

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N, X, Y = map(int, input().split())
# 全探索でいけるのでは？
# 有向グラフとしてN回幅優先すれば良いのでは？
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)
ans = defaultdict(int)
q = deque()
# 更新されない時はqに追加しない
for i in range(N):
    distant = [N]*N
    q.append(i)  # 始まりのノード
    distant[i] = 0
    while len(q):
        # vは数字, 親のノードのインデックス
        v = q.pop()
        for e in tree[v]:
            if distant[e] < distant[v]+1:  # 到達済みなら次のノードへ
                continue
            distant[e] = distant[v]+1
            q.append(e)
    for d in distant:
        ans[d] += 1
for i in range(1, N):
    print(ans[i]//2)

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

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

Submission status: Accepted

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

cnt_list = [0] * (n - 1)

for i in range(n):
    for j in range(n):
        if j <= i:
            continue
        
        #i < j,x < yのとき、i→y→x→jが最短になることはない
        num = min([j - i, abs(x - i) + 1 + abs(y - j)]) - 1 #距離 - 1、距離ゼロはif文で排除
        cnt_list[num] += 1

for n in cnt_list:
    print(n)

Submission status: Accepted

Solution code:

import collections


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

    inf = 10**9

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

    ans = [0]*N

    for i in range(N):
        q = collections.deque()
        dist = [inf]*N
        pus(i, 0, dist, q)

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

            if v-1 >= 0:
                pus(v-1, d+1, dist, q)
            if v+1 < N:
                pus(v+1, d+1, dist, q)
            if v == X-1:
                pus(Y-1, d+1, dist, q)
            if v == Y-1:
                pus(X-1, d+1, dist, q)

        for i in range(N):
            ans[dist[i]] += 1

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n, x, y = map(int, input().split())
ans = [0]*n
x, y = min(x, y), max(x, y)
 
for i in range(1, n):
    for j in range(i+1, n+1):
        # calculate dist(i, j)
        dist = j - i
        dist = min(dist, abs(j - y) + abs(x - i) + 1)
        dist = min(dist, abs(j - x) + abs(y - i) + 1)
        ans[dist] += 1
print("\n".join(list(map(str, ans[1:]))))

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

Submission status: Accepted

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

ans = [0] * (n-1)

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

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

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

Submission status: Accepted

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


def solve(N: int, X: int, Y: int):
    seen = [[False] * N] * N
    X -= 1
    Y -= 1
    cnt = []
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if seen[i][j]:
                continue
            seen[j][i] = True
            cnt.append(min(abs(j - i), abs(X - i) + 1 + abs(j - Y)))
    counter = collections.Counter(cnt)
    keys = counter.keys()
    for i in range(N):
        if i not in keys:
            print(0)
            continue
        print(counter[i])
    return


def solve2(N: int, X: int, Y: int):
    # BFS
    X -= 1
    Y -= 1
    G = [[] for _ in range(N)]
    for i in range(N):
        if not i == N - 1:
            G[i].append(i+1)
            G[i+1].append(i)
        if i == X:
            G[i].append(Y)
            G[Y].append(i)
        if i == Y:
            G[i].append(X)
            G[X].append(i)
    G = [list(set(x)) for x in G]
    q = deque([])
    ans = [0] * N
    # 各頂点をスタート地点として、他の点への移動にかかる最短距離を求めて集計する
    for i in range(N):
        dist = [-1] * N
        dist[i] = 0
        q.append(i)
        while(len(q) > 0):
            v = q.pop()
            for nv in G[v]:
                if not dist[nv] == -1:
                    continue
                dist[nv] = dist[v] + 1
                q.appendleft(nv)
        for d in dist:
            ans[d] += 1
    for i in range(N):
        ans[i] //= 2
    for i in range(1, N):
        print(ans[i])
    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
    solve2(N, X, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
    Template written to be used by Python Programmers.
    Use at your own risk!!!!
    Owned by enraged(rating - 5 star at CodeChef and Specialist at Codeforces).
"""
import sys
from functools import lru_cache
from collections import defaultdict as dd
def data(): return sys.stdin.readline().strip()
def out(var): sys.stdout.write(str(var))
def outln(var): sys.stdout.write(str(var)+"\n")
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, x, y = sp()
dp = dd(int)
for i in range(1, n):
    for j in range(i+1, n+1):
        answer = min(abs(j-i), abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(j-x))
        dp[answer] += 1
for i in range(1, n):
    outln(dp[i])

Submission status: Accepted

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

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

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

for index in range(1, len(List)):
    print(List[index])

Submission status: Accepted

Solution code:
import unittest


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(5, 2, 4), [5, 4, 1, 0])

    def test_2(self):
        self.assertEqual(think(3, 1, 3), [3, 0])

    def test_3(self):
        self.assertEqual(think(7, 3, 7), [7, 8, 4, 2, 0, 0])

    def test_4(self):
        self.assertEqual(think(10, 4, 8), [10, 12, 10, 8, 4, 1, 0, 0, 0])


def solve():
    n, x, y = read()
    result = think(n, x, y)
    write(result)


def read():
    return read_int(3)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, x, y):
    result = [0] * n
    for i in range(1, n):
        for j in range(i + 1, n + 1):
            minimum_distance = min(j - i, 1 + abs(x - i) + abs(y - j))
            result[minimum_distance] += 1
    return result[1:]


def write(result):
    for r in result:
        print(r)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

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

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

edge = tuple([0]*N for i in range(N))

for i in range(N-1):
    edge[i][i+1] = 1
    edge[i+1][i] = 1

edge[X-1][Y-1] = 1
edge[Y-1][X-1] = 1

ans = np.array(dijkstra(edge),dtype="int32")
cnt = [0]*N
for i in range(N):
    for j in ans[i]:
        cnt[j] += 1

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

Submission status: Accepted

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

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

edge = tuple([0]*N for i in range(N))

for i in range(N-1):
    edge[i][i+1] = 1
    edge[i+1][i] = 1

edge[X-1][Y-1] = 1
edge[Y-1][X-1] = 1

edge_n = np.array(edge)
ans = dijkstra(edge_n)
ans = np.array(ans,dtype="int32")
cnt = [0]*N
for i in range(N):
    for j in ans[i]:
        cnt[j] += 1

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

edge = [[0]*N for i in range(N)]

for i in range(N-1):
    edge[i][i+1] = 1
    edge[i+1][i] = 1

edge[X-1][Y-1] = 1
edge[Y-1][X-1] = 1

edge_n = np.array(edge)
ans = dijkstra(edge_n)
ans = np.array(ans,dtype="int32")
cnt = [0]*N
for i in range(N):
    for j in ans[i]:
        cnt[j] += 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# D - Line++
from collections import deque

INF = 1001001001

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

for i in range(n):
    dist = [INF]*n
    q = deque()
    dist[i] = 0
    q.append(i)
    
    while len(q)>0:
        v = q.popleft()
        d = dist[v]
        if v-1 >= 0 and dist[v-1]==INF:
            q.append(v-1)
            dist[v-1]=d+1
        if v+1 < n and dist[v+1]==INF:
            q.append(v+1)
            dist[v+1]=d+1
        if v==x and dist[y]==INF:
            q.append(y)
            dist[y]=d+1
        if v==y and dist[x]==INF:
            q.append(x)
            dist[x]=d+1
    for d in dist:
        ans[d] += 1

for a in ans[1:]:
    print(int(a//2))

Submission status: Accepted

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

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

Submission status: Accepted

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

for s in range(n):
    for t in range(s, n):
        u = min((t-s), abs(x-s) + 1 + abs(y-t), abs(x-t) + 1 + abs(y-s))
        ans[u] += 1

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

Submission status: Accepted

Solution code:
'''
ID: essi
LANG: PYTHON3
TASK: ‌D.py
''' 
# edge between x and y make the way.
# for every pair of vertix we have two way if x <= j
n, x, y = map(int,input().split())
k = [0] * n
k[0] = n # nothing
for i in range(1, n):
	for j in range(i + 1, n + 1):
		if x > j:
			k[j - i]+= 1
		else:
			way = abs(i-x) + 1 + abs(y-j)
			#way = min(abs(i-y) + 1 + abs(x-j), way)
			k[min(j - i, way)]+= 1	
for i in range(1, n):
	print(k[i])

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, X, Y = map(int, input().split())
    ans = [0] * N  # 距離ごとの合計 [d=0, d=1, d=2, d=3, d=4]の数
    X -= 1
    Y -= 1

    for start_vertex in range(N):
        dist = [float('inf')] * N
        q = deque()

        def push(vertex, distance):
            if dist[vertex] != float('inf'):
                return
            dist[vertex] = distance
            q.append(vertex)

        push(start_vertex, 0)  # 始点をpush

        while len(q) != 0:
            vertex = q.popleft()
            distance = dist[vertex]

            if vertex - 1 >= 0:
                push(vertex - 1, distance + 1)
            if vertex + 1 < N:
                push(vertex + 1, distance + 1)
            if vertex == X:
                push(Y, distance + 1)
            if vertex == Y:
                push(X, distance + 1)

        for i in range(N):
            ans[dist[i]] += 1

    for i in range(N):
        ans[i] //= 2

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def min_dist(a,b):
    return min(b-a, abs(x-a)+1+abs(y-b), abs(x-b)+1+abs(y-a))
for i in range(n):
    for j in range(i, n):
        ans_l[min_dist(i,j)] += 1
print('\n'.join([str(ans) for ans in ans_l[1:]]))

Submission status: Accepted

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

def min_dist(a,b):
    return min(b-a, abs(x-a)+1+abs(y-b), abs(x-b)+1+abs(y-a))
for i in range(n):
    for j in range(i, n):
        ans_l[min_dist(i,j)] += 1
for ans in ans_l[1:]:
    print(ans)

Submission status: Accepted

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

def min_dist(a,b):
    return min(b-a, abs(x-a)+1+abs(y-b), abs(x-b)+1+abs(y-a))
for i in range(n):
    for j in range(i, n):
        k = min_dist(i,j)
        ans_l[k] += 1
for ans in ans_l[1:]:
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
ks = [0]*(N-1)
for A in range(1,N):
    for B in range(A+1,N+1):
        if B - A > abs(X -A) + abs(Y - B) + 1:
            ks[B-A-1] -= 1
            ks[abs(X -A) + abs(Y - B)] += 1
for k in range(1,N):
    print(N - k + ks[k-1])

Submission status: Accepted

Solution code:
from collections import Counter

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

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

Submission status: Accepted

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

def distance( i, j ):
  wapu =  abs( x - i )
  wapu += 1
  wapu += abs( y - j )
  return min( ( j - i ), wapu )

ret_list = [ 0 ] * n
for i in range( 1, n + 1 ):
  for j in range( i+1, n + 1 ):
    ret_list[ distance( i, j ) ] += 1

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

Submission status: Accepted

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

m = {i:[] for i in range(1, N+1)}
for i in range(1, N+1):
    if i > 1:
        m[i].append(i-1)
    if i < N:
        m[i].append(i+1)
m[X].append(Y)
m[Y].append(X)

# print(m)

from collections import deque

dists = [[]]
for i in range(1, N+1):
    dist = [float('inf')]*(N+1)
    dist[i] = 0
    q = deque([i])
    while q:
        p = q.popleft()
        for j in m[p]:
            if dist[j] > dist[p]+1:
                dist[j] = dist[p]+1
                q.append(j)
    dists.append(dist)

# print(dists)

ansm = {i:0 for i in range(1, N+1)}
for i in range(1, N+1):
    for j in range(1, N+1):
        if dists[i][j] == 0:
            continue
        ansm[dists[i][j]] += 1

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

Submission status: Accepted

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n, x, y = map(int, sys.stdin.readline().split())
	x -= 1
	y -= 1
	ans = [0]*(n-1)
	for i in range(n):
		for j in range(i+1, n):
			log.print(i, j, ans)
			if i == j:
				continue
			if (i <= x and j <= x) or (y <= i and y <= j):
				ans[abs(i-j)-1] += 1
			elif (i <= x and y <= j):
				ans[x-i + j-y + 1 - 1] += 1
			elif (x < i < y and x < j < y):
				ans[min(abs(i-j), i-x + 1 + y-j)-1] += 1
			elif (i <= x and x < j < y):
				ans[min(abs(i-j), x-i + 1 + y-j)-1] += 1
			elif (x < i < y and y <= j):
				ans[min(abs(i-j), j-y + 1 + i-x)-1] += 1
	for i in range(len(ans)):
		print(ans[i])







main()

Submission status: Accepted

Solution code:
import sys


def input() -> str:
    return sys.stdin.readline().rstrip("\r\n")


def main():
    def min_dest(a, b):
        return min(b-a, abs(x-a)+1+abs(y-b))

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

    for i in range(n):
        for j in range(i+1, n):
            ans[min_dest(i, j)-1] += 1
    for a in ans:
        print(a)


if __name__ == "__main__":

    main()

Submission status: Accepted

Solution code:
import sys


def input() -> str:
    return sys.stdin.readline().rstrip("\r\n")


def main():
    def min_dest(a, b):
        return min(b-a, abs(x-a)+1+abs(y-b), abs(x-b)+1+abs(y-a))

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

    for i in range(n):
        for j in range(i+1, n):
            ans[min_dest(i, j)-1] += 1
    for a in ans:
        print(a)


if __name__ == "__main__":

    main()

Submission status: Accepted

Solution code:
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, x, y = map(int, input().split())
ans = {x: 0 for x in range(1, n)}

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

for v in ans.values():
    print(v)

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

Submission status: Accepted

Solution code:
N,X,Y = map(int,input().split())
from collections import defaultdict as ddict
ans = ddict(int)
for n in range(N):
    for i in range(n+1,N):
        s = i+1
        d = n+1
        p1 = abs(s-d)
        p2 = abs(s-X)+abs(d-Y)+1
        p3 = abs(s-Y)+abs(d-X)+1
        ans[min(p1,p2,p3)] += 1
for n in range(1,N):
    print(ans[n])

Submission status: Accepted

Solution code:
n,x,y = map(int,input().split())
from collections import defaultdict,deque
gr = defaultdict(list)
for i in range(1,n):
  gr[i].append(i+1)
  gr[i+1].append(i)
gr[x].append(y)
gr[y].append(x)

res  = defaultdict(int)
for i in range(1,n+1):
  q = deque()
  q.append(i)
  vis = {}
  vis[i] = 0
  while q:
    tmp = q.popleft()
    for item in gr[tmp]:
      if item not in vis:
        vis[item] = vis[tmp]+1
        q.append(item)
  for j in range(i+1,n+1):
    res[vis[j]]+=1
for i in range(1,n):
  print(res[i])

Submission status: Accepted

Solution code:
# D - Line++

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):
         tmp = min(j-i, abs(i-X)+abs(j-Y)+1)
         cnt[tmp] += 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


N, X, Y = inp_list()

"""
    XY間のショートカット経路を使う場合と使わない場合の距離をそれぞれ計算して、
    その小さい方が最短経路。
"""

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

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

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
D = [None] + [0] * (N - 1) #最低距離が1からNまでの個数を表示するリストを作る(YZT さんのコメント)

#各最低距離の個数カウント
for i in range(1, N):                           # i 出発
    for j in range(i + 1, N + 1):               # j 到着
        d = min(abs(j - i),                     # 近道をしない
                abs(X - i) + 1 + abs(j - Y),    # 「+1」は近道の距離、X < Y　
                abs(Y - i) + 1 + abs(j - X))    # 「+1」は近道の距離、Y < X　
        D[d] += 1                               # 距離ｄごとにカウント
        # print(abs(j-i),abs(X-i)+1 , abs(j-Y) , abs(Y - i) + 1,abs(j - X)," ",d,D," ",i,j)
    
for d in D[1:]: #最低距離は１だから距離０は使わないが、添え字＝距離とすることでわかりやすい
    print(d)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def PL(L) : print(*L, sep="\n")

N, X, Y = LI()

ans = [0] * N

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

PL(ans[1:])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
 
i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

n,x,y = i_l()
x -= 1
y -= 1
a = [0]*n

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

Submission status: Accepted

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

Ans=[0]*N

i=1
d=0
while i<=N:
    j=i+1
    while j<=N:
        d=(min(j-i,abs(X-i)+1+abs(j-Y)))
        Ans[d]+=1
        j+=1
    i+=1

k=1
while k<=N-1:
    print(Ans[k])
    k+=1

Submission status: Accepted

Solution code:
# coding: utf-8

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

n_k = [0] * (N+1)

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

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

Submission status: Accepted

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

#直線グラフの作成
g = [[]  for i in range(N)]
for i in range(N):
    u = i
    v = i + 1
    if v < N:
        g[u].append(v)
        g[v].append(u)

#辺を一つたす
g[X - 1].append(Y - 1)
g[Y - 1].append(X - 1)

from collections import deque
#dis = iとjの最短距離（表N＊Nの表）
dis = [[float('Inf')] * N for _ in range(N)]
#count = 最短距離の頂点組み合わせ数
count = [0] * (N - 1)

def bfs(i):#頂点iについてのbfs
    d = [False] * N #行ってないとこはFalse,いったとこはTrue
    que = deque()
    #for j in g[i]:
    que.append(i)#最初にi(最初の頂点)を追加
    d[i] = True#いったとこはTrue
    dis[i][i] = 0#自分は距離0
    #pre = i
    while que:
        p = que.popleft()

        for k in g[p]:#グラフの中にある間は
            if d[k]:#kがいったことあったらスルー
                continue
            else:
                d[k] = True#kがいったことなかったら、遷移先（k）にプラス１する
                que.append(k)
                dis[i][k] = dis[i][p] + 1
                #dis[k][i] = dis[i][p] + 1
                count[dis[i][k] - 1] += 1#indexは-１になる。
                #count[dis[k][i] - 1] += 1
        #pre = p

for i in range(N):#すべての頂点を起点にしてBFS
    bfs(i)

for i in range(N - 1):
    print(count[i] // 2)#（i,j）についてはi起点とj起点で二回加えているので、半分にする

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,X,Y=map(int,input().split())
def shortest(x,y,a,b):
    ans=min(y-x,abs(y-b)+1+abs(a-x))
    return ans
distance=[0]*(N-1)
for x in range(1,N):
    for y in range(2,N+1):
        if y<=x:
            continue
        a=shortest(x,y,X,Y)
        distance[a-1]+=1
for i in distance:
    print(i)

Submission status: Accepted

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

ans = [0]*(n-1)

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

for i in ans:
  print(i)

Submission status: Accepted

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

dist = [i*0 for i in range(N)]


for i in range(1,N+1):
  for j in range(i,N+1):
    if(i==j):
      continue
    a = abs(i-j)
    b = abs(X-i)+1+abs(Y-j)
    #c = abs(X-j)+1+abs(Y-i)
    
    #print(str(min(a,b,c))+' when ('+str(i)+','+str(j)+')')
    dist[min(a,b)]+=1
    #if(j>X):
    #  if(j<X+((Y-X)/2)):
    #    dist[N-(Y-X)+(int((Y-X)/2) - 1) - j] += 1
    #  else:
    #    dist[N-1-j]+=1
    #else:
    #  dist[N-(Y-X)-j]+=1
#print(Pi)
#dist=[]
#dist.append(abs(Ai[N-1]-Ai[0]))
#for i in range(N-1):
#  dist.append(abs((K+Ai[i])-Ai[i+1]))

#print(min(dist))
#print(dist)
  
#Pi.sort(reverse=True)
#Qi.sort()
#Ri.sort()

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

Submission status: Accepted

Solution code:
from collections import deque

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


def node_search(i):
    node_list = []
    if i != 1:
        node_list.append(i-1)
    if i != N:
        node_list.append(i+1)
    if i == X:
        node_list.append(Y)
    if i == Y:
        node_list.append(X)
    return node_list


def bfs(k):
    q = deque()
    dist = [N]*(N+1)
    q.append(k)
    check = [0]*(N+1)
    check[k] = 1
    dist[k] = 0
    while q:
        now_node = q.pop()
        check[now_node] = 1
        next_nodes = node_search(now_node)
        for node in next_nodes:
            if check[node] == 0:
                dist[node] = min(dist[now_node]+1, dist[node])
                q.appendleft(node)
    return dist


ans = [0]*N
for k in range(1, N+1):
    dist_list = bfs(k)
    for i in range(k+1, N+1):
        ans[dist_list[i]] += 1

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

Submission status: Accepted

Solution code:
def MI():return map(int,input().split())
def LI():return list(MI())

from collections import deque
INF=float("inf")
n,x,y=MI()
x-=1
y-=1
ans=[0]*n

for sv in range(n):
  dist=[INF]*n
  q=deque()
  def push(v,d):
    if dist[v]!=INF:
      return
    dist[v]=d
    q.append(v)
  push(sv,0)
  while q:
    v=q.popleft()
    d=dist[v]
    if v-1>=0:push(v-1,d+1)
    if v+1<n:push(v+1,d+1)  
    if v==x:push(y,d+1)
    if v==y:push(x,d+1)
        
  for i in range(n):ans[dist[i]]+=1
for i in range(1,n):print(ans[i]//2)

Submission status: Accepted

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

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

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

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

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

for v in D[1:N]:
    print(v)

Submission status: Accepted

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

dist = [i*0 for i in range(N)]


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

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