Problem:


Score : 400 points

Problem Statement

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

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

There is an edge between Vertex X and Vertex Y.

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

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

Constraints

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

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

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

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

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

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

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

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

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Accepted

Solution code:
from collections import deque

n, x, y = map(int, input().split())
x -= 1
y -= 1
ans = [0] * (n-1)
# グラフの作成
g = [[] * n for _ in range(n)]
for i in range(n-1):
    g[i].append(i + 1)
    g[i + 1].append(i)
g[x].append(y)
g[y].append(x)


# 幅優先探索
def bfs(u):
    dist = [-1] * n
    dist[u] = 0
    que = deque([])
    que.append(u)
    while que:
        v = que.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v] + 1
            que.append(nv)
    for i in dist:
        if i == 0:
            continue
        ans[i - 1] += 1
    return ans


# 頂点の探索
for i in range(n):
    bfs(i)
for i in ans:
    print(i // 2)

Submission status: Accepted

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

def main():
    n, x, y = map(int, input().split(" "))
    graph = np.zeros([n, n])
    for i in range(n-1):
        graph[i, i+1] = 1
        graph[x-1, y-1] = 1
    
    s_path = shortest_path(graph, method='D', directed=False)
    
    c = collections.Counter(s_path.flatten())
    for k in range(n-1):
        k += 1
        ans = int(c[k] / 2)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

Edge = [[] for _ in range(n+1)]
for i in range(1,n):
    Edge[i].append([1, i+1])
    Edge[i+1].append([1, i])

Edge[x].append([1,y])
Edge[y].append([1,x])

def dijkstra_heap(s):
    # 始点sから各頂点への最短距離
    d = [10**10] * (n+1)
    used = [False] * (n+1)
    d[s] = 0
    used[s] = True
    edgelist = []
    
    # edgeは各頂点の[重み、行先]からなる配列
    for e in Edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)

        # 未使用の頂点から最小の距離のものを探す
        if used[minedge[1]] == True:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True

        for e in Edge[v]:
            if used[e[1]] == False:
                heapq.heappush(edgelist, [e[0]+d[v], e[1]])
    return d

Ans = [0 for _ in range(n+1)]
for i in range(1,n):
    Dist = dijkstra_heap(i)
    # print(Dist)
    for dist in Dist[i:]:
        Ans[dist] += 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)

d = [[N]*N for i in range(N)]

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



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

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

Submission status: Accepted

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

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)

import heapq

# d_l = [None] * N
# q = [(0, 0)]
# while len(q) > 0:
#     dist, src = heapq.heappop(q)
#     for dst in graph[src]:
#         dist_tmp = dist + 1
#         if d_l[dst] > dist_tmp:
#             d_l[dst] = dist_tmp
#             q.append((dist_tmp, dst))

# d_r = [None] * N
# q = [(0, N - 1)]
# while len(q) > 0:
#     dist, src = heapq.heappop(q)
#     for dst in graph[src]:
#         dist_tmp = dist + 1
#         if d_r[dst] > dist_tmp:
#             d_r[dst] = dist_tmp
#             q.append((dist_tmp, dst))

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

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

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

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left #bisect_left(list, value)
import heapq
#from fractions import gcd
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

def dijkstra_heap(s,edge):
    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,w = map(int,input().split()) #n:頂点数　w:辺の数

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

for i in range(1, N-1):
    edge[i].append([1, i+1])
    edge[i].append([1, i-1])
edge[0].append([1, 1])
edge[N-1].append([1, N-2])
edge[X-1].append([1, Y-1])
edge[Y-1].append([1, X-1])

dd = defaultdict(int)
for i in range(N):
    dists = dijkstra_heap(i, edge)
    for j in dists[i+1:]:
        dd[j] += 1

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

Submission status: Accepted

Solution code:


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

DP = [[abs(i - j) for i in range(N)] for j in range(N)]

DP[X - 1][Y - 1] = 1
DP[Y - 1][X - 1] = 1

# que = deque()
# que.append((X - 1, Y - 1))
# while que:
#     tmp = que.popleft()
#     x, y = tmp[0], tmp[1]

x = X - 1
y = Y - 1
for i in range(N - 1):
    for j in range(i + 1, N):
        DP[i][j] = min(DP[i][j], DP[i][x] + DP[y][j] + 1, DP[i][y] + DP[x][j] + 1)

lst = [0] * N
for i in range(N - 1):
    # tmp = list(ans[i,:])
    # print (tmp)
    for j in range(i + 1, N):
        lst[DP[i][j]] += 1
    
print (*lst[1:], sep = '\n')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline

N, X, Y = map(int, input().split())
skip = Y - X  - 1
ans = []

for i in range(1, N):
    for j in range(i+1, N+1):
        dist = j - i
        if i < X and j >= X and j <= Y:
            left = j - X
            right = Y - j + 1
            if right < left:
                dist = j - i + right - left
        elif i >= X and i <= Y and j >= X and j <= Y:
            r1 = j - i
            r2 = i - X + Y - j + 1
            if r2 < r1:
                dist = r2
        elif i >= X and i < Y and j > Y:
            left2 = i - X + 1
            right2 = Y - i
            if left2 < right2:
                dist = j - i + left2 - right2
        elif i <= X and j >= Y:
            dist = j - i - skip
        ans.append(dist)
out = Counter(ans)

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

Submission status: Accepted

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

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

for i in range(n-1):
    for j in range(i+1, n):
        cnt[calc(i,j)-1] += 1

for c in cnt: print(c)

Submission status: Accepted

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

n_minus_route = [0] * N
n_plus_route = [0] * N
for i in range(1, N):
    for j in range(i+1, N+1):
        tmp = abs(X-i) + 1 + abs(Y-j)
        if j-i > tmp:
            n_minus_route[j-i] += 1
            n_plus_route[tmp] += 1

for k in range(1, N):
    ans = N - k - n_minus_route[k] + n_plus_route[k]
    print(ans)

Submission status: Accepted

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


N,X,Y = map(int,input().split())
X -= 1
Y -= 1
#%%
INF =10**9
dist = [[INF]*N for _ in range(N)]


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

ans = [0]*(N-1)
for dst in dist:
    for d in dst:
        if d!=INF:
            ans[d-1] += 1

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
n, x, y = map(int, input().split())

ans_lis = dd(lambda: 0)
for j in range(1, n+1):
  for i in range(1, n+1):
    reg_way = abs(j - i)
    warp_x_y = abs(x - i) + 1 + abs(y - j)
    warp_y_x = abs(y - i) + 1 + abs(x - j)
    ans = min(reg_way, warp_x_y, warp_y_x)
    #print(j, i, ans)
    ans_lis[ans] += 1
    
for i in range(1, n):
  print(ans_lis[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):
        d = min(j - i, abs(x - i) + 1 + abs(y - j))
        ans[d] += 1
print(*ans[1:], sep="\n")

Submission status: Accepted

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

for i in range(1,n+1):
  for j in range(i+1,n+1):
    if j <= x or y <= i:
      count[j-i] += 1
    else:
      c1 = j-i
      c2 = abs(i-x) + abs(j-y) + 1
      count[min(c1,c2)] += 1
      
for v in count.values():
	print(v)

Submission status: Accepted

Solution code:
n, x, y = map(int, input().split())
dist = {}
distance = 0
for m in range(1, n):
    dist[m] = 0
for i in range(1, n):
    for j in range(i+1, n+1):
        distance = min(j-i, abs(i-x)+abs(j-y)+1)
        dist[distance] += 1
for p in range(1, n):
    print(dist[p])

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

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

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)


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

    for i in range(1,n+1):
        for j in range(1,n+1):
            total[d2[i][j]]+=1

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




if __name__ == "__main__":

    main()

Submission status: Accepted

Solution code:
def z(x,y):
    if x > y:
        return(x-y)
    else:
        return(y-x)
N,X,Y = map(int,input().split())
X -= 1
Y -= 1
A = [0] * N
for i in range(N):
    for j in range(i+1,N):
        a = min(j-i,z(i,X) + 1 + z(j,Y))
        A[a] += 1
for i in range(N-1):
    print(A[i+1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n, x, y = [int(s) for s in input().strip().split()]

    result = [0] * n

    def bfs(src):
        seen = {src}
        q = [src]
        step = 0
        while q:
            q2 = []
            for u in q:
                if u > src:
                    result[step] += 1
                if u > 1 and u - 1 not in seen:
                    seen.add(u - 1)
                    q2.append(u - 1)
                if u < n and u + 1 not in seen:
                    seen.add(u + 1)
                    q2.append(u + 1)
                if u == x and y not in seen:
                    seen.add(y)
                    q2.append(y)
                if u == y and x not in seen:
                    seen.add(x)
                    q2.append(x)
            q = q2
            step += 1
    
    for i in range(1, n + 1):
        bfs(i)
    for i in range(1, n):
        print(result[i])


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    n, x, y = map(int, input().strip().split())
    dist = [[0] * (n+1) for _ in range(n+1)]

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

    for i in range(1, n+1):
        for j in range(i+1, n+1):
            dist[i][calc_dist(i, j)] += 1

    for k in range(1, n):
        ans = 0
        for node in range(1, n+1):
            ans += dist[node][k]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

ctr = defaultdict(int)

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

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

Submission status: Accepted

Solution code:
def calc(u,v,x,y):
    a = v - u
    b = abs(u-x) + abs(y-v) + 1
    c = abs(u-y) + abs(x-v) + 1
    # print(a,b,c, '-', u,v,x,y)
    return min(a,b,c)

n,x,y = map(int, input().split())
d = {}
for i in range(1,n):
    for j in range(i+1,n+1):
        dist = calc(i,j,x,y)
        if dist not in d:
            d[dist] = 0
        d[dist] += 1
        # print(i,j,dist)

for i in range(1,n):
    print(d.get(i,0))

Submission status: Accepted

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

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

for i in ans:
    print(i)

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(i):
    global ans
    q = deque()
    c = [0] * n
    d = [0] * n
    c[i] = 1
    d[i] = 0
    q.append(i)
    while q:
        p = q.popleft()
        if p != 0:
            if c[p - 1] == 0:
                q.append(p - 1)
                d[p - 1] += d[p] + 1
                c[p - 1] = 1
                ans[d[p - 1]] += 1
        if p != n - 1:
            if c[p + 1] == 0:
                q.append(p + 1)
                d[p + 1] += d[p] + 1
                c[p + 1] = 1
                ans[d[p + 1]] += 1
        if p == x:
            if c[y] == 0:
                q.append(y)
                d[y] = d[x] + 1
                c[y] = 1
                ans[d[y]] += 1
        if p == y:
            if c[x] == 0:
                q.append(x)
                d[x] = d[y] + 1
                c[x] = 1
                ans[d[x]] += 1
    #print(ans)
    #print(d)


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

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

Submission status: Accepted

Solution code:
# coding: utf-8

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

for i in range(N):
    if i<N-1:
        G[i].append(i+1)
    if i>0:
        G[i].append(i-1)

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

ans=[0 for i in range(N)]

INF=10**5

for i in range(N):
    queue=[]
    queue.append(i)
    d=[INF for j in range(N)]
    d[i]=0
    unused=[True for j in range(N)]
    unused[i]=False
    
    while queue:
        u=queue.pop(0)
        
        for j in range(len(G[u])):
            n=G[u][j]
            if unused[n] and d[n]>d[u]+1:
                unused[n]=False
                d[n]=d[u]+1
                queue.append(n)
    
    for j in range(N):
        ans[d[j]]+=1


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n,x,y = map(int,input().split())
# 問題 nC2 の中から、最短距離がk になる頂点の組み合わせをそれぞれ求める
# n <= 2*10**3なのでnC2は回る。O(1)に行ける
if x > y: x,y = y,x
#x < y
ans = [0]*n#出力は 0　消す
for i in range(1,n):
    for j in range(i+1,n+1):# i < jとする
        # パターン 1 [x,y]の両方外
        if y <= i or j <= x:
            k = j-i
            ans[k] += 1
        # パターン2 片方が[i,j]の内側
        elif (x<=i and i <= y and y <= j):
            k = min(j-i,i-x+j-y+1)
            ans[k] += 1
        # 片方が内側 i,x,j,y
        elif (i<=x and x <= j and j<=y):
            k = min(j-i,y-j+1+x-i)
            ans[k] += 1
        elif i <=x and y <= j:
            k = x-i+1+j-y
            ans[k] += 1
        else:#両方[x,y]の内側 x,i,j,y
            k = min(j-i,1+i-x+y-j)
            ans[k] += 1
        #print(i,j,k)
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

Solution code:
import bisect
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29


def main():
    N,X,Y = isRaw()
    Es = [[1]]+[[n-1,n+1] for n in range(1,N-1)]+[[N-2]]
    Es[X-1].append(Y-1)
    Es[Y-1].append(X-1)
    def shortest(n):
        qu = deque()
        visited = [0]*N
        qu.append(n)
        visited[n]=1
        path =[INF]*N
        path[n]=0
        while len(qu)!=0:
            m = qu.popleft()
            for l in Es[m]:
                if visited[l]!=0:
                    continue
                path[l] = min(path[m]+1,path[l])
                visited[l]=1
                qu.append(l)
        return path
    shortests = [shortest(n) for n in range(N)]
    npathes = [0 for i in range(N-1)]
    for n in range(N):
        for m in range(n+1,N):
            npathes[shortests[n][m]-1]+=1
    return "\n".join([str(a) for a in npathes])

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def main():
    N,X,Y=mis()
    ans = [0] * N
    for d in range(1, N):
        for l in range(1, N):
            r = l + d
            if r > N:
                break
            dist = min(abs(l-r), abs(l-X)+1+abs(Y-r))
            ans[dist] += 1
    for d in range(1, N):
        print(ans[d])



main()

Submission status: Accepted

Solution code:
from collections import defaultdict

import heapq
import sys

input = sys.stdin.readline

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    d = [[float("inf")]*N for i in range(N)]
    for i in range(N-1):
        d[i][i+1] = 1
        d[i+1][i] = 1

    d[X][Y] = 1
    d[Y][X] = 1
    e = defaultdict(int)
    for i in range(N):
        for j in range(i,N):
            if i == j:
                continue
            tmp = min(j - i, abs(X-i) + 1 + abs(Y-j))
            e[tmp] += 1
    for i in range(1,N):
        print(e[i])






if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = [0] * (N - 1)

for i in range(N - 1):
    vst = [False] * N
    q = [(i, 0)]
    vst[i] = True
    for u, c in q:
        if i < u: ans[c - 1] += 1
        next = [u + 1, u - 1]
        if u == X - 1:
            next.append(Y - 1)
        if u == Y - 1:
            next.append(X - 1)

        for v in next:
            if 0 <= v < N and not vst[v]:
                q.append((v, c + 1))
                vst[v] = True

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

Submission status: Accepted

Solution code:
def read():
    N, X, Y = list(map(int, input().split()))
    return N, X, Y

def solve(N, X, Y):
    INF = N + N
    X -= 1
    Y -= 1
    e = [[INF for j in range(N)] for i in range(N)]
    for i in range(N-1):
        e[i][i+1] = 1
        e[i+1][i] = 1
    e[X][Y] = 1
    e[Y][X] = 1

    c = [0 for i in range(N)]

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

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

if __name__ == '__main__':
    inputs = read()
    solve(*inputs)

Submission status: Accepted

Solution code:
def LI():
	return [ int(s) for s in input().split() ]

N,X,Y = LI()
dist = [0]*(N-1)

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

Submission status: Accepted

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

li = [0 for k in range(N)]
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if i <= X:
            if j <= X:
                li[j-i] += 1
            elif j < Y:
                d_to_x = min(j - X, Y - j + 1)
                li[X - i + d_to_x] += 1
            else:
                li[(X - i) + (j - Y) + 1] += 1
        elif i < Y:
            if j < Y:
                li[min(j - i, (i - X) + (Y - j) + 1)] += 1
            else:
                d_to_y = min(Y - i, i - X + 1)
                li[j - Y + d_to_y] += 1
        else:
            li[j - i] += 1
for i in range(1,N):
    print(li[i])

Submission status: Accepted

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

d = dict(zip(range(1, N), [0]*(N-1)))
for i in range(1, N):
  for j in range(i+1, N+1):
    l1 = j - i
    l2 = abs(X - i) + 1 + abs(Y - j)
    l = min(l1, l2)
    d[l] += 1

for k in d:
  print(d[k])

Submission status: Accepted

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

def distance(i, j):
    d1 = abs(j-i)
    d2 = abs(i-X)+abs(j-Y)+1
    d3 = abs(i-Y)+abs(j-X)+1
    return min(d1, d2, d3)

ret = [0]*(N-1)
for i in range(1,N):
    for j in range(i+1,N+1):
        ret[distance(i,j)-1] += 1

for val in ret:
    print(val)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    
    N,X,Y = LMIIS()
    X -= 1
    Y -= 1
    dp =[[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            if i <= X < Y <= j:
                dp[i][j] = j - i  - (Y - X) + 1
            elif  i <= X and j <= Y:
                dp[i][j] = min(j-i, Y-j+1+X-i)
            elif X <= i and j <= Y:
                dp[i][j] = min(j-i,Y-j+1+i-X)
            elif X <= i and Y <= j:
                dp[i][j] = min(j-i,j-Y+1+i-X)

            else:
                dp[i][j] = j - i
    num_length = [0] * N
    for i in range(N):
        for j in range(i+1,N):
            num_length[dp[i][j]] += 1
    
    for i in range(1,N):
        print(num_length[i])
    # print(dp)


if __name__ == '__main__':
    main()