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

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

def dijkstra_heap(s):
    #始点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

# n,w = map(int,input().split()) #n:頂点数　w:辺の数

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

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

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

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

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

Ans = [0 for _ in range(n+1)]
for i in range(1,n):
    Dist = dijkstra_heap(i)
    # print(Dist)
    for dist in Dist[i:]:
        Ans[dist] += 1

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

Submission status: 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):
        if i<=X and j<=X:
            a=j-i
            ans.append(a)
        elif Y<=i and Y<=j:
            a=j-i
            ans.append(a)
        else:
            a=j-i
            a=min(a,abs(j-Y)+abs(i-X)+1)
            ans.append(a)
for i in range(1,N):
    Ans=ans.count(i)
    print(Ans)

Submission status: Time Limit Exceeded

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(n-1):
    cost[i][i+1] = 1
    cost[i+1][i] = 1
    
cost[x-1][y-1] = 1
cost[y-1][x-1] = 1

for dis in range(1,n) :
  ans = 0
  for s in range(n) :
    ans += dijkstra(s,n,w,cost).count(dis)
  print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys

input = sys.stdin.readline
N, x, y = map(int, input().split())
dic = {}

for i in range(N + 1):
    dic[i] = []
for i in range(N - 1):
    dic[i + 1].append(i)
    dic[i].append(i + 1)
dic[x - 1].append(y - 1)
dic[y - 1].append(x - 1)
res = [0] * N

for i in range(N):
    mita_set = set()
    q = queue.Queue()
    q.put((i, 0))
    mita_set.add(i)
    while not q.empty():
        now_node, depth = q.get()
        tg_list = dic[now_node]
        res[depth] += 1
        for elem in tg_list:
            if elem not in mita_set:
                q.put((elem, depth + 1))
                mita_set.add(elem)
for i in range(1, N):
    print(res[i] // 2)

Submission status: Time Limit Exceeded

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

cost=[[float("inf") for i in range(N)] for i in range(N)]
for i in range(N-1):
  cost[i][i+1]=1
  cost[i+1][i]=1  
cost[X-1][Y-1]=1
cost[Y-1][X-1]=1
#print(cost)

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################

d=dict()
for i in range(N):
  a = dijkstra(i,N,N,cost)
  for item in a:
    if item in d: 
      d[item] += 1
    else:
      d[item] =1
#print(d)

for j in range(1,N):
  if j in d:
    print(d[j]//2)
  else:
    print(0)

Submission status: Time Limit Exceeded

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

pdic = dd(lambda:0)

# count = 0

for i in range(1,N):
    for j in range(i+1,N+1):
        
#         count += 1
        
        # no shortcut
        d1 = j-i
        # with shortcut
        i2x = abs(X-i)
        y2j = abs(Y-j)
        d2 = i2x + y2j + 1
        
        dist = min(d1,d2)
        pdic[str(dist)] += 1
        
for n in range(1,N):
    print(pdic[str(n)])
    
# print("count:",count)

Submission status: Time Limit Exceeded

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

cnt=[0 for i in range(n)]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

def solve(N, X, Y):
    INF = N + N
    X -= 1
    Y -= 1
    e = np.ones((N, N), dtype=np.int32) * INF
    for i in range(N-1):
        e[i, i+1] = 1
        e[i+1, i] = 1
    e[X, Y] = 1
    e[Y, X] = 1

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def wf(d):
    N = len(d)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                d[j][i] = min(d[j][i], d[j][k] + d[k][i])
    return d


N, x, y = map(int, input().split())
x -= 1
y -= 1
d = [[float('inf') for _ in range(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 n in range(N):
    d[n][n] = 0

d = wf(d)

cnt = {n: 0 for n in range(N)}
for i in range(N):
    for j in range(i, N):
        cnt[d[i][j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
S = [[N]*N for _ in range(N)]

for i in range(N):
    S[i][i] = 0

    if i != N-1:
        S[i][i+1] = 1
        S[i+1][i] = 1

S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for _ in range(10**3):
    for i in range(N):
        for j in range(N):
            for k in range(N):
                S[i][j] = min(S[i][j], S[i][k]+S[k][j])

#print(S)

dist = [0]*N

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

#print(dist)

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

Submission status: Time Limit Exceeded

Solution code:

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

for k in range(1,N):

    ans = 0

    for j in range(1,N+1):

        lis = {}
        lis[j-k] = 1
        lis[j+k] = 1
        lis[Y+(k-abs(j-X)-1)] = 1
        lis[Y-(k-abs(j-X)-1)] = 1
        lis[X+(k-abs(j-Y)-1)] = 1
        lis[X-(k-abs(j-Y)-1)] = 1

        #print (lis)

        for i in lis:
            
            if 1<=i<=N and min( abs(i-X)+1+abs(j-Y) , abs(i-Y)+1+abs(j-X) , abs(i-j) ) == k:
                #print (i,j)
                ans += 1

    print (ans//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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



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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop

inf = float('inf')

n, x, y = map(int, sys.stdin.readline().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)

def dijkstra(i):
    dist = [inf] * n
    dist[i] = 0
    q = [(0, i)]
    visited = set()

    while q:
        d, x = heappop(q)
        if x in visited:
            continue
        dist[x] = d
        visited.add(x)
        for y in g[x]:
            if y in visited:
                continue
            heappush(q, (d+1, y))
    return dist
    
def main():
    res = [0] * (n + 1)
    for i in range(n):
        dist = dijkstra(i)
        for d in dist:
            res[d] += 1
    for c in res[1:-1]:
        print(c // 2)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,x,y=map(int,input().split())
dp=[[abs(i-k) for k in range(N)]for i in range(N)]
dp[x-1][y-1]=1
dp[y-1][x-1]=1
for k in [x-1,y-1]:
    for i in range(N):
        for j in range(N):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j],abs(i-j))

cnt={}
for k in range(N):
    for i in range(N):
        if dp[k][i] in cnt:
            cnt[dp[k][i]]+=1
        else:
            cnt[dp[k][i]]=1

for i in range(1,N):
    try :
        print(cnt[i]//2)
    except:
        print(0)

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
import heapq


def dijkstra(n, s, edges, count):
    dist = [float('inf') for _ in range(n)]
    dist[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    while len(q):
        d, p = heapq.heappop(q)
        if s < p:
            count[d] += 1
        if dist[p] < d:
            continue
        for e in edges[p]:
            if d + 1 < dist[e]:
                dist[e] = d + 1
                heapq.heappush(q, (dist[e], e))
    return dist, count


def submit():
    n, x, y = map(int, input().split())
    
    edges = {i: [] for i in range(n)}
    for i in range(n - 1):
        edges[i].append(i + 1)
        edges[i + 1].append(i)
    edges[x - 1].append(y - 1)
    edges[y - 1].append(x - 1)
    
    dist_list = {}
    count = defaultdict(int)
    for s in range(n):
        dist_list[s], count = dijkstra(n, s, edges, count)

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


submit()

Submission status: Time Limit Exceeded

Solution code:
n,x,y = list(map(int,input().split()))
def war(d):
    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])
    return d
d = [[float("inf")]*n for i in range(n)]
for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
    d[i][i] = 0
d[x-1][y-1] = 1
d[y-1][x-1] = 1
d[n-1][n-1] = 0
ans = war(d)
#print(d)
for i in range(n-1):
    cnt = 0
    for j in range(n):
        cnt = cnt +  d[j].count(i+1)
#        print("cnt",cnt)
    print(cnt//2)

Submission status: Time Limit Exceeded

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

n, x, y = map(int, input().split())
l = np.eye(n, k=1, dtype=np.int)
l[x - 1, y - 1] = 1
out = dijkstra(l, directed=False, unweighted=True)

for i in range(1, n):
    print(np.count_nonzero(np.triu(out) == i))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

d = [[1e+10]*n for i in range(n)] 

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

d[n-1][n-1] = 0
d[X-1][Y-1] = d[Y-1][X-1] = 1

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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])
    return d

d = warshall_floyd(d)
d = [Counter(d[i]) for i in range(n)]

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

Submission status: Time Limit Exceeded

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


N, X, Y = map(lambda x: int(x), input().split(" "))

dist_matrix = [[0] * (N) for _ in range(N)]
for i in range(N-1):
    dist_matrix[i][i+1] = 1
    dist_matrix[i][i+1] = 1

dist_matrix[X-1][Y-1] = 1
dist_matrix[Y-1][X-1] = 1
graph = csr_matrix(dist_matrix)

dist_matrix = floyd_warshall(csgraph=graph, directed=False)

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

Submission status: Time Limit Exceeded

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

import itertools

#import bisect

import copy
from functools import lru_cache

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

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

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

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

    return result

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

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

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

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


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

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

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

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




if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

#N <=2*10**3
#総当たりはN*(N-1) = 4*10**6　間に合う

ans_dict = {i:0 for i in range(1,N+1)}

for i in range(1,N+1):
    for j in range(i+1,N+1):
        #print(i,j)
        #ストレートで行くパターン
        straight = j-i
        #XYを経由するパターン
        throught_XY = min(abs(X-i),abs(Y-i))+min(abs(X-j),abs(Y-j))+1
        
        distance = min(straight,throught_XY)
        
        ans_dict[distance] += 1
        
for i in range(1,N):
    print(ans_dict[i])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys

input = sys.stdin.readline
N, x, y = map(int, input().split())
dic = {}

for i in range(N + 1):
    dic[i] = []
for i in range(N - 1):
    dic[i + 1].append(i)
    dic[i].append(i + 1)
dic[x - 1].append(y - 1)
dic[y - 1].append(x - 1)
res = [0] * (N)

for i in range(N):
    mita_set = set()
    q = queue.Queue()
    q.put((i, 0))
    mita_set.add(i)
    while not q.empty():
        now_node, depth = q.get()
        tg_list = dic[now_node][:]
        res[depth] += 1
        for elem in tg_list:
            if elem not in mita_set:
                q.put((elem, depth + 1))
                mita_set.add(elem)
for i in range(1, N):
    print(res[i] // 2)

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):
        if True:
            ans.append(min(j-i, abs(i-X)+1+abs(Y-j)))
            #print(min(j-i, abs(i-X)+1+abs(Y-j)), i, j)
        elif j < Y or X < i:
            ans.append(j-i)
            #print(j-i, i, j)
        else:
            ans.append(j-i-(Y-X-1))

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

Submission status: Time Limit Exceeded

Solution code:
n, l, r = map(int, input().split())

l -= 1
r -= 1

for k in range(1, n):
    res = 0
    #print("l",l, "r",r)
    for a in range(n):
        for b in range(a+1, n):
            #print("from", a, "to", b)
            c = 9999999999
            c = min(c, b - a)
            #print(" dire", c)
            c = min(c, abs( abs(l - a) + abs(r - b) ) + 1 )
            #print(" warp", abs(l - a) + abs(r - b) +1,abs(l - a),  abs(r - b))
            if c == k:
                #print(" hit!!!!!!!!!!", k)
                res += 1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from scipy.sparse.csgraph import shortest_path
import numpy as np
N, X, Y = map(int, input().split())
edges = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    edges[i][i + 1] = 1
    edges[i + 1][i] = 1
X -= 1
Y -= 1
edges[X][Y] = 1
edges[Y][X] = 1
res = shortest_path(np.array(edges))
ans = defaultdict(int)
for i in range(N-1):
    for j in range(i+1, N):
        ans[int(res[i][j])] += 1
for k in range(1, N):
    print(ans[k])

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, X, Y = [int(x) for x in input().split()]

    ans = [0] * N
    for i in range(1, N + 1):
        s = collections.deque()
        s.append([i, 0])
        v = set()
        v.add(i)
        while s:
            c = s.popleft()
            ans[c[1]] += 1

            if c[0] == X:
                if Y not in v:
                    s.append([Y, c[1] + 1])
                    v.add(Y)
            if c[0] == Y:
                if X not in v:
                    s.append([X, c[1] + 1])
                    v.add(X)

            if c[0] != 1:
                if c[0] - 1 not in v:
                    s.append([c[0] - 1, c[1] + 1])
                    v.add(c[0] - 1)

            if c[0] != N:
                if c[0] + 1 not in v:
                    s.append([c[0] + 1, c[1] + 1])
                    v.add(c[0] + 1)

    for a in ans[1:]:
        print(a // 2)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

inf = float('inf')

n, x, y = map(int, sys.stdin.readline().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)

def bfs(i):
    dist = [inf] * n
    dist[i] = 0
    q = deque()
    q.append((i, 0))
    visited = set()

    while q:
        x, d = q.popleft()
        dist[x] = min(dist[x], d)
        visited.add(x)
        for y in g[x]:
            if y in visited:
                continue
            q.append((y, d+1))
    return dist
        

def main():
    res = [0] * (n + 1)
    for i in range(n):
        dist = bfs(i)
        for d in dist:
            res[d] += 1
    for c in res[1:-1]:
        print(c // 2)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

x = []
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i >= j:
            continue
        if i == X and Y == j:
            x.append(1)
        else:
            x.append(int(min(j - i, math.fabs(X - i) + math.fabs(Y - j) + 1)))

for i in range(1, N):
    print(x.count(i))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections

def solve(N: int, X: int, Y: int):
    d = [[100000000 for i in range(N)] for j in range(N)]
    X -= 1
    Y -= 1

    for i in range(N):
        d[i][i] = 0
        if i < 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])

    count_dict = collections.defaultdict(int)
    for row in d:
        for i in row:
            count_dict[i] += 1
    for i in range(1, N):
        print(count_dict[i]//2)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, X, Y)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
N, X, Y = map(int, input().split())
G = [[0 if i == j else INF for j in range(N)] for i in range(N)]
for i in range(N-1):
  G[i][i+1] = G[i+1][i] = 1
G[X-1][Y-1] = G[Y-1][X-1] = 1
for k in range(N):
  for i in range(N):
    for j in range(N):
      G[i][j] = min(G[i][j], G[i][k] + G[k][j])
for k in range(1, N):
  rk = 0
  for i in range(N):
    for j in range(N):
      if j <= i: continue
      if G[i][j] == k:
        rk += 1
  print(rk)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


if __name__ == "__main__":
    n, x, y = map(int, input().split())

    g1 = Graph()

    ans = [0] * (n - 1)

    for i in range(n-1):
        g1.add_edge(i, i+1)
        g1.add_edge(i+1, i)

    g1.add_edge(x-1, y-1)
    g1.add_edge(y-1, x-1)

    for i in range(n-1):
        d = Dijkstra(g1, i)
        for j in range(i+1, n):
            ans[d.dist[j]-1] += 1

    for aa in ans:
        print(aa)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import heapq

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

def warshall_floyd(n,d):
    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])
    return d





n,x,y = m()

dp = [[mod for i in range(n)] for j in range(n)]

for i in range(n):
    dp[i][i] = 0

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

dp[x-1][y-1] = 1

dp[y-1][x-1] = 1


po = dijkstra(x-1,n,n,dp)

ppo = dijkstra(y-1,n,n,dp)

ans = [0 for i in range(n)]
ppp = warshall_floyd(n,dp)
for i in range(n):
    for j in range(n):
        on = min(dp[i][j],po[i]+po[j],ppo[i]+ppo[j],po[i]+ppo[j] + 1,ppo[i]+po[j] + 1)
            #print(i,j,on)
            #print(ppp[i][j])
        ans[on] += 1
for i in range(1,n):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
INF = 10**5
d = [[INF]*n for _ in range(n)]
def wf(d):
  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])

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
wf(d)

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

for a in ans:
  print(a)