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:
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 k in range(N):
    for i in range(N):
        for j in range(N):
                S[i][j] = min(S[i][j], S[i][k]+S[k][j])
        #for k in [X-1, Y-1]:
            #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:
import itertools

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

l=list(range(1,N+1))

for k in range(1, N):
    cnt=0
    for p in itertools.combinations(l, 2):
        a=p[1]-p[0]
        b=abs(p[1]-Y)+abs(p[0]-X)+1
        if k==min(a,b):cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

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

for k in range(1, n):
    finalans=ans.count(str(k))
    print(finalans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y = [int(x) for x in input().split()]
l = [[] for i in range(n+1)]
p = []
q = []
l[1].append(2)
for i in range(2,n):
    l[i].append(i+1)
    l[i].append(i-1)
l[n].append(n-1)
l[x].append(y)
l[y].append(x)
clist = [0]*(n+1)
#ここまでで、グラフが隣接リスト表記で表される
for i in range(1,n+1):
    d = deque()
    dist = [-1]*(n+1)
    dist[i] = 0
    d.append(i)
    while True:
        v = d.popleft()
        for i in l[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
        if not d:
            break
    for j in dist:
        if j == -1:
            continue
        clist[j] += 1
for i in range(1,n):
    print((clist[i])//2)

Submission status: Time Limit Exceeded

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

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

A = np.zeros((n,n), np.int32)

for i in range(1, n):
    A[i, i-1] = 1
    A[i-1, i] = 1
A[x-1, y-1] = 1
A[y-1, x-1] = 1
dist = floyd_warshall(A, directed = False)

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.q = l
        heapq.heapify(self.q)
        return

    def push(self, n):
        heapq.heappush(self.q, n)
        return

    def pop(self):
        return heapq.heappop(self.q)


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N, X, Y = Scanner.map_int()
    X -= 1
    Y -= 1
    M = [[0 for _ in range(N)] for _ in range(N)]
    for k in range(N):
        for i in range(N):
            M[k][i] = max(0, -(k - i))
        if k >= Y:
            continue
        if k <= X:
            for i in range(Y, N):
                M[k][i] = M[k][X] + 1 + (i - Y)
            for i in range(X, Y):
                M[k][i] = min(M[k][X] + (i - X), M[k][Y] + (Y - i))
        else:
            for i in range(max(k, X), Y + 1):
                M[k][i] = min(abs(k - i), abs(X - i) + 1 +
                              abs(Y - k), abs(Y - i) + 1 + abs(X - k))
            for i in range(Y, N):
                M[k][i] = M[k][Y] + (i - Y)
    for i in range(1, N):
        ans = 0
        for m in M:
            ans += m.count(i)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

class Dijkstra():
    class Edge():
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E
    
    @property
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        import heapq
        que = []
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d

def exec(n, x, y):
    ansList = [0] * n
    V = n
    djk = Dijkstra(V)
    for m in range(n - 1):
        djk.add(m, m + 1, 1)
        djk.add(m + 1, m, 1)
    djk.add(x - 1, y - 1, 1)
    djk.add(y - 1, x - 1, 1)
    
    for m in range(n - 1):
        d = djk.shortest_path(m)
        cntList = collections.Counter(d[m:])
        for o in range(n - 1):
            ansList[o] += cntList[o]
    for i in ansList[1:]:
        print(i)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,X,Y = inputMap()
	g2 = Graph()

	for i in range(N):
		if i == 0:
			continue
		g2.add_edge(i, i-1, 1)
		g2.add_edge(i-1, i, 1)

	g2.add_edge(X-1, Y-1, 1)
	g2.add_edge(Y-1, X-1, 1)

	for i in range(1,N):
		if i == 1:
			print(N)
			continue

		ans2 = 0
		ans = []
		for ii in range(N):
			d2 = Dijkstra(g2, ii)
			for jj in range(N):
				if ii == jj:
					continue
				tmp2 = d2.shortest_distance(jj)

				if tmp2 == i:
					if (jj,ii) in ans:
						continue
					#print("{} {}".format(ii+1,jj+1))
					ans2 += 1
					ans.append((ii,jj))
		print(ans2)
		#print("{} {}".format(ans,ans2))





#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
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]

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

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

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] = 1
cost[Y-1][X-1] = 1

res = Counter()
for i in range(N):
    res += Counter(dijkstra(i, N, N, cost)[:i])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import *
nxy=input().rstrip().split(" ")
n=int(nxy[0])
x=int(nxy[1])
y=int(nxy[2])
dis=[]
for i in range(1,n):
    #print(i)
    j=i+1
    while j>i and j<=n:
        l1=abs(x-i)+1+abs(y-j)
        l2=j-i
        if l1>=l2:
            L=l2
        else:
            L=l1
        #print(L)
        dis.append(L)
        j=j+1
#print(dis)
for k in range(1,n):
    print(dis.count(k))

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict

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

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

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

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


def wf(d):
    n = len(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

nd = wf(d)

ret = defaultdict(int)

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

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

Submission status: Time Limit Exceeded

Solution code:
(N,X,Y) = map(int,input().split())
dist_1 = []
dist_all =[]
for i in range(1,N):
    dist_1.append((i,i+1))
    dist_all.append((i,i+1))
dist_1.append((X,Y))
dist_all.append((X,Y))
print(len(dist_1))
for k in range(2,N):
    if k == 2:
        pre = dist_1
    else:
        pre = dist_k
    dist_k = []
    for i in pre:
        for j in dist_1:
            if i[1] == j[0] and i[0] != j[1]:
                Candi = (i[0],j[1])
                if Candi not in dist_all:
                    dist_k.append(Candi)
                    dist_all.append(Candi)
            if i[1] == j[1] and i[0] != j[0]:
                Candi = (min(i[0],j[0]),max(i[0],j[0]))
                if Candi not in dist_all:
                    dist_k.append(Candi)
                    dist_all.append(Candi)
            if i[0] == j[0] and i[1] != j[1]:
                Candi = (min(i[1],j[1]),max(i[1],j[1]))
                if Candi not in dist_all:
                    dist_k.append(Candi)
                    dist_all.append(Candi)
    print(len(dist_k))

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
l=[]
for i in range(n-1):
  for k in range (i+1,n):
    if k<x-1 or i>y-1:
      l.append(k-i)
    else:
      l.append(min(abs(x-1-i)+abs(y-1-k)+1,k-i))
for i in range(1,n):
  print(l.count(i))

Submission status: Time Limit Exceeded

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

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[X-1][Y-1] = 1
d[Y-1][X-1] = 1

def warshall_floyd(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

wf = warshall_floyd(d)
for i in range(N):
    wf[i][i] = 0

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

#保存
import heapq
import sys
import itertools
 
sys.setrecursionlimit(10**7)

def bfs(cost,node):
    root[node]=min(root[node],cost)
    visited[node]=1
    for next_n in way[node]:
        if visited[next_n]==0:
            heapq.heappush(q,[cost+1,next_n])
    return
    
N,X,Y=map(int,input().split())
r=[i for i in range(N)]

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

for i in range(N-1):
    way[i].append(i+1)
    way[i+1].append(i)

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

#print(way)

made=[]


#print(q)
for start in r:
    root=[10**9]*N
    visited=[0]*N
    #print(root)
    q=[[0,start]]
    heapq.heapify(q)#costとnode
    while q:
        temp=heapq.heappop(q)
        #print(temp)
        #print(temp)
        if visited[temp[1]]==0:
            bfs(temp[0],temp[1])
    made.append(root)
#print(made)

ans=[0]*(N)
for item in made:
    for num in item:
        ans[num]+=1

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

"""
ans=10**9
for order in itertools.permutations([i for i in range(len(r))]):
    #print(order)
    temp=0
    for i in range(len(order)-1):
        fro=r[order[i]]
        aft=r[order[i+1]]
        #print("YES")
        #print(order[i]-1,order[i+1]-1)
        #print(root[order[i]-1][0])
        temp+=abs(made[order[i]][aft-1]-made[order[i]][fro-1])
    ans=min(ans,temp)
print(ans)
"""

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 28 20:51:45 2020

@author: naoki
"""
from collections import deque
N, X, Y = map(int,input().split())

distance_count = [0] * (N + 1)
route = [[i-1, i+1] for i in range(N+1)]

del route[-1][-1]

All_distances = [0]*N
route[X].append(Y)
route[Y].append(X)
#%%
for j in range(1,N):
    todo = deque([j])
    seen = [0 for i in range(N+1)]
    distance = [float("inf")] * (N+1)
    distance[j] = 0
    while len(todo) > 0:
        now = todo.pop()
        if now == N+1 or now == 0:
            continue
        for checking in route[now]:
            if seen[checking] < 2 and distance[checking] > distance[now] + 1:
                distance[checking] = distance[now] + 1
                todo.append(checking)
                seen[checking] += 1
            elif distance[checking] > distance[now] + 1:
                distance[checking] = distance[now] + 1
    for i in range(j,len(distance)):
        if distance[i] != float("inf"):
            All_distances[distance[i]] += 1
for i in range(1,N):
    print(All_distances[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

n, x, y = map(int, input().split())
c = [[float("inf")]*n for i in range(n)]
for i in range(n):
    c[i-1][i] = 1
    c[i][i-1] = 1
c[-1][0] = float("inf")
c[0][-1] = float("inf")
c[x-1][y-1] = 1
c[y-1][x-1] = 1

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

counter = Counter(flatten_2dim(c))
t = 0
for _, cnt in sorted(counter.items(), key=lambda x: x[0])[1:]:
    print(cnt // 2)
    t += 1
for _ in range(n-1-t):
  print(0)

Submission status: Time Limit Exceeded

Solution code:
def shortest_path(s, n, es):
    d = [float('inf')] * n

    d[s] = 0
    while True:
        update = False
        for p, q in es:
            if d[p] != float('inf') and d[q] > d[p] + 1:
                d[q] = d[p] + 1
                update = True
        if not update:
            break
    return d

n, x, y = map(int, input().split())
es = [(x - 1, y - 1), (y - 1, x - 1)]
for i in range(n - 1):
    es.append((i, i + 1))
    es.append((i + 1, i))
length = [0] * (n - 1)
for i in range(n - 1):
    a = shortest_path(i, n, es)
    for l in range(i + 1, n):
        if a[l] != float('inf') and l != 0:
            length[a[l] - 1] += 1
for l in length:
    print(l)

Submission status: Time Limit Exceeded

Solution code:
#import numpy

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

L=[[i+1 for i in range(j+1)][::-1]+[0]*(N-1-j) for j in range(N-1)]
#print(L)

for i in range(len(L)):
    L[i]=[0]+L[i]+[0]
L.append([0]*(N+2))
L.insert(0,[0]*(N+2))
L.insert(0,[0]*(N+2))

#print(L)

H=[i+1 for i in range(N-1)][::-1]
#print(L)
#print(H)

L[Y][X]=1
task=[(Y,X,1)]
while len(task)>0:
    P=task.pop()
    y,x,c=P[0],P[1],P[2]
    if y<0 or x<0 or y>N or x>N:
        continue
    if L[y+1][x]>=c+1:
        L[y+1][x]=c+1
        task.append((y+1,x,c+1))
    if L[y-1][x]>=c+1:
        L[y-1][x]=c+1
        task.append((y-1,x,c+1))
    if L[y][x+1]>=c+1:
        L[y][x+1]=c+1
        task.append((y,x+1,c+1))
    if L[y][x-1]>=c+1:
        L[y][x-1]=c+1
        task.append((y,x-1,c+1))
    #print(y,x,c)
    #print(numpy.array(L))

ans=[0 for i in range(N)]
for i in range(N+1):
    for j in range(1,N):
        ans[j]+=L[i].count(j)

ans.pop(0)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

D = [0] * (N - 1)

for i in range(1, N+1):
    for j in range(i + 1, N+1):
        K = j - i
        M = abs(X - i) + 1 + abs(Y - j)
        J = abs(Y - i) + 1 + abs(X - j)
        R = min(K, M, J)
        D[R - 1] += 1

for d in D:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
a=(y+x)/2
ans=[]
for i in range(1,n):
  for j in range(i+1,n+1):
    if j<=a:
      ans.append(j-i)
    elif i>=a:
      ans.append(j-i)
    elif i<=x and j>=a and j<=y:
      ans.append(x-i+1+y-j)
    elif i<=x and j>=y:
      ans.append(j-y+1+x-i)
    elif i>=x and j>=y and x<=a:
      ans.append(j-y+1+i-x)
    else:
      ans.append(min(j-i,y-j+i-x+1))
for i in range(1,n):
  print(ans.count(i))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,x,y = map(int,input().split())
INF = float("inf")
g = [[INF]*n for i in range(n)]
for i in range(n-1):
  g[i][i] = 0
  g[i][i+1] = 1
  g[i+1][i] = 1
g[-1][-1] = 0
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])
g = list(itertools.chain.from_iterable(g))
for i in range(1,n):
  print(g.count(i)//2)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from collections import defaultdict
inf=10**7
n,x,y=map(int,input().split())
x-=1
y-=1
dis={}
cnt=defaultdict(int)
for i,j in combinations(range(n),2):
  dis[(i,j)]=min(abs(j-i),abs(j-y)+1+abs(i-x),abs(j-x)+1+abs(i-y))
for i,j in combinations(range(n),2):
  cnt[dis[(i,j)]]+=1
for k in range(1,n):
  print(cnt[k])

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict, deque

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

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

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

def wf(d):
    n = len(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

nd = wf(d)

ret = defaultdict(int)

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, X, Y=map(int, input().split())
ans=[0 for _ in range(N)]
link=[[]]+[[2]]+[[i-1, i+1] for i in range(2, N)]+[[N-1]]
link[X].append(Y)
link[Y].append(X)

def f(p, length, moto):
  ans[length]+=1
  for data in link[p]:
    if kisyutu[data]==0:
      kisyutu[data]=1
      q.append([data, length+1, p])

for i in range(1, N+1):
  kisyutu=[1]+[0 for i in range(N)]
  kisyutu[i]=1
  q=deque()
  for data in link[i]:
    q.append([data, 1, i])
    kisyutu[data]=1
  while len(q)>0:
    data=q.popleft()
    f(data[0], data[1], data[2])
    
ans=[ans[i]//2 for i in range(N)]
print(*ans[1:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    n,x,y = map(int,input().split())
    ans = [0]*(n)
    E = [[] for i in range(n)]
    E[0].append(1)
    E[n-1].append(n-2)
    for i in range(1,n-1):
        E[i].append(i-1)
        E[i].append(i+1)
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    ans = [0]*(n)
    def search(x):
        d = [float("INF")]*n
        d[x] = 0
        q = deque([])
        q.append((x,0))
        while q:
            bef,l = q.popleft()

            for nex in E[bef]:
                if d[nex] > l+1:
                    d[nex] = l+1
                    q.append((nex,l+1))
        
        d = d[x:]
        for j in range(n):
            ans[j] += d.count(j)
    for i in range(n-1):
        search(i)

    for i in ans[1:]:
        print(i)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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] = 1
cost[Y-1][X-1] = 1

res = Counter()
for i in range(N):
    res += Counter(dijkstra(i, N, N, cost)[:i])

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

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
x-=1
y-=1
def dist(a,b):
	return min(abs(b-a),1+abs(a-x)+abs(b-y),1+abs(b-x)+abs(a-y))
#d==1
print(n)
for d in range(2,n):
	ans=0
	for i in range(n-d):
		lst=[]
		if i+d<n and dist(i,i+d)==d:
			lst.append(i+d)
		d0=d
		d0-=abs(x-i)
		d0-=1
		if d0>=0:
			if i<y-d0 and dist(i,y-d0)==d:
				lst.append(y-d0)
			if i<y+d0 and dist(i,y+d0)==d and y+d0<n:
				lst.append(y+d0)
		ans+=len(list(set(lst)))
	print(ans)

Submission status: Time Limit Exceeded

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

def clc(i1, i2):
    return min(1 + abs(i2 - y) + abs(i1 - x), i2 - i1)

for k in range(1, n+1):
    for l in range(k+1, n+1):
        tmp = clc(k, l)
        kyori.append(tmp)

for i in range(n-1):
    cnt = 0
    for k in kyori:
        if k == i + 1:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N, X, Y = map(int, input().split())
G = np.zeros((N, 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
#print(G)
spG = shortest_path(G)
for i in range(1,N):
    print(int(np.count_nonzero(spG==i)/2))

Submission status: Time Limit Exceeded

Solution code:
import heapq


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


################################
n, x, y = map(int, input().split())  #n:頂点数
w = n
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w - 1):
    edge[i + 1].append([1, i])
    edge[i].append([1, i + 1])
edge[x - 1].append([1, y - 1])
edge[y - 1].append([1, x - 1])

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

for i in range(n):
    tmp = dijkstra_heap(i)
    zero = False
    for j in tmp:
        if zero:
            dic[j] += 1
        if j == 0:
            zero = True

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python


def check(p, points, d2):
    if p in points:
        points.remove(p)
        d2.add(p)
    return points, d2


n, x, y = (int(v) for v in input().split())
x -= 1
y -= 1
c = [0] * (n - 1)
for i in range(n):
    points = set(range(n))
    d1 = {i}
    d2 = set()
    points.remove(i)
    for j in range(n - 1):
        for d in d1:
            points, d2 = check(d + 1, points, d2)
            points, d2 = check(d - 1, points, d2)
            if d == x:
                points, d2 = check(y, points, d2)
            if d == y:
                points, d2 = check(x, points, d2)

        c[j] += len(d2)
        d1 = d2
        d2 = set()
print('\n'.join([str(int(v / 2)) for v in c]))