Problem:


Score : 400 points

Problem Statement

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

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

There is an edge between Vertex X and Vertex Y.

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

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

Constraints

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

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

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

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

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

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

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

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

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
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)
for i in range(n):
        dist = [1e5] * n
        used = [0] * n
        que = []
        heappush(que, [0, i])
        while len(que):
                dis, v = heappop(que)
                if used[v]: continue
                ans[dis] += 1
                used[v] = True
                for to in links[v]:
                        if not used[to]:
                                heappush(que, [dis+1, to])
for i in range(1, n): print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
dis = [0] * (N - 1)

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

[print(i) for i in dis]

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))

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

for k in range(1,N):
    L=0
    for i in range(N-1):
        for j in range(N-1-i):
            if A[i][j]==k:
                L+=1
    print(L)

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int, input().split())
es=[[] for _ in range(n)]
for i in range(n):
    if i<n-1:
        es[i].append([1,i+1])
    if i>0:
        es[i].append([1,i-1])
    es[x-1].append([1,y-1])
    es[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 es[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 es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

from collections import defaultdict, Counter

ans=defaultdict(int)
dists=[]
for i in range(n-1):
    a=dijkstra_heap(i)[i+1:]
    c=Counter(a)
    dists.append(c)
    
for i in range(len(dists)):
    for d in dists[i].keys():
        ans[d]+=dists[i][d]

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def get_result(data):
    N, X, Y = data
    min_dist = []
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            min_dist.append(min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)]))
    for i in range(1, N):
        print(min_dist.count(i))


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

Submission status: Time Limit Exceeded

Solution code:

n,x,y=map(int,input().split())
graph={i:{} for i in range(1,n+1)}


#graphの隣接行列表示
for i in range(1,n):
    graph[i][i+1]=1
    graph[i+1][i]=1
    
graph[x][y]=1
graph[y][x]=1

#graph表示完成
import heapq
def dijkstra(s,graph,n):
    #ｓからのグラフの最短最短距離をまとめたデータを返す
    dist=[10**20 for i in range(n+1)]
    dist[s]=0
    pq=[]
    heapq.heapify(pq)
    #全ての接点を一度優先度付きキューに挿入する
    heapq.heappush(pq,(0,s))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for point in graph[node].keys():
            w=graph[node][point]
            #nodeからpointに対して伸びる辺の長さ
            newlen=dist[node]+w
            if newlen<dist[point]:
                heapq.heappush(pq,(newlen,point))
                dist[point]=newlen

    return dist

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

for i in range(1,n+1):
    sub=dijkstra(i,graph,n)
    for j in range(1,n+1):
        dis=sub[j]
        ans_dis[dis]+=1

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

Submission status: Time Limit Exceeded

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

ans_list = [0]*(n)
for i in range(1, n+1):
    for j in range(1, n+1):
        if i>j:
            min_dis = min(abs(j-i), abs(x-i) + 1 + abs(j-y), abs(y-i)+1+abs(j-x))
            ans_list[min_dis] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, X, Y = map(int, input().split())
dist = [0] * (N + 1)
cnt = [0] * (N + 1)

INF = 10**10 + 9

# d = [[INF] * N for _ in range(N)]
d = [[abs(j - i) for j in range(N)] for i in range(N)]
d[X - 1][Y - 1] = 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)
count = np.bincount(np.array(d).flatten(), minlength=N)
count = count[1:] // 2
print(*count, sep='\n')

Submission status: Time Limit Exceeded

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

from collections import deque
INF=float("inf")
n,x,y=MI()
x-=1
y-=1
ans=[0]*n

for sv in range(n):
  dist=[INF]*n
  q=deque()
  def push(v,d):
    if dist[v]!=INF:
      return
    dist[v]=d
    q.append(v)
  push(sv,0)
  while q:
    v=q.popleft()
    d=dist[v]
    if v-1>=0:
      push(v-1,d+1)
    if v+1<n:
      push(v+1,d+1)  
    if v==x:
      push(y,d+1)
    if v==y:
      push(x,d+1)
        
  for i in range(n):
    ans[dist[i]]+=1
for i in range(n):
  ans[i]//=2
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
cnt = [0] * (N - 1)

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

for i in cnt:
	print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, X, Y = map(int, input().split())
dist = [0] * (N + 1)
cnt = [0] * (N + 1)

INF = 10**10 + 9
d = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(i, N):
        d[i][j] = j - i
        d[j][i] = j - i
d[X - 1][Y - 1] = 1
d[Y - 1][X - 1] = 1
n = N


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)
count = np.bincount(np.array(d).flatten(), minlength=N)
count = count[1:] // 2
print(*count, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def get_result(data):
    N, X, Y = data
    min_dist = []
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            min_dist.append(min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)]))
    for i in range(1, N):
        print(min_dist.count(i))


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
cnt = [0] * (N - 1)

for i in range(1, N + 1):
	for j in range(i + 1, N + 1):
		#X !! Y
		cmb = j - i
		#X -> Y
		XY = abs(X - i) + 1 + abs(Y - j)
		#X <- Y
		YX = abs(Y - i) + 1 + abs(X - j)
		cmb = min(cmb, min(XY, YX))
		cnt[cmb - 1] += 1

for i in cnt:
	print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter


def bfs(start):
    queue = deque([start])
    dist = [-1] * n
    dist[start] = 0
    while queue:
        v = queue.popleft()
        for nv in graph[v]:
            if dist[nv] != -1:
                continue
            queue.append(nv)
            dist[nv] = dist[v] + 1
    return dist


n, x, y = map(int, input().split())
# 0-indexed nodes
x -= 1
y -= 1

graph = defaultdict(set)
for i in range(n - 1):
    graph[i].add(i + 1)
    graph[i + 1].add(i)
graph[x].add(y)
graph[y].add(x)

dic = defaultdict(int)
for i in range(n):
    for k, v in Counter(bfs(i)).items():
        dic[k] += v

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, x , y = map(int, input().split())

g = [[0] * n for _ in range(n)]
for i in range(1, n):
    g[i-1][i] = 1
    g[i][i-1] = 1
g[x-1][y-1] = 1
g[y-1][x-1] = 1

from scipy.sparse.csgraph import floyd_warshall
cost = np.array(floyd_warshall(g))

for i in range(1,n):
    ans = np.count_nonzero(cost==i)
    print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, X, Y = map(int, input().split())
dist = [0] * (N + 1)
cnt = [0] * (N + 1)

INF = 10**10 + 9
d = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(i, N + 1):
        d[i][j] = j - i
        d[j][i] = j - i
d[X][Y] = 1

n = N + 1
# print('d', d)


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)
# print('d', d)

cnt = [0] * (N + 1)
for i in range(1, N + 1):
    for j in range(i, N + 1):
        cnt[d[i][j]] += 1
# print(cnt)

for i in cnt[1:-1]:
    print(i)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N, X, Y = map(int, input().split())
    ans = {i: 0 for i in range(1, N)}
    for i in range(1, N + 1):
        cost = [-1]*(N+1)
        cost[i] = 0
        d = deque([i])
        while len(d) != 0:
            v = d.popleft()
            c = cost[v]
            for j in [-1, 1]:
                vj = v + j
                if vj > 0 and vj <= N and cost[vj] == -1:
                    cost[vj] = c + 1
                    d.append(vj)
                    ans[c + 1] += 1
            if v in [X, Y]:
                vxy = X + Y - v
                if cost[vxy] == -1:
                    cost[vxy] = c + 1
                    d.append(vxy)
                    ans[c + 1] += 1
    for a in ans:
        print(ans[a]//2)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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.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)

    def dijkstra(self,v_n):
        d = [-1]*self.size
    
        temp_d = [(10**9,i)for i in range(self.size)]
        temp_d[v_n] = (0,v_n)
        prev = [-1]*self.size

        q = set(range(self.size))
        
        while len(q)>0:
            u = min([temp_d[q_i] for q_i in q])[1]
            d[u] = temp_d[u][0]
            q.discard(u)
            for v in self.neighbor[u]:
                temp = temp_d[u][0]+self.w_e[u][v]
                if temp_d[v][0]>temp:
                    temp_d[v] = temp,v
                    prev[v] = u

        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:
sel='D'

if sel=='A':
    S=input()
    if S[2]==S[3] and S[4]==S[5]:
        print('Yes')
    else:
        print('No')

if sel=='B':
    X=int(input())
    ans=0
    ans+=(X//500)*1000
    ans+=((X%500)//5)*5
    print(ans)

if sel=='C':
    K,N=map(int,input().split())
    A=[int(i) for i in input().split()]
    d=[A[0]+K-A[-1]]
    for i in range(N-1):
        d.append(A[i+1]-A[i])
    d.sort()
    print(K-d[-1])

if sel=='D':
    N,X,Y=map(int,input().split())
    cnt={}
    for k in range(1,N):
        cnt[k]=0
    for i in range(1,N):
        for j in range(i+1,N+1):
            k=j-i # まっすぐ
            k=min(k,abs(i-X)+1+abs(j-Y)) # う回路１
            k=min(k,abs(i-Y)+1+abs(X-j)) # う回路２
            cnt[k]+=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 for i in range(n)]
for i in range(n):
    for j in range(i,n):
        ans[min(abs(i-j),(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))] += 1
for i in range(1,n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import collections

# 標準入力 <int><int>
N, X, Y = map(int, input().split())

br = []

for i in range(N):
  for j in range(i + 1, N):
    l = []
    #print("(" , i+1, j+1, ")", j-i, abs(X - (i + 1)) + 1 + abs(Y - (j + 1)), abs(Y - (i + 1)) + 1 + abs(X - (j + 1)))
    l.append(j - i)
    l.append(abs(X - (i + 1)) + 1 + abs(Y - (j + 1)))
    l.append(abs(Y - (i + 1)) + 1 + abs(X - (j + 1)))
    br.append(min(l))

c = collections.Counter(br)

for k, v in c.items():
  print(v)

for _ in range(N - 1 - len(c)):
  print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, X, Y = [int(i) for i in input().split()]
X -= 1
Y -= 1
ans = [0 for i in range(N)]
INF = 1000000000
for i in range(N):
    dist = [INF for i in range(N)]
    q = deque()
    def push(v,d):
        if dist[v] != INF:
            return
        dist[v] = d
        q.append(v)
    push(i, 0)
    while len(q) != 0:
        v = q.popleft()
        d = dist[v]
        if v-1 >= 0:
            push(v-1, d+1)
        if v+1 < N:
            push(v+1, d+1)
        if v == X:
            push(Y, d+1)
        if v == Y:
            push(X,d+1)
    for j in range(N):
        ans[dist[j]] += 1
for i in range(N):
    ans[i] //= 2
print("\n".join(map(str, ans[1:])))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = [int(i) for i in input().split()]
X -= 1
Y -= 1
ans = [0 for i in range(N)]
INF = 1000000000
for i in range(N):
    dist = [INF for i in range(N)]
    q = []
    def push(v,d):
        if dist[v] != INF:
            return
        dist[v] = d
        q.append(v)
    push(i, 0)
    while len(q) != 0:
        v = q.pop(0)
        d = dist[v]
        if v-1 >= 0:
            push(v-1, d+1)
        if v+1 < N:
            push(v+1, d+1)
        if v == X:
            push(Y, d+1)
        if v == Y:
            push(X,d+1)
    for j in range(N):
        ans[dist[j]] += 1
for i in range(N):
    ans[i] //= 2
print("\n".join(map(str, ans[1:])))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class Graph:
    """
    隣接リストによる無向グラフ
    """

    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))
        self.graph[dst].append((src, weight))

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


class Dijkstra:
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: 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

        # 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
                    heappush(self.Q, (alt, v))

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


def main():
    N,x,y = map(int, readline().split())

    # グラフの構築
    E = Graph()
    for i in range(1,N):
        if i == x:
            E.add_edge(x, y)
        E.add_edge(i, i+1)
    
    # 各頂点についてダイクストラ
    count = [0]*N
    for i in range(1,N):
        D = Dijkstra(E, i)
        dist = D.shortest_distance()
        for j in range(i+1,N+1):
            k = dist[j]
            count[k] += 1

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += p[j].count(i)
    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y=map(int,input().split())
edge=[[] for _ in range(n)]
edge[x-1].append(y-1)
edge[y-1].append(x-1)
for i in range(n-1):
  edge[i].append(i+1)
  edge[i+1].append(i)
visited=[[-1]*n for _ in range(n)]
def bfs(s):
  q=deque([s])
  visited[s][s]=0
  while q:
    x=q.popleft()
    for nx in edge[x]:
      if visited[s][nx]==-1:
        visited[s][nx]=visited[s][x]+1
        q.append(nx)
for i in range(n):
  bfs(i)
ans=[0]*n
for i in range(n):
  for j in range(n):
    if i<j:
      continue
    if visited[i][j]>=1:
      ans[visited[i][j]]+=1
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

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

g = [[1000000000 if i != j else 0 for j in range(n)] for i in range(n)]
for i in range(n-1):
    for j in range(n):
        g[i][j] = abs(j-i)
        g[j][i] = abs(j-i)

x -= 1
y -= 1
g[y][x] = 1
g[x][y] = 1


for k in range(n):
    for i in range(n):
        for j in range(n):
            if g[i][j] > g[i][k] + g[k][j]:
                g[i][j] = g[i][k] + g[k][j]


ds = [0] * n

for xs in g:
    for x in xs:
        ds[x] += 1

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

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, x, y = MAP()
x -= 1; y -= 1

G = list2d(N, N, 0)
for i in range(N):
    for j in range(i+1, N):
        G[i][j] = min(j - i, abs(i - x) + abs(j - y) + 1, abs(j - x) + abs(i - y) + 1)
ans = [0] * N
for i in range(N):
    for j in range(i+1, N):
        ans[G[i][j]] += 1
[print(a) for a in ans[1:]]

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

if __name__ == '__main__':
    n,x,y = map(int, input().split())
    costList = [0]*n

    for i in range(1, n):
        for j in range(i+1, n+1):
            if j > i:
                minCost = min(abs(i-j),abs( x-i) +abs(y-j)+1,abs( y-i) +abs(x-j)+1 )
                costList[minCost] = costList[minCost]+1


    for i in range(n):
        if i >0:
            print(costList[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)]
X=X-1
Y=Y-1
Es.append((X,Y)) 
for i in range(len(Es)):
    aa,bb=Es[i]
    Es.append((bb,aa))
c=[[N+1 for _ in range(N)]for _ in range(N)]
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):
    mm=min(X,i)
    cost= c[mm:] #list(COST)
    """
    d=list(D)
    used=list(USED)[mm:]
    """
    d=[N+1]*(N-mm)
    d[max(0,(i-mm))]=0
    """
    if i==min(i,X):
        d[0]=0
    else:
        d[i-mm]=0
    """
    used=[False]*(N-mm)
    #d=d[mm:]

    while True:
        v=-1
        for u in range(len(used)):
            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-mm):
            d[u] = min(d[u],d[v]+((cost[v])[mm:])[u])
    #print(i,mm,d)
    if i!=min(i,X):
        d=d[i-mm + 1:]
    else:
        d=d[1:]
    #print(d)
    ans+=d
for i in range(N-1):
    print(ans.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
import collections
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

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

d = [[float("inf")]*n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)

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

for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
k=0

for i in range(n):
    if i==0:
        continue
    for j in range(n):
        k=k+collections.Counter(warshall_floyd(d)[j])[i]
    print(k//2)
    k=0

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

INF = 1001001001
N, X, Y = map(int, input().split())
d = [[INF]*N for _ in range(N)]
for i in range(N):
    d[i][i] = 0
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

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-1)
for i in range(N-1):
    for j in range(i+1,N):
        ans[d[i][j]-1] += 1
for i in range(N-1):
    print(ans[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)]
X=X-1
Y=Y-1
Es.append((X,Y)) 
for i in range(len(Es)):
    aa,bb=Es[i]
    Es.append((bb,aa))
c=[[N+1 for _ in range(N)]for _ in range(N)]
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):
    mm=min(X,i)
    cost= c[mm:] #list(COST)
    d=list(D)
    used=list(USED)[mm:]
    d[i]=0
    d=d[mm:]

    while True:
        v=-1
        for u in range(len(used)):
            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-mm):
            d[u] = min(d[u],d[v]+((cost[v])[mm:])[u])
    #print(i,mm,d)
    if i!=min(i,X):
        d=d[i-mm + 1:]
    else:
        d=d[1:]
    #print(d)
    ans+=d
for i in range(N-1):
    print(ans.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n,x,y = map(int, input().split())
    costList = [0]*n

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


    for i in range(n):
        if i >0:
            print(costList[i]//2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
count = [0] * (N-1)
for i in range(N):
    i += 1
    for j in range(N-i):
        j += i + 1
        if i < j:
            normal = j-i
            xtoy = abs(X-i) + 1 + abs(Y-j)
            ytox = abs(Y-i) + 1 + abs(X-j)
            minRoute = min([normal, xtoy, ytox])
            count[minRoute-1] += 1
for c in count:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,x,y = mi()
dist = y-x
import numpy as np
d = np.array([[-1]*n for i in range(n)])
br = [[] for i in range(n)]
for i in range(1,n-1):
    br[i].append(i-1)
    br[i].append(i+1)
br[0].append(1)
br[n-1].append(n-2)
br[x-1].append(y-1)
br[y-1].append(x-1)

from collections import deque
l=deque()
for i in range(n):
    l.append(i)
    d[i][i]=0
    while len(l)>0:
        nn = l.popleft()
        for j in br[nn]:
            if d[i][j] ==-1:
                l.append(j)
                d[i][j] = d[i][nn]+1

for i in range(1,n):
    print(len(d[d==i])//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
 
n, x, y = map(int, sys.stdin.readline().split())
dist = []
for i in range(n):
    dist.append([])
    for j in range(n):
        dist[i].append(abs(j - i))
 
dist[x-1][y-1] = 1
def get_dist(a,b):
    if a < b:
        return dist[a][b]
    else:
        return dist[b][a]
 
for k in range(n):
    for i in range(n-1):
        for j in range(i+1, n):
            dist[i][j] = min(dist[i][j], get_dist(i, k) + get_dist(k, j))
 
final = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1, n):
        final[dist[i][j]-1] += 1
 
for one in final:
    print(one)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout  

N,X,Y = [int(c) for c in input().split()]


res=[0]*(2*N)        
for x in range(0,N):
    for y in range(0,N):
        #print(x,y,abs(x-y),abs(abs(X-1-x)+abs(Y-1-y)+1),min(abs(x-y),abs(abs(X-1-x)+abs(Y-1-y)+1)))
        r=min(abs(x-y),abs(abs(X-1-x)+abs(Y-1-y)+1))
        res[r]=res[r]+1
        if(x>y):
            res[r]=res[r]-1


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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

# 解説を読んだ。
n, x, y = [int(x) for x in input().split()]

nodes = [i for i in range(1, n + 1)]
patterns = itertools.combinations(nodes, 2)

distannces = []
distannces_append = distannces.append
for p in patterns:
    routes = (
        abs(p[1] - p[0]),
        abs(x - p[0]) + 1 + abs(p[1] - y),
        abs(y - p[0]) + 1 + abs(p[1] - x)
    )
    distannces_append(min(routes))

c = collections.Counter(distannces)

# distannces_count = distannces.count
s = '\n'.join((str(c[k]) for k in range(1, n)))
print(s)

# 後半 TLE したのでリストの関数をオブジェクトに格納した: だめ
# collections.Counter 導入: だめ。

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
count = [0] * (N-1)
for i in range(N):
    i += 1
    for j in range(N):
        j += 1
        if i < j:
            normal = j-i
            xtoy = abs(X-i) + 1 + abs(Y-j)
            ytox = abs(Y-i) + 1 + abs(X-j)
            minRoute = min([normal, xtoy, ytox])
            count[minRoute-1] += 1
for c in count:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,x,y = map(int, input().split())
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]))