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: Time Limit Exceeded

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

from collections import defaultdict
g = [[0] * n for _ in range(n)]
for i in range(1, n):
    g[i-1][i] = 1
    g[i][i-1] = 1
g[x-1][y-1] = 1
g[y-1][x-1] = 1

from scipy.sparse.csgraph import floyd_warshall
cost = floyd_warshall(g)

from collections import Counter
c = Counter()
for i in range(n):
    for j in range(i+1, n):
        c[cost[i][j]] += 1

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

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

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

    dist_freq = defaultdict(int)
    for start in range(N):
        d = deque([start])
        distance = [-1] * N
        distance[start] = 0
        while d:
            current_node = d.popleft()
            for next_node in graph[current_node]:
                if distance[next_node] == -1:
                    distance[next_node] = distance[current_node] + 1
                    d.append(next_node)
        for v in distance:
            if v != 0:
                dist_freq[v] += 1
    for k in range(1, N):
        print(dist_freq[k] // 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def min_dist(i, j):
    d1 = abs(i - j)

    d2 = abs(X - i) + abs(Y - j) + 1

    return min(d1, d2)


ans = [0] * N

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

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

Submission status: Accepted

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

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

def main():
    mod=10**9+7
    N,X,Y=MI()
    X-=1
    Y-=1
    
    ans=[0]*N
    
    for i in range(N):
        for j in range(i+1,N):
            if j<=X:
                d=j-i
            elif i>=Y:
                d=j-i
            elif i<=X and j>=Y:
                d=X-i + j-Y +1
            elif i<=X and j<=Y:
                d=min(j-i,X-i +1 +Y-j)
            elif i>=X and j>=Y:
                d=min(j-i, i-X +1 +j-Y)
            else:#どっちも内側
                d=min(j-i, i-X +1 +Y-j)
                
            ans[d-1]+=1
            
    for i in range(N-1):
        print(ans[i])
                

                
   

main()

Submission status: Accepted

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

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

def main():
    mod=10**9+7
    N,X,Y=MI()
    X-=1
    Y-=1
    
    ans=[0]*N
    
    for i in range(N):
        for j in range(i+1,N):
            d=min(j-i,abs(X-i)+1+abs(Y-j))

                
            ans[d-1]+=1
            
    for i in range(N-1):
        print(ans[i])
                

                
   

main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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


def bfs(g, n_node, start_node):
    dist = [-1] * n_node
    dist[start_node] = 0
    que = deque([start_node])

    while que:
        node = que.popleft()
        for j in g[node]:
            if dist[j] != -1:
                continue
            dist[j] = dist[node] + 1
            que.append(j)
    return dist


ans = [0] * n

for i in range(n):
    dist = bfs(g, n, i)
    for d in dist:
        ans[d] += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())
import sys
sys.setrecursionlimit(10**6)

n,x,y=sep()



d = [0] * n

for i in range(0, n - 1):
    for j in range(i, n):
        d1 = j - i
        d2 = abs((x - 1) - i) + 1 + abs((y - 1) - j)
        # print(i,j,d1,d2)
        d_min = min(d1, d2)
        d[d_min] += 1
for k in range(1, n):
    print(d[k])

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import deque
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    # 各ノードで幅優先探索を行う
    # 計算量(O(n^2))
    n, x, y = input_int_list()
    g = defaultdict(list)
    g[x].append(y)
    g[y].append(x)
    for i in range(1, n):
        g[i].append(i + 1)
        g[i + 1].append(i)
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        # 幅優先探索
        seen = set()
        dq = deque()
        dq.append((i, 0))  # node,depth
        while dq:
            p, d = dq.popleft()
            if p > i:  # 整数の組(i,j) (1 <= i <= j <= N)
                ans[d] += 1
            for q in g[p]:
                if q not in seen:
                    dq.append((q, d + 1))
                    seen.add(q)

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

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = [0]*n
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if i <= x and j >= y:
            a = abs(j-i)-abs(y-x)+1
            b = abs(i-x)+abs(j-y)+1
            ans[min(a,b)] += 1
        else:
            c = abs(x-i)+abs(y-j)+1
            d = abs(j-i)
            ans[min(c,d)] += 1

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

Submission status: Accepted

Solution code:
from itertools import *
from numpy import *
from scipy.sparse.csgraph import *
N,X,Y = map(int,input().split())
A = (N-1)*[0]
G = zeros((N,N))
G[X-1][Y-1] = 1
G[Y-1][X-1] = 1

for n in range(N-1):
  G[n][n+1] = 1
  G[n+1][n] = 1

S = shortest_path(G)

for i,j in combinations(range(N),2):
  A[int(S[i][j])-1]+=1

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

Submission status: Accepted

Solution code:
n, x, y = map(int, input().split())
graph = [[] for _ in range(n)]
 
for i in range(n):
  if i+1 < n:
    graph[i].append(i+1)
  if i-1 >=0:
    graph[i].append(i-1)
graph[x-1].append(y-1)
graph[y-1].append(x-1)
 
ans = [0] * (n-1)
from collections import deque
for i in range(n):
  dist = [-1] * n
  dist[i] = 0
  d = deque()
  d.append(i)
  while d:
    v = d.popleft()
    for j in graph[v]:
      if dist[j] != -1:
        continue
      dist[j] = dist[v] + 1
      ans[dist[j] - 1] += 1
      d.append(j)
for a in ans:
  print(a//2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n, x, y = i_map()
    ans = [0] * n

    for fr in range(1, n+1):
        for to in range(fr+1, n+1):
            cost = min(to - fr, abs(x-fr) + abs(to - y) + 1)
            ans[cost] += 1
    print(*ans[1:], sep="\n")

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for _ in range(n)]
import math
from queue import deque
n,x,y = L()
g = [[] for _ in range(n)]
for i in range(n):
    if (i == x-1):
        if (i == 0):
            g[i] = [1,y-1]
        elif (i == n-1):
            g[i] = [i-1,y-1]
        else:
            g[i] = [i-1,i+1,y-1]
    elif (i == y-1):
        if (i == 0):
            g[i] = [1,x-1]
        elif (i == n-1):
            g[i] = [i-1,x-1]
        else:
            g[i] = [i-1,i+1,x-1]
    else:
        if (i == 0):
            g[i] = [1]
        elif (i == n-1):
            g[i] = [i-1]
        else:
            g[i] = [i-1,i+1]
#print(g)
dis = [[0]*n for i in range(n)]
#print(dis)
ans = [0]*(n-1)
for i in range(n):
    q = deque()
    cnt = 1
    q.append(g[i])
    while q:
        d = []
        while q: 
            d += q.popleft()
        for j in d:
            if i != j and (dis[i][j] == 0 or dis[i][j] > cnt):
                dis[i][j] = cnt
                q.append(g[j])
                ans[cnt-1] += 1
        cnt += 1
for a in ans:
    print(int(a/2))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

# make graph
for i in range(n - 1):
    g[i].append(i + 1)
    g[i + 1].append(i)

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

def bfs(g, n_node, start_node):
    dist = [-1] * n_node
    dist[start_node] = 0
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        for n in g[node]:
            if dist[n] != -1:
                continue
            dist[n] = dist[node] + 1
            queue.append(n)
    return dist


ans_array = [0] * n
for i in range(n):
    dist = bfs(g, n, i)
    for d in dist:
        ans_array[d] += 1

for i in ans_array[1:]:
    print(i // 2)

Submission status: Accepted

Solution code:
def main():
	N, X, Y = [int(n) for n in input().split(" ")]
	vertex = [[1]] + [[i - 1, i + 1] for i in range(1, N - 1)] + [[N - 2]]
	vertex[X - 1].append(Y - 1)
	vertex[Y - 1].append(X - 1)

	count = [0] * N
	for i in range(N):
		to_visit = [i]
		checked = [0] * N
		steps = [0] * N
		checked[i] = 1

		while len(to_visit) > 0:
			visiting = to_visit.pop(0)
			vs = vertex[visiting]
			step = steps[visiting]
			for v in vs:
				if checked[v] == 0:
					checked[v] = 1
					to_visit.append(v)
					steps[v] = step + 1
					count[step + 1] += 1

	for c in count[1:]:
		print(int(c/2))

main()

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter

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

graph = [[] for _ in range(n+1)]

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

l = []
for j in range(1,n+1):
  dist = [-1] * (n+1)
  dist[0] = 0
  dist[j] = 0

  d = deque()
  d.append(j)

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

  l.extend(dist[1:])

c = Counter(l)
for i in range(1,n):
  print(int(c[i]/2))

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

Submission status: Accepted

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

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

        d[a] += 1
for ans in d[1:]:
    print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,X,Y=map(int,input().split())
d=[0]*N
for i in range(N):
    for j in range(N):
        if not i<j:
            continue
        dist=min([j-i,abs((X-1)-i)+1+abs(j-(Y-1))])
        d[dist]+=1
print(*d[1:],sep='\n')

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N,X,Y=mint()
C=[0]*(N)
for i in range(1,N):
    for j in range(i+1,N+1):
        tmp = min(j-i, abs(i-X)+1+abs(j-Y))
        C[tmp] += 1
lprint(C[1:])

Submission status: Accepted

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

dist = [0]*n

for i in range(0,n-1):
    for j in range(i,n):
        
        #xy使わない距離
        dist1 = j-i
        
        #xy使う距離
        dist2 = abs((x-1) - i) + 1 + abs((y-1) - j)
        
        
        # print(i,j,dist1,dist2)
        
        #最短距離
        dist_min = min(dist1,dist2)
        
        dist[dist_min] += 1
        
for k in range(1,n):
    print(dist[k])

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, X, Y = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

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

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

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

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,x,y=map(int, readline().rstrip().split())
    ans = [0] * (n-1)
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            d1 = abs(i-x) + abs(j-y) + 1
            d2 = abs(i-y) + abs(j-x) + 1
            d3 = abs(i-j)
            d=min(d1,d2,d3)
            ans[d-1]+=1
    for a in ans:
        print(a)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,x,y=map(int, readline().rstrip().split())
    ans = [0] * (n-1)
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            d1 = abs(i-x) + abs(j-x)
            d2 = abs(i-y) + abs(j-y)
            d3 = abs(i-x) + abs(j-y) + 1
            d4 = abs(i-y) + abs(j-x) + 1
            d5 = abs(i-j)
            d=min(d1,d2,d3,d4,d5)
            ans[d-1]+=1
    for a in ans:
        print(a)
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline

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

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

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

dists = [0] * (n-1)

for start in range(n):
    for end in range(start+1, n):
        dist = min(end-start, abs(((x-1)-start))+1+abs(end-(y-1)))
        dists[dist-1] += 1

for dist in dists:
    print(dist)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n, x, y = LI()
    ans = [0 for _ in range(n)]
    m = y-x-1

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Sep  7 15:49:02 2020

@author: liang
"""

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):
        #print(i,j)
        res = min(abs(i-j), abs(X-i) + 1 + abs(Y-j))
        #print(i, j, res)
        ans[res-1] += 1

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque, Counter
n, x, y = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
    G[i].append(i+1)
    G[i+1].append(i)
G[x-1].append(y-1)
G[y-1].append(x-1)
c = Counter()
for i in range(n):
    q = deque([i])
    dist = [-1]*n
    dist[i] = 0
    while q:
        cur = q.popleft()
        for nx in G[cur]:
            if dist[nx] != -1:
                continue
            dist[nx] = dist[cur]+1
            q.append(nx)
    for j, d in enumerate(dist):
        if i == j:
            continue
        c[d] += 1
for i in range(1, n):
    print(c[i]//2)

Submission status: Accepted

Solution code:
from collections import deque


N, X, Y = map(int, input().split())
to = [[] for _ in range(N)]

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

X, Y = X - 1, Y - 1
to[X].append(Y)
to[Y].append(X)


def main():
    ans = [0] * N
    for i in range(N):
        dist = [-1] * N
        dist[i] = 0
        que = deque([i])

        while que:
            v = que.popleft()
            for nv in to[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    if nv > i:
                        ans[dist[nv]] += 1
                    que.append(nv)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    dis = defaultdict(int)
    for i1 in range(n):
        for i2 in range(i1+1, n):
            d = min(abs(i2-i1), abs(x-i1)+abs(y-i2)+1, abs(x-i2)+abs(y-i1)+1)
            dis[d] += 1

    for k1 in range(1, n):
        print(dis[k1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    dis = defaultdict(int)
    for i1 in range(n):
        for i2 in range(n):
            d = min(abs(i2-i1), abs(x-i1)+abs(y-i2)+1, abs(x-i2)+abs(y-i1)+1)
            dis[d] += 1

    for k1 in range(1, n):
        print(dis[k1]//2)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, x, y= map(int, input().split())
    edges = {e:[] for e in range(n)}
    for i1 in range(1, n - 1):
        edges[i1].append(i1-1)
        edges[i1].append(i1+1)
    edges[0].append(1)
    edges[n-1].append(n-2)
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)

    dis = defaultdict(int)
    for j1 in range(n):
        seen = set()
        cnt = 0
        dis_each = [n] * n
        nexts = [j1]
        nextnext = []
        while len(seen) < n:
            for next in nexts:
                if next not in seen:
                    seen.add(next)
                    dis_each[next] = cnt
                    nextnext += edges[next]
            nexts = nextnext
            nextnext = []
            cnt += 1
        for d in dis_each:
            dis[d] += 1
    for k1 in range(1, n):
        print(dis[k1]//2)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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


from collections import deque
def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

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

for i in range(n):
    D = bfs(i)
    for d in D:
        ans_dist[d] += 1

for i in range(n-1):
    print(ans_dist[i+1]//2)

Submission status: Accepted

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

ans = [0] *(n-1)

for j in range(n):
  mark = ['inf']*(n)
  que = deque([j])
  mark[j] = 0
 
  while que:
    q = que.popleft()
    for k in next[q]:
      if mark[k] == 'inf':
        mark[k] = mark[q] + 1
        que.append(k)
  
  for l in range(0,n):
    if mark[l] != 0:
      ans[mark[l]-1] += 1

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

for i in li:
    print(i)

Submission status: Accepted

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

Submission status: Accepted

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

dp=[[0]*N for i in range(N)]
dist=[0]*N
X-=1
Y-=1
for i in range(N):
  for j in range(N):
    if not i<j:continue
    dp[i][j]=min(j-i,abs(j-Y)+1+abs(X-i))
    dist[dp[i][j]]+=1

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

Submission status: Accepted

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


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

for a in ans:
    print(a)

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):
    dis1 = j-i
    dis2 = abs(X-i) + 1 + abs(Y - j)
    dis3 = abs(Y-i) + 1 + abs(X - j)
    d = min(dis1,dis2,dis3)
    ans[d] += 1

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

Submission status: Accepted

Solution code:
import sys

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,abs((X-1)-i)+1+abs((Y-1)-j))-1] += 1
        #print(i,j,min(j-i,abs((X-1)-i)+1+abs((Y-1)-j))-1)

for i in range(len(d)):
    print(d[i])

Submission status: Accepted

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

ans = [0] * (N + 1)

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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