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:
# Problem D - Line++

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

# initialization
graph = [[0]*(N+1) for i in range(N+1)]
kyori_list = [0]*N

# dp count
for i in range(1, N+1):
    for j in range(i, N+1):
        if i==j:
            continue
        graph[i][j] = min(j-i, abs(X-i)+1+abs(Y-j))
for i in range(1, N+1):
    for j in range(1, N+1):
        if i==j:
            continue
        kyori_list[graph[i][j]] += 1

# output
for i in range(1, N):
    print(kyori_list[i])

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(1, n + 1):
    if i == 1:
        a.append([2])
    elif i == n:
        a.append([n - 1])
    else:
        a.append([i - 1, i + 1])
a[x - 1].append(y)
a[y - 1].append(x)

d = {}
for i in range(n - 1):
    d[i + 1] = 0

def solve(s):
    queue = deque()
    queue.append(a[s - 1])
    visit = set()
    visit.add(s)
    depth = 0

    while queue:
        depth += 1
        nn = queue.popleft()
        adj = []
        for i in nn:
            if i not in visit:
                d[depth] += 1
                adj = adj + a[i-1]
            visit.add(i)
        if adj != []:
            queue.append(adj)

for i in range(n):
    solve(i + 1)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,x,y=map(int,input().split())
l=[]
for i in range(n-1):
  for j in range(i+1,n):
    d1=j-i
    d2=abs((x-1)-i)+abs(j-(y-1))+1
    d=min(d1,d2)
    l.append(d)
import collections
c=collections.Counter(l)
for kk in range(1,n):
  print(c[kk])

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

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

Submission status: Accepted

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


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


ans = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1, n):
        d = shortest_path(i, j)
        ans[d-1] += 1

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

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n,x,y = MAP()

dd = defaultdict(int)

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

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N, X, Y = [int(item) for item in input().split()]
    X -= 1
    Y -= 1

    edges = [[] for _ in range(N)]
    for i in range(N-1):
        edges[i].append(i+1)
        edges[i+1].append(i)
    edges[X].append(Y)
    edges[Y].append(X)


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

    res_memo = [0 for _ in range(N)]
    for i in range(N):
        fp = [-1 for _ in range(N)]
        que = collections.deque([[i, 0]])
        fp[i] = 0
        while que:
            node, dist = que.popleft()
            for to_node in edges[node]:
                if fp[to_node] == -1:
                    que.append([to_node, dist+1])
                    fp[to_node] = dist+1

        for item in fp:
            res_memo[item] +=1
    
    for item in res_memo[1:]:
        print(item//2)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N,X,Y = map(int,input().split())
g = [[] for _ in range(N+1)]
for i in range(1,N+1):
    if i != 1:
        g[i].append(i-1)
    if i != N:
        g[i].append(i+1)
g[X].append(Y)
g[Y].append(X)
from collections import deque
answer = [0]*(N+1)
for i in range(1,N+1):
    q = deque([i])
    d = [None]*(N+1)
    d[i] = 0
    while q:
        p = q.popleft()
        for j in g[p]:
            if d[j] == None:
                d[j] = d[p]+1
                q.append(j)
    for k in d[1:]:
        answer[k] += 1
for l in answer[1:-1]:
    print(l//2)

Submission status: Accepted

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

l = [0]*(n-1)

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

for i in l:
    print(i)

Submission status: Accepted

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

ans = [0]*(N-1)
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] += 1

for a in ans:
    print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,x,y = map(int,input().split())
ko = [0 for i in range(10**4)]
for i in range(1,n):
  for j in range(i+1,n+1):
    c1 = j-i
    if i<=x and y<=j:
      c2 = (x-i)+1+(j-y)
    elif i<=x and j<y:
      c2 = (x-i)+1+(y-j)
    elif x<i and y<=j:
      c2 = (i-x)+1+(j-y)
    else:
      c2 = (i-x)+1+(y-j)
    ko[min(c1,c2)] += 1
  #  print(i,j,j-i,c1,c2,ko[:10])
for i in range(1,n):
  print(ko[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):
        c = min(abs(j-i), abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(j-x))
        d[c] += 1
for i in range(1,n):
    print(d[i])

Submission status: Accepted

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


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)]


sys.setrecursionlimit(1000000)


def main():
    N, X, Y = LI()
    X -= 1
    Y -= 1
    cnt = [0] * N

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

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


main()

Submission status: Accepted

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


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)]


sys.setrecursionlimit(1000000)


def main():
    N, X, Y = LI()
    X -= 1
    Y -= 1
    dist = [[N] * N for _ in range(N)]

    q = deque()
    for i in range(N):
        q.append(i)
        dist[i][i] = 0
        while q:
            u = q.popleft()
            t = dist[i][u] + 1
            if u < N - 1:
                if dist[i][u + 1] > t:
                    q.append(u + 1)
                    dist[i][u + 1] = t
            if u >= 1:
                if dist[i][u - 1] > t:
                    q.append(u - 1)
                    dist[i][u - 1] = t
            if u == X:
                if dist[i][Y] > t:
                    q.append(Y)
                    dist[i][Y] = t
            if u == Y:
                if dist[i][X] > t:
                    q.append(X)
                    dist[i][X] = t

    cnt = [0] * N

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

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


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

for i in ans:
    print(i)

Submission status: Accepted

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

from collections import deque

INF = 1000000000
ans = [0]*(N-1)


def rep(sv,dist):
    que = deque()

    def push(v,d):
        if (dist[v] != INF): return
        dist[v] = d
        que.append(v)

    push(sv,0)

    while(que):
        v = que.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-1:
            push(Y-1, d+1)
        #逆に気を付ける
        if v == Y-1:
            push(X-1, d+1)

for i in range(N):
    dist = [INF]*N
    rep(i,dist)
    # print(dist)
    for d in dist:
        if d-1 == -1:continue
        ans[d-1] += 1


for an in ans:
    print(an//2)
# print(ans)

Submission status: Accepted

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

for i in range(1, N):
    for j in range(i+1, N+1):
        cnt.append(min(j-i, abs(X-i)+abs(Y-j)+1))

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

reselt = [0]*(n-1)

for i in range(n):
    stack=deque([i])
    check = [-1]*n
    check[i] = 0
 
    while len(stack)>0:
        v = stack.popleft()
        for i in root[v]:
            if check[i] == -1:
                check[i] = check[v]+1
                reselt[check[i]-1] += 1
                stack.append(i)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N,X,Y=map(int,input().split())
    X-=1
    Y-=1
    adj=[[] for i in range(N)]
    adj[X].append(Y)
    adj[Y].append(X)
    for i in range(N-1):
        adj[i].append(i+1)
        adj[i+1].append(i)
    cnt=[0]*(N)
    for i in range(N):
        dist=[-1]*N
        qu=deque([i])
        dist[i]=0
        while(len(qu)>0):
            v=qu.popleft()
            for nv in adj[v]:
                if dist[nv]==-1:
                    dist[nv]=dist[v]+1
                    cnt[dist[nv]]+=1
                    qu.append(nv)
    for i in range(1,N):
        print(cnt[i]//2)
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,X,Y = map(int,readline().split())
ans = [0]*N
graph = [[] for _ in range(N)]
for i in range(N-1):
    graph[i].append(i+1)
    graph[i+1].append(i)
graph[X-1].append(Y-1)
graph[Y-1].append(X-1)

def bfs(x,q,dist):
    while q:
        v = q.popleft()
        for nx in graph[v]:
          if dist[nx] != 0:
            continue
          dist[nx] = dist[v] + 1
          q.append(nx)
          if nx > x:
            ans[dist[nx]] +=1

for i in range(N):
    dist = [0]*N
    q = deque([i])
    bfs(i,q,dist)
      
print('\n'.join(str(n) for n in ans[1:]))

Submission status: Accepted

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,X,Y = map(int,readline().split())
ans = [0]*N
for i in range(1,N):
    for j in range(i+1,N+1):
        dist = min(j-i,abs(i-X)+1+abs(j-Y),abs(i-Y)+1+abs(j-X))
        ans[dist]+=1
print('\n'.join(str(n) for n in ans[1:]))

Submission status: Accepted

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
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 S(): return input()
def LS(): return input().split()


INF = float('inf')


def main():
    n, x, y = LI()
    x, y = x - 1, y - 1
    d = [[INF] * n for _ in range(n)]
    ans = [0] * n
    for i in range(n - 1):
        for j in range(i + 1, n):
            d[i][j] = min([j - i,
                           abs(x - i) + 1 + abs(j - y),
                           abs(y - i) + 1 + abs(j - x)])
            ans[int(d[i][j])] += 1
    print(*ans[1:], sep='\n')


main()

Submission status: Accepted

Solution code:
import itertools
import functools
import math
from collections import Counter

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

k=[]

for i in range(1,N):
    for j in range(i+1,N+1):
        chk = min(abs(j-i),abs(X-i)+abs(j-Y)+1)
        k.append(chk)

a=Counter(k)

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

Submission status: Accepted

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

mi={i:0 for i in range(1,n)}
for i in range(1,n):
  for j in range(i+1,n+1):
    if i<=x and y<=j:
      mi[x-i+1+j-y]+=1
    elif x<i and y<=j:
      mi[min(i-x+1+j-y,j-i)]+=1
    elif i<=x and j<y:
      mi[min(x-i+1+y-j,j-i)]+=1
    elif x<i and j<y:
      mi[min(i-x+1+y-j,j-i)]+=1
    else:
      mi[j-i]+=1
      
for i in range(1,n):
  print(mi[i])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#幅優先探索(BFS)
import sys
input = sys.stdin.readline

n,x,y = [int(x) for x in input().split()] # nは頂点の数、mは辺の数
g = [[] for _ in range(n)] # 隣接リスト

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

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

# 0からの各頂点の距離
di = [0]*n
for i in range(n):
    l = bfs(i)
    for j in l:
        if j == 0:
            continue
        di[j-1] += 1
di = di[:-1]
for k in di:
    print(k//2)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos
 
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)


show_flg=False
show_flg=True


ans=0

n,x,y=LI_()
n+=1
m=defaultdict(int)
for i in rep(n):
    for j in rep(i+1,n):
        d=min(j-i,abs(i-x)+abs(j-y)+1,abs(i-y)+abs(j-x)+1)
        m[d]+=1

for i in rep(1,n):
    print(m[i])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import OrderedDict
n, x, y = map(int, input().split())
x = x-1
y = y-1
dist_hist = OrderedDict({i: 0 for i in range(1, n)})
for i in range(n-1):
  for j in range(i+1, n):
    if i<=x and j>=y:
      dist = j-i + 1 - (y-x)
    elif i<=x and x<j<y:
      dist = min(j-i, x-i + 1 + y-j)
    elif x<i<y and y<=j:
      dist = min(i-x + 1 + j-y, j-i)
    elif x<i<y and x<j<y:
      dist = min(j-i, i-x + 1 + y-j)
    else:
      dist = j - i
    dist_hist[dist] += 1
[print(value) for value in dist_hist.values()]

Submission status: Accepted

Solution code:

import numpy as np
from scipy.sparse.csgraph import  dijkstra
from scipy.sparse import csr_matrix

def resolve():
    N, X, Y = map(int, input().split())
    G = np.zeros((N+1, N+1), dtype=np.int64)
    for i in range(1, N):
        G[i, i+1] += 1
        G[i+1, i] += 1
    G[X, Y] += 1
    G[Y, X] += 1

    csr = csr_matrix(G)
    dist = dijkstra(csr)

    dic = {}
    for di in dist:
        for d in di:
            if d in dic:
                dic[d] += 1
            else:
                dic[d] = 1
    for i in range(1, N):
        if i in dic:
            print(dic[i]//2)
        else:
            print(0)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    klist = defaultdict(int)
    for i in range(n):
        for j in range(i+1, n):
            if (i <= x and j <= x) or (y <= i and y <= j):
                k = j - i
                klist[k] += 1
            elif i <= x and x < j <= y:
                k = min(j - i, (x - i + y - j) + 1)
                klist[k] += 1
            elif i <= x and y <= j:
                k = (j - i) - (y - x) + 1
                klist[k] += 1
            else:
                k = min((j - i), ((i - x) + abs(y - j) + 1))
                klist[k] += 1
    for i1 in range(1, n):
        print(klist[i1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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