Problem:


Score : 400 points

Problem Statement

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

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

There is an edge between Vertex X and Vertex Y.

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

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

Constraints

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

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

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

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

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

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

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

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

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,deque
def bfs(G,s,N):
    dist=[-1]*(N+1)
    d=deque()
    dist[s]=0
    d.append(s)
    while(len(d)!=0):
        v=d[0]
        d.popleft()
        for nv in G[v]:
            if(dist[nv]!=-1):
                continue
            #発見した地点への操作
            dist[nv]=dist[v]+1
            d.append(nv)
            #ここまで
    return dist

N,X,Y=map(int,input().split())
G=[[] for i in range(N+1)]
for i in range(1,N):
    G[i].append(i+1)
    G[i+1].append(i)
G[X].append(Y);G[Y].append(X)
Count=[0]*(N+1)
for i in range(1,N+1):
    li=bfs(G,i,N)
    c=Counter(li)
    for i in range(1,N+1):
        Count[i]+=c[i]
for i in range(1,N):
    print(Count[i]//2)

Submission status: Time Limit Exceeded

Solution code:
# Code for D - Line++
# Use input() to fetch data from STDIN
from collections import defaultdict
d = defaultdict(int)

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

g = [[float("inf")]*n for i in range(n)]

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

g[x-1][y-1] = 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])

d = defaultdict(int)

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        d[g[i][j]] += 1

for k in range(n - 1):
    print(int(d[k + 1] / 2))

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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 main():
  n,x,y=LI()
  
  cost = [[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

  ans=[0]*(n-1)
  for i in range(n):
    a=dijkstra(i,n,n,cost)
    for x in a[i:]:
      ans[x]+=1

  for x in ans[1:]:
    print(x)
  print(0)

main()
# print(main())

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
ans=defaultdict(int)
dists=[]
for i in range(n-1):
    a=dijkstra_heap(i)[i+1:]
    for aa in a:
        ans[aa]+=1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()


N,X,Y=map(int,input().split())
data=[[] for i in range(N+1)]
for i in range(1,N):
    a=i;b=i+1
    data[a].append(b)
    data[b].append(a)
data[X].append(Y)
data[Y].append(X)


dic=defaultdict(int)
for n in range(1,N+1):
    stack=deque([[n,0]])
    visited=set()
    while stack:
        #print(stack)
        a,m=stack.popleft()
        for p in data[a]:
            if not p in visited:
                visited.add(p)
                stack.append([p,m+1])
                if p>n:
                    dic[m+1]+=1


lst=[]
for i in range(N-1):
    print(dic[i+1])

Submission status: Time Limit Exceeded

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

d = [[float('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

x -= 1
y -= 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])

e = [0] * n

for i in range(n):
  for j in range(i):
    e[d[i][j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
5 2 4
'''

def solve(n,x,y):
	adj = [[] for i in range(n+1)]
	adj[x].append(y)
	adj[y].append(x)
	for i in range(1,n):
		adj[i].append(i+1)
		adj[i+1].append(i)
	# print(adj)
	ans = []
	d = {}
	for i in range(1,n):
		d[i] = 0
	for k in range(1,n+1):
		q = [k]
		dis = [maxsize]*(n+1)
		dis[k] = 0
		while(q):
			src = q.pop()
			for nn in adj[src]:
				if(dis[nn] > dis[src]+1):
					dis[nn] = dis[src] + 1
					q.append(nn)
		curr = 0
		# print('k:',k,dis)
		for ii in range(k+1,n+1):
			d[dis[ii]] += 1
	return d

N,X,Y = list(map(int, stdin.readline().rstrip().split()))
ans = solve(N,X,Y)
for i in range(1,N):
	print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
def resolve():
    # 最短経路問題で使われるアルゴリズムの１つ。
    # グラフ上の全ての頂点間の最短経路を探す
    # 負の閉路（辺の重みの和が負になるような閉路）がない限り、負の辺があっても使える。

    # 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
    # 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
    def warshall_floyd(v_num, e_num, dist_lst):

        # 負の閉路を持つか

        # 頂点iから頂点jへの経路と、頂点kを経由した場合の経路とを比較して
        # よりコストの合計が小さい方を配列に入れる動的計画法
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

        ans=[0]*N
        for lst in dist_lst:
            for i in range(len(lst)):
                ans[lst[i]]+=1

        for j in range(1,N):
            print(ans[j]//2)

    N,X,Y=map(int,input().split())
    # 頂点の数と辺の数
    v_num, e_num = N,N

    # 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
    # a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]

    for i in range(v_num-1):
        dist_lst[i][i+1] = 1
        dist_lst[i+1][i]=1
    dist_lst[X-1][Y-1] = 1
    dist_lst[Y-1][X-1] = 1


    for v in range(v_num):
        dist_lst[v][v] = 0

    warshall_floyd(v_num, e_num, dist_lst)





resolve()

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
import heapq


def dijkstra(n, s, edges):
    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 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


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 = {}
    for s in range(n):
        dist_list[s] = dijkstra(n, s, edges)

    count = defaultdict(int)
    for i in range(n):
        dist = dist_list[i]
        for j in range(i + 1, n):
            count[dist[j]] += 1

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


submit()

Submission status: Time Limit Exceeded

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

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

edge = [[10**9 for j 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=10**9)
d = floyd_warshall(G)
ans = []
for i in d:
  for j in i:
    ans.append(j)

for i in range(1,N):
  print(int(ans.count(i)/2))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
N, X, Y = [int(str) for str in input().strip().split()]

INF = 100000
d = [[INF] * N for _ in range(N)]

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

dists = dict()
for i in range(N):
    for j in range(i + 1, N):
        k = d[i][j]
        dists[k] = dists.get(k, 0) + 1

for k in range(1, N):
    print(dists.get(k, 0))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
import numpy as np
from scipy.sparse.csgraph import shortest_path

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

d_table = []
for i in range(N):  # 2 * 10 ** 3
    d_list = [0] * N
    if i != 0:
        d_list[i - 1] = 1
    if i != N - 1:
        d_list[i + 1] = 1
    d_table.append(d_list)

d_table[X - 1][Y - 1] = 1
d_table[Y - 1][X - 1] = 1
adj = np.array(d_table)
d_matrix = shortest_path(adj, method="FW")

counter = collections.Counter(list(d_matrix.flatten()))
ans_s = []
for k in range(1, N):  # 2 * 10 ** 3
    c = counter[float(k)]
    c = c // 2
    ans_s.append(str(c))
ans = "\n".join(ans_s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
import heapq
n,x,y = map(int,input().split())
G = [[]*n for i in range(n)]
for i in range(n-1):
  G[i].append((i+1))
  G[i+1].append(i)
x-=1;y-=1
G[x].append((y))
G[y].append((x))
# print(G)
def bfs(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    q = collections.deque()
    q.append(s)
    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] != inf:continue
            dist[v] = dist[u] + 1
            q.append(v)
    return dist
sets = [set() for i in range(n)]
for i in range(n-1):
  dist = bfs(G,i)
  for j in range(n):
    sets[dist[j]].add((min(i,j),max(i,j)))
for i in range(1,n):
  print(len(sets[i]))

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    # 最短経路問題で使われるアルゴリズムの１つ。
    # グラフ上の全ての頂点間の最短経路を探す
    # 負の閉路（辺の重みの和が負になるような閉路）がない限り、負の辺があっても使える。

    # 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
    # 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
    def warshall_floyd(v_num, e_num, dist_lst):

        # 負の閉路を持つか
        negative_cycle_flag = False

        # 頂点iから頂点jへの経路と、頂点kを経由した場合の経路とを比較して
        # よりコストの合計が小さい方を配列に入れる動的計画法
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

        for v in range(v_num):
            # dist_lstに負の数が格納されているとは、
            # グラフが負の閉路を持つことを意味する
            if dist_lst[v][v] < 0:
                negative_cycle_flag = True

        if negative_cycle_flag:
            print("NEGATIVE CYCLE")
        else:
            ans=[0]*N
            for lst in dist_lst:
                for i in range(len(lst)):
                    ans[lst[i]]+=1

            for j in range(1,N):
                print(ans[j]//2)

    N,X,Y=map(int,input().split())
    # 頂点の数と辺の数
    v_num, e_num = N,N

    # 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
    # a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]

    for i in range(v_num-1):
        dist_lst[i][i+1] = 1
        dist_lst[i+1][i]=1
    dist_lst[X-1][Y-1] = 1
    dist_lst[Y-1][X-1] = 1


    for v in range(v_num):
        dist_lst[v][v] = 0

    warshall_floyd(v_num, e_num, dist_lst)





resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import bisect
from operator import itemgetter
 
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,X,Y = IL()

dp = [[MAX_INT]*(N+1) for i in range(N+1)]
for i in range(1,N):
  dp[i][i+1] = 1
  dp[i+1][i] = 1
else:
  dp[X][Y] = 1
  dp[Y][X] = 1

ans = [0]*(N+1)
for k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      if i == j:
        dp[i][j] = 0
      else:
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#print(dp)

for i in range(1,N+1):
  for j in range(i+1,N+1):
    ans[dp[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())
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")

graph = np.zeros((N, N))
for i in range(N - 1):
    graph[i][i + 1] = 1
    graph[i + 1][i] = 1
graph[X - 1][Y - 1] = 1
graph[Y - 1][X - 1] = 1

shortest_paths = shortest_path(csr_matrix(graph), directed=False, method="D")
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    for j in range(N):
        if i != j:
            d[shortest_paths[i][j]] += 1
for i in range(N - 1):
    print(d[float(i + 1)] // 2)

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
dist = [[0] * (n+1) for _ in range(n+1)]


def calc_dist(i, j):
    return min(j-i, abs(i-x)+1+abs(j-y))
    # if j <= x or y <= i:
    #     return j - i
    # elif x < i < j < y:
    #     return min(j - i, (i - x) + 1 + (j - y))
    # elif x < i < y:
    #     return min(j - i, (i - x) + 1 + (j - y))
    # elif x < j < y:
    #     return min(j - i, (x - i) + 1 + (y - j))
    # else:
    #     print("{} {} {} {}".format(i, j, x, y))
    #     raise RuntimeError



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

for k in range(1, n):
    ans = 0
    for node in range(1, n+1):
        ans += dist[node][k]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

N, x, y = map(int, input().split())
graph = [[0 for i in range(N)] for i in range(N)]

for i in range(N-1):
    graph[i][i+1] = 1
    graph[i+1][i] = 1

graph[x-1][y-1] = 1
graph[y-1][x-1] = 1

graph = csr_matrix(graph)

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

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

for i in range(N):
    for j in range(N):
        if result[i,j]  == 0:
            continue
        ans[int(result[i, j])] = ans[int(result[i,j])] + 1

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

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)
#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 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])
    return d

d = [[float('inf')] * N for i in range(N)]

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

d = wf(d)

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

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

Submission status: Time Limit Exceeded

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

for i in range(1, n):
    for j in range(i+1, n+1):
        # calculate dist(i, j)
        dist = j - i
        dist = min(dist, abs(j - y) + abs(x - i) + 1)
        dist = min(dist, abs(j - x) + abs(y - i) + 1)
        ans[dist] += 1
print("\n".join(list(map(str, ans[1:]))))

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
D = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i,N):
        D[i][j] = j-i
D[X-1][Y-1] = 1
for i in range(N):
    for j in range(i,N):
        c,d = max(i,X-1),min(i,X-1)
        e,f = max(Y-1,j),min(j,Y-1)
        a = min(D[i][j],D[d][c]+D[f][e]+1)
        D[i][j] = a
A = [0]*(N-1)
for i in range(N):
    for j in range(i,N):
        k = D[i][j]
        if k == 0:
            continue
        A[k-1] += 1
for a in A:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = [int(i) for i in input().split()]
gp = [[float('inf')]*N for _ in range(N)]

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



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

d = warshall_floyd(gp, N)
li = [0]*(N-1)
for i in range(N):
    for j in range(i+1, N):
        li[d[i][j]-1] += 1

for i in li:
    print(i)

Submission status: Time Limit Exceeded

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

for ans in d:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




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


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N,X,Y=acinput()



dist=[[-1 for j in range(N+1) ] for i in range(N+1)]


for i in range(1,N):
    for j in range(i,N+1):
        a=np.abs(i-X)
        b=np.abs(j-Y)
        dist[i][j]=min(j-i,a+b+1)
        

res=[0]*(N+1)
for i in range(N):
    for j in range(i, N+1):
        res[dist[i][j]]+=1
        

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

Submission status: Time Limit Exceeded

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

d = []
for i in range(n):
    lst = [0 for _ in range(n)]
    temp = i+1
    umeru = 1
    while temp <= n-1:
        lst[temp] = umeru
        umeru += 1
        temp += 1
    temp = i-1
    umeru = 1
    while temp >= 0:
        lst[temp] = umeru
        umeru += 1
        temp -= 1
    d.append(lst)

d[x-1][y-1] = 1
d[y-1][x-1] = 1

lst = [x-1, y-1]
for k in lst:
    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 for _ in range(n)]
for i in range(n):
    for j in range(i+1, n):
        ans[d[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())
x,y = x-1,y-1
dist_list = []
for i in range(n-1):
    for j in range(i+1,n):
        dist1 = j-i
        dist2 = abs(i-x) +1 + abs(j-y)
        dist = min(dist1,dist2)
        dist_list.append(dist)

S = set(dist_list)
D = {}
for i in range(n):
    D[str(i+1)]=0
for i in range(len(dist_list)):
    D[str(dist_list[i])]=D[str(dist_list[i])]+1
    
for i in range(1,n):
    print(D[str(i)])

Submission status: Time Limit Exceeded

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

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

ans = [0]*(n-1)

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

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

for i in range(n):
    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:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
import heapq
n,x,y = map(int,input().split())
G = [[]*n for i in range(n)]
for i in range(n-1):
  G[i].append((i+1,1))
  G[i+1].append((i,1))
x-=1;y-=1
G[x].append((y,1))
G[y].append((x,1))
# print(G)
def disktra(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    hq=[]
    heapq.heappush(hq,(dist[s],s))
    while hq:
        cost,u =heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v,c in g[u]:
            if dist[v] <= dist[u] +c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq,(dist[v],v))
    return dist
sets = [set() for i in range(n)]
for i in range(n-1):
  dist = disktra(G,i)
  for j in range(n):
    sets[dist[j]].add((min(i,j),max(i,j)))
for i in range(1,n):
  print(len(sets[i]))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
setrecursionlimit(1000000)

# INF = float('inf')
INF = int(1e10)

def input():
    return stdin.readline()[:-1]

def dijkstra(s, n, w, cost):
    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 main():
    from builtins import int, map
    N, X, Y = map(int, input().split())

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

    counter = [0] * N
    for n in range(N):
        mat = dijkstra(n, N, N, cost)
        for v in mat[n+1:]:
            counter[v] += 1
    for v in counter[1:]:
        print(v)
        # print(*counter, end="\n")



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
N, X, Y = map(int, input().split())
X -= 1
Y -= 1

g = np.zeros((N, N), dtype=int)
a = np.arange(N - 1)
np.add.at(g, (a, a + 1), 1)
np.add.at(g, (a + 1, a), 1)
np.add.at(g, (X, Y), 1)
np.add.at(g, (Y, X), 1)
fw = floyd_warshall(g)
fw = (fw + 0.5).astype(int)
fw = np.tril(fw).ravel()
fw = fw[fw > 0]

cnt = np.bincount(fw).tolist()
ans = [0] * (N - 1)
for i, c in enumerate(cnt[1:]):
    ans[i] = c

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

N,X,Y=map(int,input().split())
E=[[] for i in range(N+1)]
for i in range(1,N):
    E[i].append(i+1)
    E[i+1].append(i)
E[X].append(Y)
E[Y].append(X)

ANS=[0]*(N+1)
from collections import deque
for i in range(1,N+1):
    Q=deque()
    Q.append(i)
    D=[-1]*(N+1)
    D[i]=0
    
    while Q:
        x=Q.popleft()
        for to in E[x]:
            if D[to]==-1:
                D[to]=D[x]+1
                Q.append(to)
                ANS[D[to]]+=1
    #print(D)
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 = 1 << 30
dis = [ [abs(i-j) if abs(i-j) < 2 else INF for i in range(N)] for j in range(N)]
dis[X-1][Y-1] = 1
dis[Y-1][X-1] = 1

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

for i in range(1, N):
  ans = 0
  for j in range(N): ans += dis[j].count(i)
  print(ans//2)

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():
    #n:辺数,w:スタート一
    n,w = map(int,input().split())

    edge = [[] for i in range(n)]
    dg = 10**7
    # edge[i]:[コスト]
    for i in range(n-1):
        x,y = map(int,input().split())
        z = 1
        x -= 1
        y -= 1
        edge[x].append(dg + y)
        edge[y].append(dg + x)
    
    s = w-1
    d = [-1]*n
    d[s] = 0

    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)

        

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        v,c = minedge%dg,minedge//dg
        if d[v] >= 0:
            continue
        d[v] = c
        for e in edge[v]:
            vNext = e%dg
            if d[vNext]:
                heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)

    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 = warshall_floyd(n,dp)

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

for i in range(n):
    for j in range(n):
        if po[i][j] >= 1:
            ans[po[i][j]] += 1
for i in range(1,n):
    print(ans[i]//2)