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
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n) 


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

    for i in range(N):
        q = queue.Queue()
        q.put((i, 0))
        close = set()
        while not q.empty():
            s, c = q.get()
            if s in close:
                continue
            
            close.add(s)
            res[c] += 1

            if s + 1 < N and s + 1 not in close:
                q.put((s + 1, c + 1))
            if s > 0 and s - 1 not in close:
                q.put((s - 1, c + 1))
            if s == X and Y not in close:
                q.put((Y, c + 1))
            if s == Y and X not in close:
                q.put((X, c + 1))

    res = map(lambda l: str(l // 2), res[1:])
    print("\n".join(res))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
n, x, y = map(int, input().split())

links = [[] for i in range(n)]
for i in range(1, n):
        links[i-1].append(i)
        links[i].append(i-1)
links[x-1].append(y-1)
links[y-1].append(x-1)

ans = [0] * (n+1)
dist = [[1e11]*n for i in range(n)]
for i in range(n):
        used = [0 for i in range(n)]
        que = Queue()
        que.put([i, 0])
        while que.qsize():
                v, dis = que.get()
                used[v] = True
                for to in links[v]:
                        if not used[to]:
                                dist[i][to] = min(dist[i][to], dis+1)
                                que.put([to, dis+1])
        for a in dist[i]:
                if a!=1e11: ans[a] += 1
for i in range(n-1): print(ans[i+1]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1, n):
        if j < x or i > y:
            dist = j-i
        else:
            dist = min([j - i, abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 

res = [str(one) for one in final]
print ("\n".join(res))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, deque

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

    def bfs(i):
        q = deque()
        q.append(i)
        while len(q):
            now = q.popleft()
            for j in edge[now]:
                if j == i:
                    continue

                if not cost[j]:
                    cost[j] = cost[now] + 1
                    q.append(j)
        
    ct = Counter()
    for i in range(N):
        cost = [0] * N
        bfs(i)
        ct += Counter(cost)

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations
from collections import Counter

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

nodes = list(range(1, N + 1))
distance_counter = Counter()
a = Y - X - 1
p = (Y - X) // 2 + X
ans = []
for i, j in combinations(nodes, 2):
    if j - i == 1:
        continue
    distance = min(abs(X - i) + abs(Y - j) + 1, j - i)
    distance_counter[distance] += 1

for k in range(1, N):
    if k == 1:
        ans.append(N)
    else:
        ans.append(distance_counter.get(k, 0))

print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

for i in range(n - 1):
    edge[i].append([1, i + 1])
    edge[i + 1].append([1, i])

edge[x - 1].append([1, y - 1])
edge[y - 1].append([1, x - 1])

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

d = dijkstra_heap(0)
# print(d)

ans = [0] * (n)
# print(edge)
for i in range(n):
    d = dijkstra_heap(i)
    # print(d)
    for j in d:
        if j != float("inf"):
            ans[j] += 1

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

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

Submission status: Time Limit Exceeded

Solution code:
# D - Line++
import numpy as np 

N, X, Y = map(int, input().split())
cnt = np.zeros(N, dtype=np.int64)
T = np.zeros((N,N), dtype=np.int64)
for i in range(N):
    for j in range(i+1,N):
         tmp = min(j-i, abs(i-X+1)+abs(j-Y+1)+1)
         T[i,j] = tmp
         cnt[tmp] += 1

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

Submission status: Time Limit Exceeded

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

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):
        if i <= x:
            if abs(i +j -x) <= abs(y - i -j):
                A[i][i+j] = j
            elif abs(i + j -x) > abs(y - i -j):
                A[i][i + j] = x-i + 1 + abs(y - (i+j))
        elif i>x:
            if abs(x-i)<= abs(y-i):
                A[i][i + j] = min(abs(x- i) +1 +abs(y-i-j),j)
            else:
                A[i][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:
N, X, Y = map(int, input().split())

for k in range(1,N):
    ans = 0
    for i in range(1,N):
        for j in range(i,N+1):
            min_dis = min((j-i), abs(X-i)+1+abs(j-Y))
            if min_dis == k:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,X,Y=map(int, input().split())
ans = np.zeros(N-1)
for i in range(1,N):
  for j in range(i+1,N+1):
    root1 = j-i
    root2 = abs(X-i) + 1 + abs(Y-j)
    min_k = min(root1, root2)
    ans[min_k-1] = ans[min_k-1] + 1

for a in ans:
  print(int(a))

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
n, x, y = map(int, input().split())

links = [[] for i in range(n)]
for i in range(1, n):
        links[i-1].append(i)
        links[i].append(i-1)
links[x-1].append(y-1)
links[y-1].append(x-1)

ans = [0] * (n+1)
dist = [[1e11]*n for i in range(n)]
for i in range(n):
        used = [0] * n
        que = Queue()
        que.put([i, 0])
        while que.qsize():
                v, dis = que.get()
                used[v] = True
                for to in links[v]:
                        if not used[to]:
                                dist[i][to] = min(dist[i][to], dis+1)
                                que.put([to, dis+1])
        for a in dist[i]:
                if a!=1e11: ans[a] += 1
for i in range(n-1): print(ans[i+1]//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, x, y = map(int, input().split())
g1 = np.zeros((n+1,n+1),dtype=np.int64)
g2 = np.zeros((n+1,n+1),dtype=np.int64)
ans = np.zeros(n+1,dtype=np.int64)
for i in range(1,n+1):
    g1[i,i:] = range(n - i + 1)

#for i in range(1,n+1):
#    print(g1[i,1:])


for i in range(1,x+1):
    g2[i,i:y+1] = range(x - i + 1 , x - 2 * i + 2 + y )[::-1]
    g2[i,y+1:] = range(x - i + 2,x - i + 2 + n - y)

for i in range(x+1,n+1):
    #print(i,i - x + 1 , i - x + 1 + n - i )
    if i+1 < y+1:
        g2[i,i+1:y+1] = range(i - x + 1 , i - x + 1 + y - i  )[::-1]
    g2[i,y+1:] = range(i - x + 2,i - x + 2 + n - y)


#for i in range(1,n+1):
#    print(g2[i,1:])

#print('aaa')
g = np.minimum(g1,g2)

#for i in range(1,n+1):
#    print(g[i,1:])

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import combinations

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

    D = dict()
    D[1] = {2}
    D[n] = {n - 1}
    for i in range(2, n):
        D[i] = {i - 1, i + 1}

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

    A = [0]*(n - 1)
    for c in combinations(range(1, n + 1), 2):
        Q = deque()
        Q.extend(D[c[0]])
        cnt = 0
        end = False
        while not end:
            cnt += 1
            Qex = set()
            while len(Q) != 0:
                e = Q.popleft()
                if e == c[1]:
                    Q.clear()
                    end = True
                    break

                Qex |= D[e]

            Q.extend(Qex)

        A[cnt - 1] += 1

    for a in A:
        print(a)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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.append(diff)

for i in range(1, n):
    print(ans.count(i))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
import collections
from sys import *
dic = collections.defaultdict(list)
for i in range(1,N):
    dic[i].append(i+1)
    dic[i+1].append(i)
dic[X].append(Y)
dic[Y].append(X)
distances = [0] * (N+1)
q = collections.deque()
for i in range(1,N+1):
    visited = [False]*(N+1)
    visited[i] = True
    distance = [0] *(N+1)
    q.append(i)
    while q:
        start= q.popleft()
        for item in dic[start]:
            if not visited[item]:
                visited[item] = True
                distance[item] = distance[start] +1
                distances[distance[item]] += 1
                q.append(item)

stdout.write("\n".join([str(x//2) for x in distances[1:-1]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
n, x, y = map(int, sys.stdin.readline().split())

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,x,y = map(int, input().split())
s = np.zeros((n,n))
t = np.zeros(n)
x = x-1
y = y-1
for i in range(0,n):
  for j in range(i,n):
    a = abs(i-x)+abs(j-y)+1
    b = abs(i-j)
    if a < b:
      t[a-1] += 1
    else:
      t[b-1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n) 

def SS(L):
    S = [0] * (len(L))
    for i, l in enumerate(L):
        S[i + 1] = S[i] + l

    return S


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

    for i in range(N):
        q = queue.Queue()
        q.put((i, 0))
        close = set()
        while not q.empty():
            s, c = q.get()
            if s in close:
                continue
            
            close.add(s)
            res[c] += 1

            if s + 1 < N and not s + 1 in close:
                q.put((s + 1, c + 1))
            if s > 0 and not s - 1 in close:
                q.put((s - 1, c + 1))
            if s == X and not Y in close:
                q.put((Y, c + 1))
            if s == Y and not X in close:
                q.put((X, c + 1))

    for r in res[1:]:
        print(r // 2)
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
dist_list = []
for i in range(1, N+1):
    for j in range(i+1, N+1):
        dist_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(dist_list.count(k))

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]*N)
USED=tuple([False]*N)
ans=[]
for i in range(N):
    cost= 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):
            """
            if (min(u,v),max(u,v)) in Es:
                d[u] = min(d[u],d[v]+1) 
            """
            d[u] = min(d[u],d[v]+cost[v][u])

    ans+=d[i:]

for i in range(N-1):
    print(ans.count(i+1))

Submission status: Time Limit Exceeded

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

    dmin = [[n]*n for _ in [0]*n]

    nlist = list(range(n))

    for i in range(n):
        for j in range(i,n):
            dmin[i][j] = j-i
            dmin[j][i] = j-i

    for i in range(x):
        for j in range(y-1,n):
            dmin[i][j] -= y-x-1
            dmin[j][i] -= y-x-1


    for i in range(n):
        for j in range(x,(x+y)//2):
            t = dmin[j][x-1]+dmin[x-1][i]
            if dmin[i][j]>t:
                dmin[i][j] = t
                dmin[j][i] = t

        for j in range((x+y)//2,y):
            t = dmin[j][y-1]+dmin[y-1][i]
            if dmin[i][j]>t:
                dmin[i][j] = t
                dmin[j][i] = t

    res = [0]*(n+1)
    for dmin_ in dmin:
        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:
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]*N)
USED=tuple([False]*N)
ans=[]
for i in range(N):
    #cost= 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):
            if (min(u,v),max(u,v)) in Es:
                d[u] = min(d[u],d[v]+1) 
            #d[u] = min(d[u],d[v]+cost[v][u])

    ans+=d[i:]

for i in range(N-1):
    print(ans.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

combi = list(itertools.combinations(range(1,N+1), 2))
dist = [[i+1, 0] for i in range(0, N-1)]

c = [min([kyori[1] - kyori[0], int(abs((kyori[1] - Y))) + 1 + int(abs((X - kyori[0])))]) for kyori in combi]

for i in range(len(c)):
    dist[c[i]-1][1] += 1
for i in range(0, N-1):
    print(dist[i][1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for i in range(N-1):
    A[i][i + 1] = 1
    A[i+1][i] = 1
A[X - 1][Y - 1] = 1
A[Y - 1][X - 1] = 1

D = [(i, j) for i in range(N) for j in range(N) if i<j]

A = np.array(A)

a = np.identity(N)
for i in range(N-1):
    r = 0
    tmp = []
    a = np.dot(a, A)
    for (i, j) in D:
        if a[i][j] > 0:
            r += 1
        else:
            tmp.append((i, j))
    D = tmp
    print(r)

Submission status: Time Limit Exceeded

Solution code:
def renew(mat, dis):
    for i in range(N):
        for j in range(i, N):
            if mat[i][j] == dis:
                if (i-1 >= 0):
                    if (mat[i-1][j] == 0):
                        mat[i-1][j] = dis+1
                if (i+1 < N):
                    if (mat[i+1][j] == 0):
                        mat[i+1][j] = dis+1
                if (j-1 >= 0):
                    if (mat[i][j-1] == 0):
                        mat[i][j-1] = dis+1
                if (j+1 < N):
                    if (mat[i][j+1] == 0):
                        mat[i][j+1] = dis+1

    return mat


def judge(mat):
    flag = 0 in mat[0][1:]
    for i in range(1, N):
        flag = flag|(0 in mat[i][i+1:])

    return flag

if __name__ == "__main__":
    N, X, Y = list(map(int, input().split()))
    d = [[0 for i in range(N)] for j in range(N)]
    for i in range(N-1):
        d[i][i+1] = 1

    d[X-1][Y-1] = 1
    for i in range(1, N):
        if judge(d):
            d = renew(d, i)
        else:
            break

    num = 0
    for j in range(1, N):
        for i in range(N):
            num += d[i][i+1:].count(j)
        print(num)
        num = 0

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
class Graph(object):
  def __init__(self):
    self.graph = defaultdict(list)

  def addEdge(self, u, v):
    self.graph[u].append(v)
    self.graph[v].append(u)

  def search(self, v, searched):
    visited = [False] * len(self.graph)

    visited[v] = True
    queue = deque([(v,0)])
    while queue:
      s,d = queue.popleft()
      k = lambda x,y: (min(x,y),max(x,y))
      s_ = [(i,d+1) for i in self.graph[s] if not visited[i] and d+1<=searched[k(v,i)]]
      queue.extend(s_)
      for i,_ in s_:
        visited[i] = True
        searched[k(v,i)] = min(searched[k(v,i)], d+1)
        
def main():
  g = Graph()
  N,X,Y = map(int, input().split())
  for i in range(N-1): g.addEdge(i,i+1)
  g.addEdge(X-1,Y-1)
  ans = defaultdict(int)
  searched = defaultdict(lambda :2*10**3)
  for i in range(N-1): g.search(i, searched)
  for v in searched.values(): ans[v] += 1
  print("\n".join([str(ans[i]) for i in range(1,N)]))
  
main()

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(i+1, N+1):
            dist = min([j-i,abs(X-i)+1+abs(j-Y),abs(Y-i)+1+abs(j-X)])
            if dist==k:
                count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections

N, X, Y = map(int, input().split())
x = X-1
y = Y-1
dist = dict()
for i in range(N-1):
    for j in range(i+1, N):
        dist_ = min(abs(j-i), abs(x-i) + 1 + abs(j-y), abs(y-i) +1 + abs(j - x))
        dist[i, j] = dist_

out = collections.Counter(dist.values())
for i in range(N-1):
    print(out[i+1])

Submission status: Time Limit Exceeded

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

dic = collections.defaultdict(list)
for i in range(1,N):
    dic[i].append(i+1)
    dic[i+1].append(i)
dic[X].append(Y)
dic[Y].append(X)
distances = [0] * (N+1)
for i in range(1,N+1):
    visited = [False]*(N+1)
    visited[i] = True
    distance = [0] *(N+1)
    q = collections.deque()
    q.append(i)
    while q:
        start= q.popleft()
        for item in dic[start]:
            if not visited[item]:
                visited[item] = True
                distance[item] = distance[start] +1
                q.append(item)
    for item in distance:
        distances[item] += 1

print("\n".join([str(int(x/2)) for x in distances[1:-1]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n) 

def SS(L):
    S = [0] * (len(L))
    for i, l in enumerate(L):
        S[i + 1] = S[i] + l

    return S


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

    for i in range(N):
        stack = [i]
        close = set()
        c = 0
        while len(stack) != 0:
            stack2 = []
            for s in stack:
                if s in close:
                    continue
                close.add(s)
                res[c] += 1
                if s + 1 < N and not s + 1 in close:
                    stack2.append(s + 1)
                if s > 0 and not s - 1 in close:
                    stack2.append(s - 1)
                if s == X and not Y in close:
                    stack2.append(Y)
                if s == Y and not X in close:
                    stack2.append(X)
            c += 1
            stack = stack2[:]

    for r in res[1:]:
        print(r // 2)
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

x = x-1
y = y-1

G = [[i-1,i+1] for i in range(n)]

G[0] = [1]
G[-1]= [n-2]

G[x].append(y)
G[y].append(x)

count_mat = [[float('inf')]*n for i in range(n)]

def bfs(ini):
    visited = set()
    visited.add(ini)
    prev_steps = [ini]
    count_mat[ini][ini] = 0
    count = 0
    next_steps = set()
    
    while len(prev_steps) != 0:
        count +=1
        for prev_step in prev_steps:#前にいたところ
            for next_step in G[prev_step]:#次にいくところ
                next_steps.add(next_step)
        next_steps = next_steps - visited#すでに訪れたところを引く
        for next_step in next_steps:
            visited.add(next_step)
            count_mat[ini][next_step] = count
            count_mat[next_step][ini] = count
        prev_steps = next_steps
        next_steps = set()
for i in range(0, n):
    bfs(i)

count_dict = {i : 0 for i in range(0, n)}
for row in count_mat:
    for k in row:
        count_dict[k] =count_dict[k]  + 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

ans = []

for i in range(n-1):
    for j in range(i+1,n):
        # ショートカットできない場合
        # print(i,j)
        if j < x:
            temp = j-i
            ans.append(temp)
        else:
            shortcut = abs((x-1) - i) + 1 + abs((y-1) -j )
            not_shortcut = j-i
            temp = min(shortcut,not_shortcut)
            ans.append(temp)
        # print(temp)

for i in range(1,n):
    print(ans.count(i))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra


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


N, X, Y = inpl()

edge = [[-1 for n in range(N)] for i in range(N)]

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

G = csgraph_from_dense(edge, null_value=-1)
ans_dict = {}
for g in dijkstra(G):
    for i in g:
        ans_dict[i] = ans_dict.get(i, 0) + 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
N,X,Y = map(int, input().split())
D = np.zeros((N,N))
for i in range(N-1):
  D[i][i+1]=1
  D[i+1][i]=1
D[X-1][Y-1]=1
D[Y-1][X-1]=1
A = floyd_warshall(D)
for k in range(1,N): print (np.sum(A==k)//2)

Submission status: Time Limit Exceeded

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

    print(N)
    for k in range(2, N):
        ans = 0
        for i in range(N):
            ans += sum(1 for j in range(i + 1, N)
                       if min(j - i, abs(i - X) + abs(j - Y) + 1) == k)
        print(ans)


main()

Submission status: Time Limit Exceeded

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

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


main()

Submission status: Time Limit Exceeded

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

result = []
for i, j in combinations(range(1, N+1), 2):
    mins = min([j-i, abs(Y-j)+abs(X-i)+1])
    result.append(mins)
print(N)
for i in range(1, N-1):
    print(result.count(i+1))

Submission status: Time Limit Exceeded

Solution code:

def debug(start, distance):
    for i in range(N):
        print("distance ", i,  end=' ')
        for j in range(N):
            if (distance[j] == i):
                print('(', start + 1, j+1, ')', end=' ')
        print()
    
def bfs(start, degrees, cd, N, cumul, res):
    distance = [2000] * N
    distance[start] = 0
    visited = [0] * N
    pile = [start]
    d = 0
    visited[start] = 1
    while (len(pile) > 0):
        node = pile.pop(0)
        d = distance[node]
        for i in range(degrees[node]):
            #print(node, cumul[node], i)
            v = cd[cumul[node] + i]
            if (d  + 1 < distance[v]):
                distance[v] = d + 1
            if (visited[v] == 0):
                visited[v] = 1
                pile.append(v)
    for i in range(start, N):
       res[distance[i]] += 1
    #debug(start, distance)





data = input().split()
N, a, b = int(data[0]), int (data[1]) - 1, int(data[2]) - 1
degrees = [2] * N 
if (b < a):
    b = a
    a = int(data[2]) - 1
degrees[N-1] = 1
degrees[0] = 1
degrees[a] += 1
degrees[b] += 1
cd = []
res = [0] * 2001
for i in range(a):
    cd.append(i+1)
    if (i > 0):
        cd.append(i - 1)
cd.append(b)
for i in range(a, b):
    cd.append(i+1)
    if (i > 0):
        cd.append(i - 1)
cd.append(a)
for i in range(b, N):
    if (i < N -1):
        cd.append(i+1)
    if (i > 0):
        cd.append(i - 1)
cumul = [0]
#print(degrees)
#print(len(cd))
for i in range(N):
    cumul.append(cumul[i] + degrees[i])
#print(cumul)
#print(cd)
for i in range(N):
    bfs(i, degrees, cd, N, cumul, res)
for i in range(1, N):
    print (res[i])

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)) 
X=X-1
Y=Y-1
ans=[]
#print()
for i in range(N):
    for j in range(i+1,N):
        if j<=X:
            dd=j-i 
        elif i<=X and j>X and j< Y:
            dd= X-i + min( j-X, 1+ Y-j)
        elif i<=X and j>=Y:
            dd=X-i+j-Y+1

        elif i>X and j<Y:
            dd=min( j-i, Y-j+i-X+1)
        elif i>X and i< Y and j>=Y:
            dd= j-Y + min( 1+i-X , Y-i)
        else:
            dd=j-i
        ans.append(dd)
        #print(i,j,dd)
#print(ans)
for i in range(N-1):
    print(ans.count(i+1))