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:
import sys
# sys.stdin = open('input.txt')

from collections import deque

class Node:
    def __init__(self, num=None):
        self.num = num
        self.next = []
        self.visited = False

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

nodes = []
q = deque()
ans = [0] * n

x -= 1
y -= 1

for i in range(n):
    node = Node(i)
    nodes.append(node)

# 無向グラフ
for i in range(n):
    node = nodes[i]
    if i == 0:
        node.next.append(nodes[i+1])
    elif i == n-1:
        node.next.append(nodes[i-1])
    else:
        node.next.append(nodes[i-1])
        node.next.append(nodes[i+1])
    if i == x:
        node.next.append(nodes[y])
    elif i == y:
        node.next.append(nodes[x])

# Select the initial node
for i in range(n):
    # Initialize
    dist = [0] * n
    for node in nodes:
        node.visited = False

    # add the initial node
    q.append(nodes[i])

    # BFS
    while len(q) > 0:
        node = q.popleft()
        node.visited = True

        if node.next is not None:
            for next_node in node.next:
                if not next_node.visited:
                    dist[next_node.num] = dist[node.num] + 1
                    next_node.visited = True
                    q.append(next_node)
    for i in range(n):
        ans[i] += dist.count(i)

#  Remove duplications -(1,2), (2,1)
for i in range(i):
    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())
for k in range(1, n):
    min_combi_set = list()
    for i in range(1, n+1):
        for j in range(1, i):
            min_distance = min(abs(i-j), abs(x-i) + 1 + abs(j-y),abs(y-i) + 1 + abs(x-j))
            if min_distance == k:
                min_combi_set.append({i, j})
    print(len(min_combi_set))

Submission status: Time Limit Exceeded

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

answer = []

for i in range(n - 1):
  for j in range(i + 1, n):
    answer.append(min(abs(j - i), abs(i + 1 - x) + 1 + abs(j + 1 - y)))
    
for i in range(n - 1):
  print(answer.count(i + 1))

Submission status: Time Limit Exceeded

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

distance_list = []

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


for i in range(1, N):
    ans = distance_list.count(i)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, X, Y = [int(i) for i in input().split()]
X, Y = X-1, Y-1

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

for i in range(1, N):
    print(dd[i] // 2)

Submission status: Time Limit Exceeded

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

A = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N-i):
        A[i][i + j] = min(abs(x- i) +1 +abs(y-i-j),j)
A[X-1][Y-1] = 1
ans = []
ans.append(sum(A, []))
for t in range(N):
    if t == 0:
        continue
    sum =  A.count(t)
    print(ans[0].count(t))

Submission status: Time Limit Exceeded

Solution code:
import copy
N, X, Y = input().split()
N = int(N)
X = int(X)
x = X - 1
Y = int(Y)
y = Y -1

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

for p in range(N):
    ans.append(sum(A, []))
for t in range(N):
    if t == 0:
        continue
    sum =  A.count(t)
    print(ans[0].count(t))

Submission status: Time Limit Exceeded

Solution code:
import copy
N, X, Y = input().split()
N = int(N)
X = int(X)
x = X - 1
Y = int(Y)
y = Y -1

A = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N-i):
        A[i][i + j] = min(abs(x- i) +1 +abs(y-i-j),j)
A[X-1][Y-1] = 1
for t in range(N):
    if t == 0:
        continue
    sum = 0
    for u in range(N):
        sum = sum + A[u].count(t)

    print(sum)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def dfs(rel, s):
    dist = [-1] * len(rel)

    q = deque()
    q.append(s)
    dist[s] = 0

    while len(q):
        e = q.popleft()
        for ei in Rel[e]:
            if dist[ei] >= 0:
                continue
            q.append(ei)
            dist[ei] = dist[e] + 1

    ans = [0] * (len(rel) - 1)
    for d in dist:
        ans[d] += 1
    return ans


N, X, Y = map(int, input().split())
Rel = [None] + [[] for _ in range(N)]
for i in range(1, N + 1):
    if i > 1:
        Rel[i].append(i - 1)
    if i < N:
        Rel[i].append(i + 1)
Rel[X].append(Y)
Rel[Y].append(X)

K = [0] * (N - 1)

for i in range(1, N + 1):
    dist = dfs(Rel, i)
    for k, v in enumerate(dist[1:]):
        K[k] += v

for k in K[:-1]:
    print(k // 2)
print(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import Counter

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

n_iter = itertools.combinations(list(range(1,N+1)), 2)

count_list = []

for i, j in n_iter:
  #1. abs(X - i) + abs(Y - j) + 1
  #2. abs(Y - i) + abs(X - j) + 1
  #3. abs(j - i)
  x = min(
    abs(X - i) + abs(Y - j) + 1,
    abs(Y - i) + abs(X - j) + 1,
    abs(j - i)
  )
  count_list.append(x)

# 要素数の数え上げと取り出し
num_counter = Counter(count_list)
for i in range(1, N):
  if i in num_counter:
    print(num_counter[i])
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import Counter

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

xy = 0

n_list = list(range(1,N+1))
n_iter = itertools.combinations(n_list, 2)

count_list = []

for i, j in n_iter:
  #1. abs(X - i) + abs(Y - j) + 1
  #2. abs(Y - i) + abs(X - j) + 1
  #3. abs(j - i)
  x = min(
    abs(X - i) + abs(Y - j) + 1,
    abs(Y - i) + abs(X - j) + 1,
    abs(j - i)
  )
  count_list.append(x)

# 要素数の数え上げと取り出し
num_counter = Counter(count_list)
for i in range(1, N):
  if i in num_counter:
    print(num_counter[i])
  else:
    print(0)

Submission status: Time Limit Exceeded

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

g = [[]  for i in range(N)]
for i in range(N):
    u = i
    v = i + 1
    if v < N:
        g[u].append(v)
        g[v].append(u)

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

from collections import deque
dis = [[float('Inf')] * N for _ in range(N)]
count = [0] * (N - 1)
def bfs(i):
    d = [False] * N
    que = deque()
    #for j in g[i]:
    que.append(i)
    d[i] = True
    dis[i][i] = 0
    pre = i
    while que:
        p = que.popleft()

        for k in g[p]:
            if d[k]:
                continue
            else:
                d[k] = True
                que.append(k)
                dis[i][k] = dis[i][p] + 1
                dis[k][i] = dis[i][p] + 1
                count[dis[i][k] - 1] += 1 
                #count[dis[k][i] - 1] += 1
        pre = p

for i in range(N):
    bfs(i)

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

Submission status: Time Limit Exceeded

Solution code:
def get_grid(N):
    grid = [[1 + N for _ in range(N)] for _ in range(N)]
    for i in range(N - 1):
        grid[i][i + 1] = 1
        grid[i + 1][i] = 1
    return grid

def print_grid(grid):
    for row in grid:
        print(row)
    print()

N, X, Y = list(map(int, input().split()))
grid = get_grid(N)
grid[X - 1][Y - 1] = 1
grid[Y - 1][X - 1] = 1

# print_grid(grid)

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

# print_grid(grid)

from collections import defaultdict

counter = defaultdict(lambda: set())
for i in range(N):
    for j in range(N):
        if i != j:
            counter[grid[i][j]].add((min([i, j]), max([i, j])))

# print(counter)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
class Graph:
    def __init__(self,w_v,w_e):
        super().__init__()
        self.size = len(w_v)
        self.w_v = [v_i for v_i in w_v]#value of vartex
        self.w_e = [{} for _ in [0]*self.size]

        self.maxw = 0

        self.neighbor = [[] for _ in [0]*self.size]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i#weight of edge
            self.w_e[b_i][a_i] = w_i#weight of edge

            self.neighbor[a_i].append(b_i)
            self.neighbor[b_i].append(a_i)
            self.maxw+=w_i

    def dijkstra(self,v_n):
        d = [self.maxw]*self.size
        d[v_n] = 0
        prev = [-1]*self.size

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

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

    w_v = [0]*n
    w_e = [(i,i+1,1) for i in range(n-1)]
    w_e.append((x-1,y-1,1))

    g = Graph(w_v,w_e)

    distance = [g.dijkstra(i)[0] for i in range(n)]

    res = [0]*n
    for dmin_ in distance:
        for d in dmin_:
            res[d] += 1

    for r in res[1:n]:
        print(r//2)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    if i == 0:
        edge[i].append([1,i+1])
    elif i == w-1:
        edge[i].append([1,i-1])
    else:
        edge[i].append([1,i+1])
        edge[i].append([1,i-1])
edge[X-1].append([1,Y-1])
edge[Y-1].append([1,X-1])

ans = [0]*(N+1)
tmp = []
for i in range(N):
    tmp.append(dijkstra_heap(i,edge)[i+1:])

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

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

Submission status: Time Limit Exceeded

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

dic = defaultdict(int)

X = X - 1
Y = Y - 1

for i in range(N):
    for j in range(i + 1, N):
        if i <= X and Y <= j:
            v = X - i + 1 + j - Y
        elif (i <= X) and (X <= j and j <= Y):
            v = min(j - i, X - i + 1 + Y - j)
        elif (X <= i and i <= Y) and Y <= j:
            v = min(j - i, i - X + 1 + j - Y)
        elif (X <= i and i <= Y) and (X <= j and j <= Y):
            v = min(j - i, i - X + 1 + Y - j)
        else:
            v = j - i

        dic[v] += 1


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

Submission status: Time Limit Exceeded

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

def bfs(u):
    dist = [-1 for _ in range(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 d in dist:
        if d == 0:
            continue
        ans[d-1] += 1
    return ans


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

ans = [0]*(n-1)
for i in range(n):
    bfs(i)

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

Submission status: Time Limit Exceeded

Solution code:
"""
https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC%28heapq%29%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95
"""
import heapq
import sys

input = sys.stdin.readline

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

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

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    if i == 0:
        edge[i].append([1,i+1])
    elif i == w-1:
        edge[i].append([1,i-1])
    else:
        edge[i].append([1,i+1])
        edge[i].append([1,i-1])

edge[X-1].append([1,Y-1])
edge[Y-1].append([1,X-1])
tmp = []
for i in range(N):
    tmp.append(dijkstra_heap(i,edge))
ans = [0]*(N+1)
for i in range(N):
    for j in range(i,N):
        ans[tmp[i][j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

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

inf=1001001001
answer=[0]*(N-1)

for j in range(N):
    v=[inf]*N
    q=Queue()
    q.put(j)
    #print(q)
    v[j]=0
    while not q.empty():
        i=q.get()
        if i-1>=0 and v[i-1]==inf:
            v[i-1]=v[i]+1
            q.put(i-1)
            #print(i-1)
        if i+1<N and v[i+1]==inf:
            v[i+1]=v[i]+1
            q.put(i+1)
            #print(i+1)
        if i==X-1 and v[Y-1]==inf:
            v[Y-1]=v[i]+1
            q.put(Y-1)

        if i==Y-1 and v[X-1]==inf:
            v[X-1]=v[i]+1
            q.put(X-1)
        #print(v)
    #print(v)
    for k in v:
        if k>0:
            answer[k-1]+=1
for a in answer:
    print(a//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,x,y=map(int,input().split())
d=defaultdict(list)
for i in range(1,n):
    for j in range(i+1,n+1):
        r=min(abs(i-j),abs(x-i)+1+abs(y-j),abs(x-j)+1+abs(y-i))
        d[r].append((i,j))
for i in range(1,n):
    print(len(d[i]))

Submission status: Time Limit Exceeded

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

K = [0 for _ in range(N)]
INF = 10 ** 9
def bfs(n):
    d = deque()
    d.append(n)
    reached = [INF for _ in range(N)]
    reached[n] = 0
    dx = [-1, 1]
    while d:
        x = d.popleft()
        for i in range(2):
            nx = x + dx[i]
            if nx < 0 or nx > N - 1 or reached[nx] != INF:
                continue
            d.append(nx)
            reached[nx] =reached[x] + 1
        if x == X-1 and reached[Y-1] == INF:
            reached[Y-1] = reached[x] + 1
            d.append(Y-1)
        if x == Y-1 and reached[X-1] == INF:
            reached[X-1] = reached[x] + 1
            d.append(X-1)
    for i in range(N):
        K[reached[i]] += 1            

for i in range(N):
    bfs(i)

for i in range(1, N):
    print(K[i]//2)

Submission status: Time Limit Exceeded

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

K = [0 for _ in range(N)]
INF = 10 ** 9
def bfs(n):
    d = deque()
    d.append(n)
    reached = [INF for _ in range(N)]
    reached[n] = 0
    dx = [-1, 1]
    while d:
        x = d.popleft()
        for i in range(2):
            nx = x + dx[i]
            if nx < 0 or nx > N - 1 or reached[nx] != INF:
                continue
            d.append(nx)
            reached[nx] =reached[x] + 1
        if x == X-1 and reached[Y-1] == INF:
            reached[Y-1] = reached[x] + 1
            d.append(Y-1)
        if x == Y-1 and reached[X-1] == INF:
            reached[X-1] = reached[x] + 1
            d.append(X-1)
    for i in range(N):
        K[reached[i]] += 1            

for i in range(N):
    bfs(i)

for i in range(len(K)):
    K[i] = K[i] // 2

for i in range(1, len(K)):
    print(K[i])

Submission status: Time Limit Exceeded

Solution code:
def inpl():
    return list(map(int, input().split()))


N, X, Y = inpl()
X -= 1
Y -= 1
ans = {}
for i in range(N):
    for j in range(i + 1, N):
        c = min(j - i, abs(i - X) + 1 + abs(j - Y), abs(i - Y) + 1 + abs(j - X))
        ans[c] = ans.get(c, 0) + 1

for i in range(1, N):
    print(ans.get(i, 0))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N, X, Y = map(int, input().split())
g = [[float("inf")] * N for _ in range(N)]

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

c = Counter()
for i in range(N):
    c.update(g[i][:i])

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N, X, Y = (int(i) for i in input().split())
#B = [int(x) for x in stdin.readline().rstrip().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]

ans = []

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

#print(N)
for k in range(1, N):
    print(ans.count(k))

Submission status: Time Limit Exceeded

Solution code:
import heapq


def inpl():
    return list(map(int, input().split()))


class Graph:
    def __init__(self):
        self.edge = {}
        self.cost = {}
        self.vertex = set()
        return

    def addEdgeCost(self, i, j, c, directed=False):
        self.vertex.add(i)
        self.vertex.add(j)

        if i not in self.edge:
            self.edge[i] = []
        self.edge[i].append(j)
        self.cost[(i, j)] = c

        if directed is False:
            return

        if j not in self.edge:
            self.edge[j] = []
        self.edge[j].append(i)
        self.cost[(j, i)] = c
        return


def dijkstra(g: Graph, s=None) -> dict:
    def solve(v_start):
        ret_cost = {v: float("inf") for v in g.vertex}
        ret_cost[v_start] = 0
        heap = [(0, v_start)]

        while heap:
            _, v_from = heapq.heappop(heap)
            for v_to in g.edge.get(v_from, []):
                nc = ret_cost[v_from] + g.cost[(v_from, v_to)]
                if ret_cost[v_to] > nc:
                    ret_cost[v_to] = nc
                    heapq.heappush(heap, (nc, v_to))
        return ret_cost

    if s is None:
        V = g.vertex
    else:
        V = [s]

    ret = {}
    for v in V:
        ret[v] = solve(v)
    return ret


N, X, Y = inpl()

G = Graph()
for i in range(N - 1):
    G.addEdgeCost(i, i + 1, 1, directed=True)
G.addEdgeCost(X - 1, Y - 1, 1, directed=True)

ans_dict = {}
for g in dijkstra(G).values():
    for v in g.values():
        ans_dict[v] = ans_dict.get(v, 0) + 1

for i in range(1, N):
    print(ans_dict.get(i, 0) // 2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,X,Y=map(int,input().split())
    X-=1
    Y-=1
    
    d=[[INF]*N for _ 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
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    ans=[0]*N
    for i in range(N-1):
        for j in range(i+1,N):
            ans[d[i][j]]+=1
    for row in ans[1:]:
        print(row)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

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

answer = [0 for _ in range(0, N)]
for i in range(1, N+1):
    for j in range(i, N+1):
        distance1 = abs(i - j)
        distance2 = abs(X-i) + abs(Y-j) + 1
        distance3 = abs(X-j) + abs(Y-i) + 1
        min_distance = min(distance1, distance2, distance3)
        answer[min_distance] += 1
for i, a in enumerate(answer):
    if i != 0:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
Es=[(i,i+1) for i in range(N-1)]
Es.append((X-1,Y-1)) 
for i in range(len(Es)):
    aa,bb=Es[i]
    Es.append((bb,aa))
#print(Es)
c=[[N+1 for _ in range(N)]for _ in range(N)]
#print(c)
for each in Es:
    f,t=each
    c[f][t]=1
 
#COST=tuple(c)
D=tuple([N+1 for _ in range(N)])
USED=tuple([False for _ in range(N)])
#ans=[]
ans_2=[0 for _ in range(N-1)]
for i in range(N):
    cost= c#list(COST)
    d=list(D)
    used=list(USED)
    d[i]=0
    while True:
        v=-1
        for u in range(N):
            if not used[u] and ( v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(N):
            d[u] = min(d[u],d[v]+cost[v][u])
    #print(d)
    #ans+=d[i:]
    for each in d[i+1:]:
        ans_2[each-1]+=1
#print(ans)
#for i in range(N-1):
#    print(ans.count(i+1))
for each in ans_2:
    print(each)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

from collections import deque

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

answer = deque([0 for _ in range(0, N)])
for i in range(1, N+1):
    for j in range(i, N+1):
        distance1 = abs(i - j)
        distance2 = abs(X-i) + abs(Y-j) + 1
        distance3 = abs(X-j) + abs(Y-i) + 1
        min_distance = min(distance1, distance2, distance3)
        answer[min_distance] += 1
answer.popleft()
for a in answer:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

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

answer = [0 for _ in range(0, N)]
for i in range(1, N+1):
    for j in range(i, N+1):
        distance1 = abs(i - j)
        distance2 = abs(X-i) + abs(Y-j) + 1
        distance3 = abs(X-j) + abs(Y-i) + 1
        min_distance = min(distance1, distance2, distance3)
        answer[min_distance] += 1
for a in answer[1:]:
    print(a)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

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

answer = [0 for _ in range(0, N)]
seen = []
for i in range(1, N+1):
    for j in range(1, N+1):
        if i == j:
            continue
        if {i, j} in seen:
            continue
        distance1 = abs(i - j)
        distance2 = abs(X-i) + abs(Y-j) + 1
        distance3 = abs(X-j) + abs(Y-i) + 1
        min_distance = min(distance1, distance2, distance3)
        seen.append({i, j})
        answer[min_distance] += 1
for a in answer[1:]:
    print(a)

Submission status: Time Limit Exceeded

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

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

def bfs(i, j):
    dist = [-1]*N
    dist[i] = 0
    que = collections.deque([])
    que.append(i)
    
    while len(que) != 0:
        v = que.popleft()
        for nv in graph[v]:
            if dist[nv] != -1:continue
            dist[nv] = dist[v]+1
            if nv == j:break
            que.append(nv)
    return dist[j]

graph = {}
for i in range(N):
    graph[i] = set()

for i in range(N-1):
    graph[i].add(i+1)
    graph[i+1].add(i)
graph[X-1].add(Y-1)
graph[Y-1].add(X-1)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse
N,X,Y = (int(x) for x in input().split())
lil = scipy.sparse.lil_matrix((N, N))
for i in range(N-1):
    lil[i, i+1] = 1
    lil[i+1, i] = 1
lil[X-1, Y-1] = 1
lil[Y-1, X-1] = 1
lil2 = scipy.sparse.csgraph.dijkstra(lil)
k = [((np.count_nonzero(lil2 == i)) // 2) for i in range(1,N)]
for j in range(N-1):
    print(k[j])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

def bfs(i, j):
    dist = [-1]*N
    dist[i] = 0
    que = collections.deque([])
    que.append(i)
    
    while len(que) != 0:
        v = que.popleft()
        for nv in graph[v]:
            if dist[nv] != -1:continue
            dist[nv] = dist[v]+1
            que.append(nv)
    return dist[j]

graph = {}
for i in range(N):
    graph[i] = set()

for i in range(N-1):
    graph[i].add(i+1)
    graph[i+1].add(i)
graph[X-1].add(Y-1)
graph[Y-1].add(X-1)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse
N,X,Y = (int(x) for x in input().split())
lil = scipy.sparse.lil_matrix((N, N))
for i in range(N-1):
    lil[i, i+1] = 1
    lil[i+1, i] = 1
lil[X-1, Y-1] = 1
lil[Y-1, X-1] = 1
lil2 = scipy.sparse.csgraph.dijkstra(lil)
for i in range(1,N):
    print((np.count_nonzero(lil2 == i)) // 2)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
answers=[0]*(N-1)
for i in range(1,N+1):
    numbers=[a for a in range(1,N+1) if a!=i]
    for j in numbers:
        answer=min(abs(i-j),abs(X-i)+1+abs(j-Y),abs(i-Y)+1+abs(j-X))
        answers[answer-1]+=1
for a in answers:
    print(a//2)

Submission status: Time Limit Exceeded

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

x = x-1
y = y-1

count_dict = {i : 0 for i in range(0, n)}

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dlist = []
for i in range(1,N+1):
  for j in range(i,N+1):
    dis = min( abs(j-i), abs(X-i) +1+abs(j-Y), abs(Y-i) +1+abs(j-X) )
    dlist.append(dis)
    
for i in range(1,N):
  cnt = 0
  for val in dlist:
    if( val == i ):
      cnt+=1
  print( cnt )

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
A=[]
for i in range(N-1):
    A.append([-1]*(N-1-i))

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

for k in range(N-1):
    print(Ndmin[k])