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:
from collections import deque
INF = 10**9

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

for sv in range(n):
  dist = [INF] * n
  q = deque()

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

  push(sv, 0)

  while q:
    v = q.popleft()
    d = dist[v]
    if v-1 >= 0: push(v-1, d+1)
    if v+1 < n: push(v+1, d+1)
    if v == x: push(y, d+1)
    if v == y: push(x, d+1)

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# N=頂点数、X,Y=座標
N, X, Y = map(int, input().split())
X -= 1
Y -= 1

# 未セットの値
INF = 10**4

# キューデータ(次の値、最短距離)
queue_list = []

# 最短距離ごとのリスト
min_e_list = [0 for i in range(N)]

for i in range(N):
    # キューデータ初期値をセット
    queue_list.append([i, 0])
    # 最短距離リスト(最短距離)
    min_dist_list = [INF for i in range(N)] 

    # キューデータが空になるまで繰り返す
    while(len(queue_list) != 0):
        
        # 先頭データを取り出す。
        pop_data = queue_list.pop(0)

        # 取り出した座標がセット済みの場合は何もしない
        if(min_dist_list[pop_data[0]] != INF):
            continue

        # 最短距離リストにデータセット
        min_dist_list[pop_data[0]] = pop_data[1]

        # 2重に数えないよう(i < 取り出した座標時)、最短距離ごとのリストにデータセット
        if(i < pop_data[0]):
            min_e_list[pop_data[1]] += 1

        # 1.隣の頂点(次の座標、+1,-1した値)
        if(pop_data[0]+1 < N):
            queue_list.append([pop_data[0]+1, pop_data[1]+1])
        if(pop_data[0] > 0 and pop_data[0]-1 < N):
            queue_list.append([pop_data[0]-1, pop_data[1]+1])
        
        # 2.X,Yで示した値
        if(pop_data[0] == X):
            queue_list.append([Y, pop_data[1]+1])
        if(pop_data[0] == Y):
            queue_list.append([X, pop_data[1]+1])

# 出力
for i,v in enumerate(min_e_list):
    if(i != 0):
        print(v)

Submission status: Time Limit Exceeded

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

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

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

ans=[0 for _ in range(N)]
for k in range(N):
    for l in range(k+1,N):
        if d[k][l]<N:
            ans[d[k][l]]+=1
    
for o in range(N-1):
    print(ans[o+1])

Submission status: Time Limit Exceeded

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

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

# N = 2000
# X = 100
# Y = 1900


X -= 1
Y -= 1

# @profile


def main(N, X, Y):
    ans = [0]*N
    graph = np.zeros((N, N))
    # np.fill_diagonal(graph[1:, :], 1)
    np.fill_diagonal(graph[:, 1:], 1)
    graph[X, Y] = 1
    # graph[Y, X] = 1
    dist_matrix = dijkstra(graph, directed=False)
    # print(dist_matrix)

    for i in range(1, N):
        print(np.count_nonzero(dist_matrix == i)//2)


main(N, X, Y)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# N=頂点数、X,Y=座標
N, X, Y = map(int, input().split())
X -= 1
Y -= 1

# 未セットの値
INF = 10**4

# キューデータ(次の値、最短距離)
queue_list = []

# 最短距離ごとのリスト
min_e_list = [0 for i in range(N)]

for i in range(N):
    # キューデータ初期値をセット
    queue_list.append([i, 0])
    # 最短距離リスト(最短距離)
    min_dist_list = [INF for i in range(N)] 

    # キューデータが空になるまで繰り返す
    while(len(queue_list) != 0):
        
        # 先頭データを取り出す。
        pop_data = queue_list.pop(0)

        # 取り出した座標がセット済みの場合は何もしない
        if(min_dist_list[pop_data[0]] != INF):
            continue

        # 最短距離リストにデータセット
        min_dist_list[pop_data[0]] = pop_data[1]

        # 2重に数えないよう(i < 取り出した座標時)、最短距離ごとのリストにデータセット
        if(i < pop_data[0]):
            min_e_list[pop_data[1]] += 1

        # 1.隣の頂点(次の座標、+1,-1した値)
        if(pop_data[0]+1 < N):
            queue_list.append([pop_data[0]+1, pop_data[1]+1])
        if(pop_data[0] > 0 and pop_data[0]-1 < N):
            queue_list.append([pop_data[0]-1, pop_data[1]+1])
        
        # 2.X,Yで示した値
        if(pop_data[0] < Y and pop_data[0] == X):
            queue_list.append([Y, pop_data[1]+1])
        if(pop_data[0] < X and pop_data[0] == Y):
            queue_list.append([X, pop_data[1]+1])

# 出力
for i,v in enumerate(min_e_list):
    if(i != 0):
        print(v)

Submission status: Time Limit Exceeded

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

def largest(a,b,c):
  if a <= b:
    if a<= c:
      return a
    else:
      return c
  else:
    if b<=c:
      return b
    else:
      return c
    
def absol(d):
  if d < 0:
    return -d
  else:
    return d
    
def dist(i,j):
  return largest(j-i, absol(x-i) + absol(y-j) + 1, absol(x-j) + absol(y-i) + 1)

listlist = [0]*(n-1)

for i in range(1,n):
  for j in range(i+1,n+1):
    distance = dist(i,j)
    listlist[distance-1] = listlist[distance-1] + 1
    
for k in listlist:
  print(k)

Submission status: Time Limit Exceeded

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

def largest(a,b,c):
  if a <= b:
    if a<= c:
      return a
    else:
      return c
  else:
    if b<=c:
      return b
    else:
      return c
    
def absol(d):
  if d < 0:
    return -d
  else:
    return d
    
def dist(i,j):
  return largest(j-i, absol(x-i) + absol(y-j) + 1, absol(x-j) + absol(y-i) + 1)

listlist = [0]*(n-1)

for i in range(1,n):
  for j in range(i+1,n+1):
    distance = dist(i,j)
    listlist[distance-1] = listlist[distance-1] + 1
    
for k in range(0, n-1):
  print(listlist[k])

Submission status: Time Limit Exceeded

Solution code:
#D

line = [int(x) for x in input().split()]
n = line[0]
x = line[1]
y = line[2]

results =[0]*(n+2)

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

for i in range(0, n-1):
    print(results[i])

Submission status: Time Limit Exceeded

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

for k in range(1, n):
  count = 0
  for i in range(1, n+1):
    for j in range(1, n+1):
      dist = min(abs(j-i), 1 + abs(x-i)+abs(y-j), 1 + abs(y-i)+abs(x-j))
      if dist == k:
        count+=1
  print(count//2)

Submission status: Time Limit Exceeded

Solution code:
n, x, y = [int(x) for x in input().split()]

#探索済リスト
done = [[i] for i in range(n)]

table = [[1]]

for i in range(n - 2):
    table += [[i, i + 2]]

table += [[n - 2]]
table[x - 1] += [y - 1]
table[y - 1] += [x - 1]

#i0を起点として i から距離 k の個数を求める
#該当する組み合わせ数を返す
def func(i0,i,past, L, cnt,done):
    #移動先可能リストに応じて探索
    for j in table[i]:
        #移動先が移動してきた地点でない場合のみ探索
        if j != i:            
            #距離が1ならば カウント
            if L == 1:
                # 以前の最短距離で到達している場所は計算場外する
                if j not in done[i0]:
                    done[i0] +=[j]
                    cnt += 1
            else:
                cnt, done = func(i0, j, i, L - 1, cnt, done)
    return(cnt,done)

#距離k (1 ～ n-1)に対する答えを出力
for k in range(1, n):
    ans = 0
    for i in range(n):
        cnt, done = func(i, i, i, k, 0, done)
        ans += cnt
    ans = ans//2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
N,X,Y=map(int,input().split())
d=[[10**7 for _ in range(N)] for _ in range(N)]
for a in range(1,N):
    d[a-1][a]=1
    d[a][a-1]=1
d[X-1][Y-1]=1
d[Y-1][X-1]=1

d = floyd_warshall(d)

ans=[0 for _ in range(N)]
for k in range(N):
    for l in range(k+1,N):
        if d[k][l]<N:
            ans[int(d[k][l])]+=1
    
for o in range(N-1):
    print(ans[o+1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
def mCn(m, n):
    def factorial_ntimes(m, n):
        r = 1
        while n:
            r *= m
            m -= 1
            n -= 1
        return r
    return int(factorial_ntimes(m, n) / factorial(n))

n, x, y = load_list()

class Node():
    def __init__(self, n):
        self.n = n
        self.adjs = []

    def add(self, adj):
        self.adjs.append(adj)

    def __str__(self):
        return self.n

nodes = dict()
for i in range(1, n+1):
    nodes[i] = Node(i)

for i in range(1, n):
    nodes[i].add(nodes[i+1])
    nodes[i+1].add(nodes[i])

nodes[x].add(nodes[y])
nodes[y].add(nodes[x])

# for node in nodes.values():
#     print("node: %d" % node.n)
#     for a in node.adjs:
#         print(a.n)

def inf():
    return 100000

dic = defaultdict()
mindict = defaultdict(inf)
for node in nodes.values():
    q = list()
    q.append((node, 0))
    while len(q):
        t, d = q.pop()
        for a in t.adjs:
            if node.n == a.n:
                continue
            # if a.n < t.n:
            #     continue
            s = tuple(sorted((node.n, a.n)))
            # print(s)
            if mindict[s] >= (d+1):
                mindict[s] = d+1
                q.append((a, d+1))
# print(mindict)

count = defaultdict(int)

for key in mindict.keys():
    count[mindict[key]] += 1

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

Submission status: Time Limit Exceeded

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

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

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

edge = np.array(edge, dtype = np.int64).T
graph = csr_matrix((edge[2], (edge[:2])), (N, N))

# print (graph)

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import deque
def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    D = [[0 for _ in range(N)] for _ in range(N)]
    D[X][Y] = 1
    D[Y][X] = 1
    queue = deque([[X, Y]])
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[X][Y] = True 
    ans = [0 for _ in range(N)]
    while queue:
        x,y = queue.popleft()
        for i, j in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+i, y+j
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if visited[nx][ny]:
                continue
            else:
                visited[nx][ny] = True
                D[nx][ny] = min(abs(ny-nx), D[x][y]+1)
                queue.append([nx, ny])
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            v = D[i][j]
            ans[v-1] += 1
    print(*ans[:-1], sep="\n")
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
def mCn(m, n):
    def factorial_ntimes(m, n):
        r = 1
        while n:
            r *= m
            m -= 1
            n -= 1
        return r
    return int(factorial_ntimes(m, n) / factorial(n))

n, x, y = load_list()

class Node():
    def __init__(self, n):
        self.n = n
        self.adjs = []

    def add(self, adj):
        self.adjs.append(adj)

    def __str__(self):
        return self.n

nodes = dict()
for i in range(1, n+1):
    nodes[i] = Node(i)

for i in range(1, n):
    nodes[i].add(nodes[i+1])
    nodes[i+1].add(nodes[i])

nodes[x].add(nodes[y])
nodes[y].add(nodes[x])

# for node in nodes.values():
#     print("node: %d" % node.n)
#     for a in node.adjs:
#         print(a.n)

def inf():
    return 100000


dist2count = defaultdict(int)
for node in nodes.values():
    visited = set()
    visited.add(node.n)
    dist = defaultdict(int)
    dist[node.n] = 0
    q = deque()
    q.append(node)
    while len(q):
        t = q.popleft()
        for a in t.adjs:
            if a.n in visited:
                continue
            dist[a.n] = dist[t.n] + 1
            visited.add(a.n)
            q.append(a)
    for target, dist in dist.items():
        if target == node.n:
            continue
        dist2count[dist] += 1
        # print("(%d,%d) -> %d " % (node.n, target, dist))

for k in range(1, n):
    print(dist2count[k] // 2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import deque
def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    D = [[float("inf") for _ in range(N)] for _ in range(N)]
    D[X][Y] = 1
    D[Y][X] = 1
    queue = deque([[X, Y]])
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[X][Y] = True 
    while queue:
        x,y = queue.popleft()
        for i, j in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+i, y+j
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if visited[nx][ny]:
                continue
            else:
                visited[nx][ny] = True
                D[nx][ny] = min(abs(ny-nx), D[x][y]+1)
                queue.append([nx, ny])
    ans = [0 for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            v = D[i][j]
            ans[v-1] += 1
    print(*ans[:-1], sep="\n")
main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import deque
def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    D = [[float("inf") for _ in range(N)] for _ in range(N)]
    D[X][Y] = 1
    D[Y][X] = 1
    queue = deque([[X, Y]])
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[X][Y] = True 
    while queue:
        x,y = queue.popleft()
        for i, j in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+i, y+j
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if visited[nx][ny]:
                continue
            else:
                visited[nx][ny] = True
                D[nx][ny] = min(abs(ny-nx), D[x][y]+1)
                queue.append([nx, ny])
    ans = [0 for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            v = D[i][j]
            ans[v-1] += 1
    print(*ans[:-1], sep="\n")
main()

Submission status: Time Limit Exceeded

Solution code:
n, x, y = [int(x) for x in input().split()]

#探索済リスト
done = [[i] for i in range(n)]

table = [[1]]

for i in range(n - 2):
    table += [[i, i + 2]]

table += [[n - 2]]
table[x - 1] += [y - 1]
table[y - 1] += [x - 1]


#i0を起点として i から距離 k の個数を求める
#該当する組み合わせ数を返す
def func(i0,i, L, cnt,done):
    #移動先可能リストに応じて探索
    for j in table[i]:
        #距離が1ならば カウント
        if L == 1:
            # 以前の最短距離で到達している場所は計算場外する
            if j not in done[i0]:
                done[i0] +=[j]
                cnt += 1
        else:
            cnt,done = func(i0,j, L - 1, cnt,done)
    return(cnt,done)

#距離k (1 ～ n-1)に対する答えを出力
for k in range(1, n):
    ans = 0
    for i in range(n):
        cnt, done = func(i, i, k, 0,done)
        ans += cnt
    ans = ans//2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, X, Y = [int(x) for x in input().strip().split()]
D = defaultdict(int)
L = [[i-1, i+1] for i in range(1, N+1)]
L[0] = [L[0][1]]
L[-1] = [L[-1][0]]
L[X-1].append(Y)
L[Y-1].append(X)

def bfs(i):
    ni = deque(L[i-1])
    c = 1
    C = [0] * N
    C[i-1] = -1
    while ni:
        nii = ni
        ni = deque([])
        for niii in nii:
            if C[niii-1] != 0:
                continue
            C[niii-1] = c
            if niii > i:
                D[c] += 1
            ni.extend(L[niii-1])
        c += 1
    return True

for n in range(1, N+1):
    bfs(n)

for n in range(1, N):
    print(D[n])

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
edge=[]
for i in range(int(n)):
    tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
    edge.append(tmp)
edge[x-1][y-1]=1
edge[y-1][x-1]=1
#print(edge)

def bfs(start,goal,graph):
    keiro={}
    i=0
    Tovisit=[start]
    visited=[]
    while len(Tovisit)>0:
        #print(Tovisit)
        if goal in Tovisit:
            break      
        nex=Tovisit.pop(0)
        visited.append(nex)
        #行けるポイントを探す G[nex][]!=none
        for v in range(len(graph[nex])):
            if graph[nex][v]!=-1:
                if v in visited:
                    continue
                if v in Tovisit:
                    continue
                Tovisit.append(v)
                keiro[v]=nex
    sum=0
    x=goal
    while x!=start:
        sum+=1
        x=keiro[x]
    return sum

for k in range(1,n):
    num=0
    for i in range(n):
        for j in range(i,n):
            if bfs(i,j,edge)==k:
                num+=1
    print(num)

Submission status: Time Limit Exceeded

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

d=[[10**7 for _ in range(N)] for _ in range(N)]
for a in range(1,N):
    d[a-1][a]=1
    d[a][a-1]=1
d[X-1][Y-1]=1
d[Y-1][X-1]=1

for i in range(N):
    for j in range(N):
        for k in range(N):
            d[i][j]=min(d[i][k]+d[k][j],d[i][j])
for i in range(N):
    for j in range(N):
        for k in range(N):
            d[i][j]=min(d[i][k]+d[k][j],d[i][j])

ans=[0 for _ in range(N)]
for k in range(N):
    for l in range(k+1,N):
        if d[k][l]<N:
            ans[d[k][l]]+=1
    
for o in range(N-1):
    print(ans[o+1])

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n, x, y = map(int, input().split())
anslist = []
for i in range(n-1):
    anslist.append(0)

for s in range(1,n):
    for p in range(s+1,n+1):
        dsp = abs(p - s)
        dsxyp = abs(x - s) + 1 + abs(p - y)
        dsyxp = abs(y - s) + 1 + abs(p - x)
        distance = min(dsp,dsxyp,dsyxp)
        anslist[distance - 1] += 1

for k in range(len(anslist)):
    print("{}".format(anslist[k]))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n, x, y = map(int, input().split())
anslist = []
for i in range(n-1):
    anslist.append(0)

for s in range(1,n):
    for p in range(s+1,n+1):
        dsp = abs(p - s)
        dsxp = abs(x - s) + abs(p - x)
        dsyp = abs(y - s) + abs(p - y)
        dsxyp = abs(x - s) + 1 + abs(p - y)
        dsyxp = abs(y - s) + 1 + abs(p - x)
        distance = min(dsp,dsxp,dsyp,dsxyp,dsyxp)
        anslist[distance - 1] += 1

for k in range(len(anslist)):
    print("{}".format(anslist[k]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, x, y = [int(i) for i in input().split()]

def short_dis(a,b,X,Y):
    simple_roo = abs(a-b)
    xy_roo = min(abs(a-X),abs(a-Y)) + min(abs(b-X),abs(b-Y)) +1
    
    short_roo = min(simple_roo,xy_roo)
    
    return short_roo

ans = {}
for i in range(1,n):
    ans[i] = 0
    
    

for i in range(2,n+1):
    for j in range(1,i):
        if i !=j:
            dist = int(short_dis(i,j,x,y))
            ans[dist]+=1

for i in list(ans.values()):
    print(int(i))

Submission status: Time Limit Exceeded

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

def largest(a,b,c):
  if a <= b:
    if a<= c:
      return a
    else:
      return c
  else:
    if b<=c:
      return b
    else:
      return c
    
def absol(d):
  if d < 0:
    return -d
  else:
    return d
    
def dist(i,j):
  return largest(j-i, absol(x-i) + absol(y-j) + 1, absol(x-j) + absol(y-i) + 1)

listlist = []
for t in range(1,n):
  listlist.append([t,0])

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

for t in range(0,n-1):
  print(listlist[t][1])

Submission status: Time Limit Exceeded

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

from collections import defaultdict
d = defaultdict(int)

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, x, y = [int(x) for x in input().split()]
x -= 1
y -= 1
BIG = 65521
ans = {i: 0 for i in range(n)}


def bfs(start_v):
    """ある始点からほかの全点に行くまでの最短距離を求める。"""
    qu = deque()
    qu_append = qu.append
    qu_popleft = qu.popleft
    qu_append(start_v)
    # 始点からvに移動するまでの最短距離: dist[v]
    dist = [BIG] * n

    def push(v, d):
        """始点からvまでの最短距離が算出されていないときに，その距離を保存し，
        キューに頂点vを追加する。"""
        if dist[v] != BIG:
            # 既に訪問済みで距離が求められている。
            return
        dist[v] = d
        qu_append(v)

    push(start_v, 0)

    while len(qu):
        v = qu_popleft()
        # 始点からvの次の頂点へ移動する距離。
        d = dist[v] + 1
        if v < n - 1:
            push(v + 1, d)
        if v > 0:
            push(v - 1, d)
        if v == x:
            push(y, d)
        if v == y:
            push(x, d)

    for i in range(n):
        if dist[i] != 0:
            ans[dist[i]] += 1


def main():
    for i in range(n):
        bfs(i)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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):
        diff1 = j - i
        diff2 = x + y - i - j + 1
        if i <= x and j >= y:
            diff2 = x - y - i + j + 1
        elif x <= i <= y and x <= j <= y:
            diff2 = -x + y + i - j + 1
        elif x < i < y and j > y:
            diff2 = -x - y + i + j + 1
        if diff2 < 1:
            diff2 = diff1
        diff = min(diff1, diff2)
        ans[diff] = ans[diff] + 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, x, y = [int(x) for x in input().split()]
x -= 1
y -= 1
BIG = 65521
ans = [0] * n


def bfs(start_v):
    """ある始点からほかの全点に行くまでの最短距離を求める。"""
    qu = deque()
    qu_append = qu.append
    qu_popleft = qu.popleft
    qu_append(start_v)
    # 始点からvに移動するまでの最短距離: dist[v]
    dist = [BIG] * n

    def push(v, d):
        """始点からvまでの最短距離が算出されていないときに，その距離を保存し，
        キューに頂点vを追加する。"""
        if dist[v] != BIG:
            # 既に訪問済みで距離が求められている。
            return
        dist[v] = d
        qu_append(v)

    push(start_v, 0)

    while len(qu):
        v = qu_popleft()
        # 始点からvの次の頂点へ移動する距離。
        d = dist[v] + 1
        if v < n - 1:
            push(v + 1, d)
        if v > 0:
            push(v - 1, d)
        if v == x:
            push(y, d)
        if v == y:
            push(x, d)

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


def main():
    for i in range(n):
        bfs(i)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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