Problem:


Score : 400 points

Problem Statement

We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:

For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.

There is an edge between Vertex X and Vertex Y.

For each k=1,2,...,N-1, solve the problem below:

Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

Constraints

3 \leq N \leq 2 \times 10^3

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

For each k=1, 2, ..., N-1 in this order, print a line containing the answer to the problem.

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

There are five pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).

There are four pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).

There is one pair (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 3: (1,5).

There are no pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 4.

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Accepted

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

dist_from_X = list(abs(i - (X - 1)) for i in range(N))
dist_from_Y = list(abs(i - (Y - 1)) for i in range(N))

ans_list = [0] * N

for i in range(N):
    for j in range(i, N):
        i_X_Y_j = dist_from_X[i] + 1 + dist_from_Y[j]
        i_Y_X_j = dist_from_Y[i] + 1 + dist_from_X[j]
        i_j = abs(i - j)
        min_dist_i_j = min(i_X_Y_j, i_Y_X_j, i_j)
        ans_list[min_dist_i_j] += 1

for num in ans_list[1:]:
    print(num)

Submission status: Accepted

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

Submission status: Accepted

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

x -= 1
y -= 1

dis = [[-1]*n for _ in range(n)]
dis_cnt = [0]*(n-1)

for i in range(n):
  for j in range(n):
    if i>j:
      continue
    dis[i][j] = min( abs(j-i), abs(x-i) + abs(j-y) + 1, abs(y-i) + abs(j-x)+1 )
    if dis[i][j]>0:
      dis_cnt[dis[i][j]-1] += 1
    
#print(dis_cnt)
[print(dis_cnt[i]) for i in range(n-1)]

Submission status: Accepted

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

from collections import defaultdict,deque
cnt = defaultdict(int)

INF = 10 ** 18

def bfs(n):
    que = deque([n])
    dist = [INF] * (N + 2)
    dist[n] = 0
    dist[0] = -INF
    dist[N + 1] = -INF
    
    while que:
        v = que.popleft()
        d = dist[v]

        # VIP
        if v == X:
            if dist[Y] > d + 1:
                dist[Y] = d + 1
                que.appendleft(Y)
        elif v == Y:
            if dist[X] > d + 1:
                dist[X] = d + 1
                que.appendleft(X)

        # --
        if dist[v - 1] > d + 1:
            dist[v - 1] = d + 1
            que.append(v - 1)
        
        # ++
        if dist[v + 1] > d + 1:
            dist[v + 1] = d + 1
            que.append(v + 1)
    
    for i in range(n+1, N+1):
        cnt[dist[i]] += 1


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

Submission status: Accepted

Solution code:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N, X, Y = map(int, read().split())

dist = []
for i in range(1, N):
    x = np.arange(i + 1, N + 1)
    # 直接
    d1 = np.abs(x - i)
    # i -> X -> Y -> x
    d2 = np.abs(i - X) + np.abs(Y - x) + 1
    # i -> Y -> X -> x
    d3 = np.abs(i - Y) + np.abs(X - x) + 1
    d = np.minimum(np.minimum(d1, d2), d3)
    dist.append(d)

dist = np.concatenate(dist)
count = np.bincount(dist, minlength=N)
print('\n'.join(count[1:].astype(str)))

Submission status: Accepted

Solution code:
from sys import stdin
n,x,y = [int(x) for x in stdin.readline().rstrip().split()]
a = [0] * n
for i in range(x):
    a[i] = x - (i+1)
k = y - x
if k % 2 == 1:
    k = k//2 + 1
    for i in range(k):
        a[i+x] = i+1
        a[y-1-i] = i+1
else:
    k = k//2 
    for i in range(k):
        a[i+x] = i+1
        a[y-1-i] = i+1
for i in range(n-y):
    a[y+i] = a[y-1]+i+1
c = [0] * n
for i in range(n):
    for j in range(i+1,n):
        A = j-i
        B = abs(x-1 - i) + a[j]
        p = min(A,B)
        c[p] += 1
for i in range(n-1):
    print(c[i+1])

Submission status: Accepted

Solution code:
N,X,Y = map(int,input().split())
X -=1
Y-=1
dist_dict = {i:0 for i in range(1,N)}
for i in range(N-1):
    for j in range(i+1,N):
        d0 = j -i
        d1 = abs(X-i) + 1 + abs(j-Y)
        d = min(d0,d1)
        dist_dict[d] += 1
for i in range(1,N):
    print(dist_dict[i])

Submission status: Accepted

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

            count[j-i-(Y-X)+1] += 1
        else:
            # print(i, j, j-i)
            # min((j-i), abs(X-i)+abs(Y-j)+1)

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

from itertools import combinations

n,x,y=map(int,readline().split())
dis=[0]*n
lst=list(range(1,n+1))
for a,b in combinations(lst,2):
  if b<=x or a>=y:
    dist=b-a
  else:
    dist=min(b-a, abs(x-a)+abs(y-b)+1)
  dis[dist]+=1
print(*dis[1:],sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N, X, Y = map(int, read().split())

dist = []
for i in range(1, N):
    x = np.arange(i+1, N + 1)
    # 直接
    d1 = np.abs(x - i)
    # i -> X -> Y -> x
    d2 = np.abs(i - X) + np.abs(Y - x) + 1
    # i -> Y -> X -> x
    d3 = np.abs(i - Y) + np.abs(X - x) + 1
    d = np.minimum(np.minimum(d1, d2), d3)
    dist.append(d)

dist = np.concatenate(dist)
count = np.bincount(dist, minlength=N)
print('\n'.join(count[1:].astype(str)))

Submission status: Accepted

Solution code:
import math
N, X, Y = map(int, input().split())
d = [[0]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
  for j in range(1,N+1):
    d[i][j] = abs(j-i)
#print(d[1][3])

for i in range(1,X+1):
  for j in range(int((X+Y)/2)+1,N+1):
    d[i][j]= abs(Y-j)+1+(X-i)
#print(d[1][3])
for i in range(X,Y+1):
  for j in range(X,Y+1):
    d[i][j]= min(abs(j-i),min(i,j)-X+Y-max(i,j)+1)
#print(d[1][3]) 
for i in range(X+1,math.ceil((X+Y)/2)):
  for j in range(Y,N+1):
    d[i][j]= (j-Y)+1+(i-X)

#print(d[1][3])
ans = [0]*N
for i in range(1,N):
  for j in range(i+1,N+1):
    ans[d[i][j]] += 1

#print(ans)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


n, x, y = [0] * 3

def format_input(filename = None):
	global n, x, y
	if filename == None:
		n, x, y = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(3, 2 * 10**3)
		x = rng(1, n-1)
		y = rng(x+1, n)
		print(n, x, y)

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

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

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

if __name__ == '__main__':
	format_input()

	get_answer()

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

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

Submission status: Accepted

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

dist_dict = {i:0 for i in range(1,N)}
for i in range(N-1):
    for j in range(i+1,N):
        # XYパスを使わない場合
        d0 = j -i
        # XY パスを使う場合
        d1 = abs(X-i) + 1 + abs(j-Y)

        d = min(d0,d1)
        dist_dict[d] += 1
for i in range(1,N):
    print(dist_dict[i])

Submission status: Accepted

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

ans[x-1][y-1] = 1
ans[y-1][x-1] = 1
for i in range(n):
  for j in range(n):
    if ans[i][j] > ans[i][x-1]+ans[x-1][j]:
      ans[i][j] = ans[i][x-1]+ans[x-1][j]
    
for i in range(n):
  for j in range(n):
    if ans[i][j] > ans[i][y-1]+ans[y-1][j]:
      ans[i][j] = ans[i][y-1]+ans[y-1][j]

answer = [0]*(n-1)
for i in range(n):
  for j in range(n):
    if ans[i][j] == n or ans[i][j] == 0:
      continue
    answer[ans[i][j]-1] += 1
for i in range(n-1):
  print(answer[i]//2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,x,y = map(int,input().split())
al = [0 for i in range(n-1)]
for i in range(1,n):
    for j in range(i+1,n+1):
        if i <= x:
            if j <= x:
                al[j-i-1] += 1
            elif j <= y:
                now = min(j-i,y-j+(x-i)+1)
                al[now-1] += 1
            else:
                al[j-y+(x-i)] += 1
        elif i <= y:
            if j <= y:
                now = min(j-i,y-j+(i-x)+1)
                al[now-1] += 1
            else:
                now = min(j-i,j-y+(i-x)+1)
                al[now-1] += 1
        else:
            al[j-i-1] += 1
for i in al:
    print(i)

Submission status: Accepted

Solution code:
N,X,Y=map(int,input().split())
X-=1
Y-=1
#ld=[[0 for _ in range(N)] for _ in range(N)]
lnd=[0 for _ in range(N)]#sonomama
for i in range(N):
    for j in range(i+1,N):
        if (0<=i<=X and 0<=j<=X) or (Y<=i<=N-1 and Y<=j<=N-1):
            #ld[i][j]=j-i
            lnd[j-i]+=1

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

Submission status: Accepted

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

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


    mn=min(a,b)
    #print(i+1,j+1,a,b,mn)
    ans[mn-1]+=1
    



for x in ans:
  print(x)

#print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

x -= 1
y -= 1

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

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

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    N, X, Y = (int(i) for i in input().split())
    X -= 1
    Y -= 1
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        edge[i].append(i+1)
        edge[i+1].append(i)
    edge[X].append(Y)
    edge[Y].append(X)

    def bfs(s):
        d = [-1 for _ in range(N)]
        que = deque()
        d[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for v in edge[u]:
                if d[v] != -1:
                    continue
                d[v] = d[u] + 1
                que.append(v)
        return d

    dist = [[] for _ in range(N)]
    for i in range(N):
        dist[i] = bfs(i)
    cnt = [0]*N
    for i in range(N):
        for j in range(i+1, N):
            cnt[dist[i][j]] += 1
    for c in cnt[1:]:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
from re import split
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy
import re

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, x, y = LI()
G = [[] for _ in range(n)]
ans = [0] * (n - 1)
for i in range(n - 1):
    G[i] += [i + 1]
    G[i + 1] += [i]

for j in range(n):
    q = [j]
    par = [-1] * n
    dist = [-1] * n
    dist[j] = 0
    while q:
        u = q.pop()
        for v in G[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q += [v]
    flag = [0] * n
    q2 = [x - 1, y - 1]
    dist[x - 1] = min(dist[x - 1], dist[y - 1] + 1)
    dist[y - 1] = min(dist[y - 1], dist[x - 1] + 1)
    while q2:
        a = q2.pop()
        for b in G[a]:
            if dist[a] + 1 < dist[b]:
                dist[b] = dist[a] + 1
                q2 += [b]

    for k in range(n):
        if k == j: 
            continue
        else:
            ans[dist[k] - 1] += 1


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

Submission status: Accepted

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


def solve(N: int, X: int, Y: int):
    D = [0 for _ in range(N)]
    for i in range(N):
        for j in range(i+1, N):
            if j <= X-1:
                d = j - i
            elif i >= Y-1:
                d = j - i
            else:
                d = min(j-i, abs(i-X+1)+abs(j-Y+1)+1)
            D[d] += 1
    for i in range(N-1):
        print(D[i+1])
    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:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

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

ans=[0]*n
for i in range(n):
  a=dijkstra_heap(i,edge)
  # print(a)
  for x in a[i:]:
    ans[x]+=1

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

Submission status: Accepted

Solution code:
def calc(N, X, Y):
    X -= 1
    Y -= 1
    d = {i: 0 for i in range(N)}
    for i in range(N):
        for j in range(i, N):
            e = min(
                abs(j - i),
                abs(X - i) + 1 + abs(Y - j),
                abs(Y - i) + 1 + abs(X - j)
                )
            d[e] += 1
    ans = '\n'.join([str(d[i]) for i in range(1, N)])
    return ans



(N, X, Y) = tuple([int(s) for s in input().split()])
print(calc(N, X, Y))

Submission status: Accepted

Solution code:
N,X,Y=map(int,input().split())
c=[[1]]+[[i-1,i+1] for i in range(1,N-1)]+[[N-2]]
c[X-1].append(Y-1)
c[Y-1].append(X-1)
from collections import deque
q=deque()
a=[0]*(N-1)
for i in range(N):
    d=[-1]*N
    d[i]=0
    q.append(i)
    while q:
        p=q.popleft()
        for n in c[p]:
            if d[n]<0:
                q.append(n)
                d[n]=d[p]+1
                a[d[p]]+=1
print(*[i//2 for i in a],sep='\n')

Submission status: Accepted

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

Submission status: Accepted

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

G = [[] for i in range(N)]
for i in range(N):
    if i == X-1:
        G[i].append(Y-1)
    if i == Y-1:
        G[i].append(X-1)

    if i == 0:
        G[i].append(1)
    elif i == N-1:
        G[i].append(N-2)
    else:
        G[i].append(i+1)
        G[i].append(i-1)

ans = [0]*(N-1)
for s in range(N):
    dist = [-1]*N
    q = deque([])
    q.append(s)
    dist[s] = 0

    while len(q) != 0:
        v = q.popleft()
        for nv in G[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v] + 1
            q.append(nv)
    for d in dist:
        if d != 0:
            ans[d-1] += 1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N, X, Y = [int(str) for str in input().strip().split()]

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from math import *


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

d = y - x + 1
res = [0] * n
for i in range(n):
    for j in range(i + 1, n):
        if j <= x:
            res[j-i] += 1
        elif i >= y:
            res[j-i] += 1
        elif i >= x and j <= y:
            t = min(j - i, d - j + i)
            res[t] += 1
        elif i <= x and  x <= j <= y:
            d1 = x - i
            t = d1 + min(j - x, d - j + x)
            res[t] += 1
        elif y >= i >= x  and j >= y:
            d1 = j - y
            t = d1 + min(y - i, d - y + i)
            res[t] += 1
        else:
            res[j - i - d + 2] += 1
            

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

Submission status: Accepted

Solution code:
from collections import deque

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

ret = [0] * N

vec = [[] for _ in range(N)]
for i in range(N - 1) :
  vec[i].append(i + 1)
  vec[i + 1].append(i)
vec[X - 1].append(Y - 1)
vec[Y - 1].append(X - 1)
  
for i in range(N) :
  dist = [-1] * N
  dist[i] = 0
  q = deque([i])
  while q :
    cur = q.popleft()
    cd = dist[cur]
    for nex in vec[cur] :
      if dist[nex] != -1 : continue
      q.append(nex)
      dist[nex] = cd + 1
  
  for i in range(N) :
    ret[dist[i]] += 1
    
    
for i in range(1, N) :
  print(ret[i] // 2)

Submission status: Accepted

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

def main():
     n, x, y = map(int, input().split())
     ans = [0 for i in range(n)]

     for i in range(1, n+1):
          for j in range(i+1, n+1):
               route_a = j - i
               route_b = abs(x-i) + abs(j-y) + 1
               dis = min(route_a, route_b)
               # print('i:{}, j:{}, dis:{}, r_a:{}, r_b:{}'.format(i, j, dis, route_a, route_b))
               ans[dis] += 1
     
     print('\n'.join(map(str, ans[1:])))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, x, y = map(int, input().split())
count = [0]*(n-1)

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

for ci in count:
    print(ci)

Submission status: Accepted

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

n, x, y = map(int, input().split())
ans = [0] * (n - 1)
for i in range(n):
    check = 0
    for j in range(i + 1, n):
        check += 1
        if x - 1 <= i:
            a = i - x + 1
        else:
            a = x - 1 - i
        if y - 1 <= j:
            b = j - y + 1
        else:
            b = y - 1 - j
        cnt = min(check, a + b + 1)
        ans[cnt - 1] += 1
for i in range(n - 1):
    print(ans[i])

Submission status: Accepted

Solution code:
import itertools

N, X, Y = map(int, input().split())
lst = [0] * N
for l, r in itertools.combinations(range(1, N + 1), 2):
    lst[min(r - l, abs(r - Y) + 1 + abs(l - X))] += 1
for i in range(1, N):
    print(lst[i])

Submission status: Accepted

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

counts = [0 for _ in range(N-1)]

for n1 in range(1, N):
  for n2 in range(n1+1, N+1):
    if n2 >= Y:
      upper = n2 - Y
    else:
      upper = Y - n2
    if n1 <= X:
      lower = X - n1
    else:
      lower = n1 - X
    diff = min(n2 - n1, upper + lower + 1)
    counts[diff-1] += 1
for c in counts:
  print(c)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

l = [[0 for _ in range(N)] for _ in range(N)]

for i in range(1,N):
    l[i-1][i] = 1
    l[i][i-1] = 1
l[X-1][Y-1] = 1
l[Y-1][X-1] = 1

a = np.array(l)

cnt = 1
ans = [0]*(N+1)
for i in shortest_path(a):
    for j in range(cnt,N):
        ans[int(i[j])] += 1
    cnt += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

def get_shortest_path(i, j, x, y):
  base_dist = j - i
  dist_short = abs(x-i) + abs(y-j) + 1
  return min(base_dist, dist_short)

for i in range(n-1):
  for j in range(i+1, n):
    dist = get_shortest_path(i, j, x-1, y-1)
    res_list[dist-1] += 1
for i in range(n-1):
  print(res_list[i])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

for a in ansl:
    print(a)

Submission status: Accepted

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

n, x, y = list(map(int, input().split()))
graph = [0] + [[] for _ in range(n)]
for i in range(n - 1):
    graph[i+1].append(i+2)
    graph[i+2].append(i+1)
graph[x].append(y)
graph[y].append(x)

def bfs(graph, queue, dist, num):
    while queue:
        current = queue.pop(0)

        for c in graph[current]:
            if dist[c] != -1:
                continue
            dist[c] = dist[current] + 1
            num[dist[c]] += 1
            queue.append(c)

num = [0] + [0] * (n - 1)
for i in range(1, n+1):
    queue = [i]
    dist = [-1] + [-1] * n
    dist[i] = 0
    bfs(graph, queue, dist, num)

for v in num[1:]:
    print(v // 2)

Submission status: Accepted

Solution code:
N, X, Y = list(map(int, input().split()))
X,Y = X-1,Y-1
dist = [[1000]*(m-1) for m in range(N,0,-1)]

for i in range(N-1):
    for j in range(i+1, N):
        dist[i][j-i-1] = min(j-i, abs(X-i)+abs(Y-j)+1)
a = {i:0 for i in range(1, N)}
for dis in dist:
    for d in dis:
        a[d]+=1
for i in range(1, N):
    print(a[i])

Submission status: Accepted

Solution code:
from collections import deque

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

g = {}
for i in range(n - 1):
    g.setdefault(i, [])
    g.setdefault(i + 1, [])
    g[i].append(i + 1)
    g[i + 1].append(i)


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

global_stat = [0] * n

def bfs(i, g):
    q = deque([(i, 0)])
    vis = [0] * len(g)
    vis[i] = 1
    stat = [0] * len(g)
    while q:
        cur_v, cur_dist = q.popleft()
        # print("%s->%s: %s" % (i + 1, cur_v + 1, cur_dist))
        if cur_v > i:
            stat[cur_dist] += 1
        for adj_v in g[cur_v]:
            if not vis[adj_v]:
                vis[adj_v] = 1
                q.append((adj_v, cur_dist + 1))
    # print(stat)
    return stat

for i in range(n):
    local_stat = bfs(i, g)
    for i, v in enumerate(local_stat):
        global_stat[i] += v

# global_stat = [v // 2 for v in global_stat]
# print(global_stat)

for v in global_stat[1:]:
    print(v)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

n, x, y = map(int, sys.stdin.readline().split())
    
def main():
    res = [0] * (n + 1)
    for i, j in combinations(range(1, n+1), 2):
        d = min(j - i, abs(i - x) + 1 + abs(j - y))
        res[d] += 1
        
    for i in range(1, n):
        print(res[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

N, X, Y = map(int, input().split())
answers = [0 for _ in range(N - 1)]
# print(answers)

def min_distance(a, b):
    global X, Y
    simple = b - a
    a_to_x = abs(X - a)
    x_to_y = 1
    y_to_b = abs(Y - b)
    return min(simple, a_to_x + x_to_y + y_to_b)

G = [(i + 1) for i in range(N)]
# print(G)
for v in itertools.combinations(G, 2):
    # print(v[0], v[1])
    # print(v[0], v[1], min_distance(v[0], v[1]))
    answers[min_distance(v[0], v[1]) - 1] += 1

for answer in answers:
    print(answer)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect
import scipy.sparse
from scipy.sparse.csgraph import shortest_path

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, X, Y = map(int, input().split())
L = min(X, Y)
R = max(X, Y)

ans = [0] * (N - 1)

for i in range(1, N):
    for j in range(i + 1, N + 1):
        ans[min(j - i, abs(L - i) + abs(R - j) + 1) - 1] += 1
for i in ans:
    print(i)

Submission status: Accepted

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

X = X-1
Y = Y-1

for i in range(N-1):
    for j in range(N-i-1):
        k = i + j + 1
        if k <= X+1 or Y-1 <= i:
            ans[k-i-1] = ans[k-i-1] + 1
        else:
            xy = abs(i-X)+1+abs(k-Y)
            if xy < k-i:
                ans[xy-1] = ans[xy-1] + 1
            else:
                ans[k-i-1] = ans[k-i-1] + 1

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

Submission status: Accepted

Solution code:
import sys
import math
import collections
from collections import deque
#x = int(input())
n, x, y = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

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

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

Submission status: Accepted

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

cnt = {n: 0 for n in range(1, N)}
for i in range(1, N + 1):
    for j in range(i+1, N + 1):
        d1 = abs(i - j)
        d2 = 1 + min(abs(x - i) + abs(y - j), abs(x - j) + abs(y - i))
        cnt[min(d1, d2)] += 1

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