Problem:


Score : 400 points

Problem Statement

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

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

There is an edge between Vertex X and Vertex Y.

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

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

Constraints

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

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

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

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

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

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

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

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

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline

from collections import deque

N,X,Y=MI()
l = []
for i in range(N):
    if i!=0 and i!=N-1:
        n = [i-1,i+1]
    elif i==0:
        n = [1]
    else:
        n = [N-2]
    if i==X-1:
        n += [Y-1]
    if i==Y-1:
        n += [X-1]
    l.append(n)
ans = []
for i in range(N):
    dist = [-1]*N
    q=deque()
    q.append(i)
    dist[i]=0
    while q:
        u = q.popleft()
        for next in l[u]:
            if dist[next]==-1:
                dist[next]=dist[u]+1
                q.append(next)
    ans += dist
for k in range(N-1):
    print((ans.count(k+1))//2)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

to = [[] * N for i in range(N)]

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

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

ans = [0] * N

for i in range(N):
    dis = [0] * N
    dis[i] = 0
    visited = [False] * N
    q = queue.Queue()
    q.put(i)
    visited[i] = True

    while not q.empty():
        tmp_v = q.get()
        for j in to[tmp_v]:
            if not visited[j]:
                dis[j] = dis[tmp_v] + 1
                visited[j] = True
                q.put(j)

    for j in range(N):
        ans[dis[j]] += 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,x,y = map(int,input().split())
a = np.zeros(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        dist = min(j-i, abs(i-x+1)+1+abs(j-y+1), abs(i-y+1)+1+abs(j-x+1))
        a[dist-1] += 1
for ans in a:
    print(int(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = [0] * (N - 1)
for i in range(N - 1):
    for j in range(i + 1, N):
        ij = j - i
        ix = abs(i - X)
        iy = abs(i - Y)
        jx = abs(j - X)
        jy = abs(j - Y)

        minn = ij
        minn = min(minn, ix + 1 + jy)
        minn = min(minn, iy + 1 + jx)

        ans[minn - 1] += 1

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

ans = [0] * (N - 1)
for i in range(N - 1):
    minn = 9999999999
    for j in range(i + 1, N):
        ij = abs(i - j)
        ix = abs(i - X)
        iy = abs(i - Y)
        jx = abs(j - X)
        jy = abs(j - Y)

        minn = ij
        minn = min(minn, ix + 1 + jy)
        minn = min(minn, iy + 1 + jx)

        ans[minn - 1] += 1

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline

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

# dp =[[0]*(N) for _ in range(N)]
# for j in range(N-1):
#     dp[j][j+1]=1
#     dp[j+1][j]=1

# # 線がついているところ
# dp[X-1][Y-1] = 1
# dp[Y-1][X-1] = 1

# print(*dp,sep="\n")

def dist(s,g):
    if s<=X and Y<=g:
        return X-s + 1 + g-Y
    elif s==X and g==Y:
        return 1
    else:
        return min(g-s,abs(s-X)+1+abs(g-Y),abs(s-Y)+1+abs(g-X))

for k in range(1,N):
    cnt =0

    if k==1:
        print(N)
    else:
        for i in range(1,N+1):
            for j in range(i+1,N+1):
                if dist(i,j) == k:
                    cnt+=1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline

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

# dp =[[0]*(N) for _ in range(N)]
# for j in range(N-1):
#     dp[j][j+1]=1
#     dp[j+1][j]=1

# # 線がついているところ
# dp[X-1][Y-1] = 1
# dp[Y-1][X-1] = 1

# print(*dp,sep="\n")

def dist(s,g):
    if s<=X and Y<=g:
        return X-s + 1 + g-Y
    elif s==X and g==Y:
        return 1
    else:
        return min(g-s,abs(s-X)+1+abs(g-Y))

for k in range(1,N):
    cnt =0

    if k==1:
        print(N)
    else:
        for i in range(1,N+1):
            for j in range(i+1,N+1):
                if dist(i,j) == k:
                    cnt+=1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
from collections import Counter

n, x, y = list(map(int, input().split()))
graph = [[0]*n for _ in range(n)]

# 辺を張る
for i in range(n-1):
    graph[i][i+1] = 1
    graph[i+1][i] = 0
graph[x-1][y-1] = 1
graph[y-1][x-1] = 1

graph = csr_matrix(graph)

# 各点からの最短距離を求める
counter = Counter()
for i in range(n):
    dist = dijkstra(csgraph=graph, directed=False, indices=i)
    counter += Counter(dist)

# 答えを出力
for i in range(1, n):
    print(counter[i] // 2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, x, y = [int(i) for i in input().split()]
x, y = [x - 1, y - 1]

def shortest_dist(a, b):
    return min(min(abs(a - b), abs(a - x) + 1 + abs(b - y)), abs(a - x) + 2 + abs(b - x))

distance = [0] * n
for i in range(n):
    for j in range(i+1, n):
        distance[shortest_dist(i, j)] += 1

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


# abs(a - b)
# abs(a - x) + 1 + abs(b - y)
# abs(a - x) + 2 + abs(b - x) 
# ↑のうち最小

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

N, X, Y = map(int, input().split())
a = [[] for i in range(N)]
a[X - 1].append(Y - 1)
a[Y - 1].append(X - 1)
for i in range(N - 1):
	a[i].append(i + 1)
	a[i + 1].append(i)
ans = [0] * (N - 1)
for i in range(N - 1):
	b = [[0, i]]
	c = [False] * N
	d = [sys.maxsize] * N
	d[i] = 0
	while len(b):
		e = heapq.heappop(b)
		c[e[1]] = True
		for j in a[e[1]]:
			if c[j]:
				continue
			if e[0] + 1 < d[j]:
				d[j] = e[0] + 1
				heapq.heappush(b, [d[j], j])
	j = i + 1
	while j < N:
		ans[d[j] - 1] += 1
		j += 1
for i in ans:
	print(i)

Submission status: Time Limit Exceeded

Solution code:
def warshallFloyd(n,l):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                l[i][j]=min(l[i][j],l[i][k]+l[k][j])
    return l

n,x,y=map(int,input().split())
l=[[float('inf') for i in range(n)] for i in range(n)]

for i in range(n):
    l[i][i]=0
for i in range(n-1):
    l[i][i+1]=1
    l[i+1][i]=1
l[x-1][y-1]=1
l[y-1][x-1]=1

distance=warshallFloyd(n,l)

ans=[0]*n

for i in range(n-1):
    for j in range(i+1,n):
        ans[distance[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())
A = []
for i in range(N-1):
    a = i+1
    for j in range(i+1,N):
        b = j+1
        A.append(min([b-a,abs(X-a)+abs(Y-b)+1]))
for i in range(1,N):
    print(A.count(i))

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
S = [[0 for j in range(N)] for i in range(N)]
A = []
for i in range(N-1):
    a = i+1
    for j in range(i+1,N):
        b = j+1
        S[i][j] = min([b-a,abs(X-a)+abs(Y-b)+1])
for i in range(N-1):
    for j in range(i+1,N):
        A.append(S[i][j])
for i in range(1,N):
    print(A.count(i))

Submission status: Time Limit Exceeded

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

x -= 1
y -= 1

ans = [0] * n


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

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

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
for k in range(1,N):
    S = 0
    for i in range(1,N):
        for j in range(i+1,N+1):
            if min(j-i,abs(X-i)+abs(Y-j)+1,abs(X-j)+abs(Y-i)+1) == k:
                S += 1
    print(S)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
for k in range(1,N):
    S = 0
    for i in range(1,N):
        for j in range(i+1,N+1):
            if min(j-i,abs(X-i)+abs(Y-j)+1) == k:
                S += 1
    print(S)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
for k in range(1,N):
    S = 0
    for i in range(1,N):
        for j in range(i+1,N+1):
            A = abs(X-i)+abs(Y-j)+1
            if j-i <= A:
                if j-i == k:
                    S += 1
            else:
                if A == k:
                    S += 1
    print(S)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
for k in range(1,N):
    S = 0
    for i in range(1,N):
        for j in range(i+1,N+1):
            if j-i <= abs(X-i)+abs(Y-j)+1:
                if j-i == k:
                    S += 1
            else:
                if abs(X-i)+abs(Y-j)+1 == k:
                    S += 1
    print(S)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
for k in range(1,N):
    S = 0
    for i in range(1,N):
        for j in range(i+1,N+1):
            if (i<= X and j<=X) or (i>=Y and j>=Y):
                if j-i == k:
                    S += 1
            elif i <= X and j >= Y:
                if j-i+X-Y+1 == k:
                    S += 1
            elif i > X and j < Y:
                if j-i <= Y-j+i-X+1:
                    if j-i == k:
                        S += 1
                else:
                    if Y-j+i-X+1 == k:
                        S += 1
            elif i <= X:
                if j-i <= X+Y-i-j+1:
                    if j-i == k:
                        S += 1
                else:
                    if X+Y-i-j+1 == k:
                        S += 1
            else:
                if j-i <= -X-Y+i+j+1:
                    if j-i == k:
                        S += 1
                else:
                    if -X-Y+i+j+1 == k:
                        S += 1
    print(S)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
for k in range(1,N):
    S = 0
    for i in range(1,N):
        for j in range(i+1,N+1):
            if (i<= X and j<=X) or (i>=Y and j>=Y):
                if j-i == k:
                    S += 1
            elif i <= X and j >= Y:
                if j-i+X-Y+1 == k:
                    S += 1
            elif i >= X and j <= Y:
                if j-i <= Y-j+i-X+1:
                    if j-i == k:
                        S += 1
                else:
                    if Y-j+i-X+1 == k:
                        S += 1
            elif i <= X and X <= j <= Y:
                if j-i <= X+Y-i-j+1:
                    if j-i == k:
                        S += 1
                else:
                    if X+Y-i-j+1 == k:
                        S += 1
            elif j >= Y and X <= i <= Y:
                if j-i <= -X-Y+i+j+1:
                    if j-i == k:
                        S += 1
                else:
                    if -X-Y+i+j+1 == k:
                        S += 1
            else:
                print(i,j,k)
    print(S)

Submission status: Time Limit Exceeded

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

G=[[] for i in range(N)]
num=[0]*(N-1)

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

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

from collections import deque
from copy import deepcopy
def BFS(a,b):
    d=deque([])
    d.append([a,[0]*N])
    while d:
        x,c=d.popleft()
        chk=deepcopy(c)
        chk[x]=1
        for i in G[x]:
            if chk[i]==1:continue
            if i==b:
                ans=chk.count(1)
                return ans
            else:
                d.append([i,chk])

for i in range(N-1):
    for j in range(i+1,N):
        n=BFS(i,j)
        num[n-1]+=1

for a in num:
    print(a)

Submission status: Time Limit Exceeded

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

import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,x,y = na()
ans = [0]*(n-1)

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

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

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split(sep=" "))
root = []
X = X-1
Y = Y-1
for i in range(0,N,1):
    for j in range(i+1,N,1):
        if j - i < abs(i-X)+abs(j-Y)+1:
            root.append(j-i)
        else:
            root.append(abs(i-X)+abs(j-Y)+1)
for k in range(1,N,1):
    print(root.count(k))
    root.count(k)

Submission status: Time Limit Exceeded

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

dist = [0]*5000

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

inf = np.iinfo(np.uint32).max



def solve():
    dists_y = [abs(y-a) for a in range(0,n+1)]
    dists_x = [abs(x-a) for a in range(0,n+1)]
    count_dists = np.zeros(n+1, dtype=int)
    for a in range(1,n+1):
        for b in range(1,a+1):
            dis = min(abs(b-a), dists_x[a] + dists_y[b] + 1, dists_y[a] + dists_x[b] + 1)
            count_dists[dis] += 1
    #print(min_dists)
    for j in range(1,n):
        print(count_dists[j])


#
# def ceildiv(a, b):
#     return a // b + a % b



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

# import time
# t = time.time()
# n, x, y = 2000, 600, 1200


solve()
#print(time.time()- t)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
inf = np.iinfo(np.uint32).max

# def solve():
#     dxy = abs(x - y)
#     for j in range(3, n+1):
#         ans = max(n - dxy - j + 1, 0) # 0 -> XY -> N
#         print(ans)
#         if j*2 <= dxy + 1:
#             ans += dxy + 1
#         print(ans)
#         for bit1 in [x-1, n-y]:
#             bit2 = ceildiv(dxy - 1, 2)
#             print(j, bit1, bit2)
#             ans += max(min(j - 1, bit1, bit2) , 0)
#             ans += max(min(j - 2, bit1, bit2) , 0)
#         print(ans)
#         if j==1:
#             ans-=1
#         exit()
#         print(j, ans)

def solve():
    count_dists = np.zeros(n+1, dtype=int)
    for a in range(1,n+1):
        for b in range(1,a+1):
            dis = min(abs(b-a), abs(x-a)+ abs(y-b) + 1, abs(y-a) + abs(x-b) + 1)
            count_dists[dis] += 1
    #print(min_dists)
    for j in range(1,n):
        print(count_dists[j])


#
# def ceildiv(a, b):
#     return a // b + a % b




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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
inf = np.iinfo(np.uint32).max

# def solve():
#     dxy = abs(x - y)
#     for j in range(3, n+1):
#         ans = max(n - dxy - j + 1, 0) # 0 -> XY -> N
#         print(ans)
#         if j*2 <= dxy + 1:
#             ans += dxy + 1
#         print(ans)
#         for bit1 in [x-1, n-y]:
#             bit2 = ceildiv(dxy - 1, 2)
#             print(j, bit1, bit2)
#             ans += max(min(j - 1, bit1, bit2) , 0)
#             ans += max(min(j - 2, bit1, bit2) , 0)
#         print(ans)
#         if j==1:
#             ans-=1
#         exit()
#         print(j, ans)

def solve():
    min_dists = np.full((n, n), inf)
    count_dists = np.zeros(n+1, dtype=int)
    for a in range(1,n+1):
        for b in range(1,n+1):
            dis = min(abs(b-a), abs(x-a)+ abs(y-b) + 1, abs(y-a) + abs(x-b) + 1)
            min_dists[a-1,b-1] = dis
            count_dists[dis] += 1
    #print(min_dists)
    for j in range(1,n):
        print(count_dists[j]//2)



def ceildiv(a, b):
    return a // b + a % b




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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def exp(k, i, i0, d, leng, r, cnt=0, pre=[]):
  if i < 0 or i >= leng:
    return 0
  if i in pre:
    return 0
  pre.append(i)
  if cnt == k:
    for j in range(k):
      if {i0, i} in d[j+1]:
        return 0
    d[k].append({i0, i})
    return 0
  cnt += 1
  if r[i] != 0:
    return exp(k, r[i], i0, d, leng, r, cnt, pre) + exp(k, i-1, i0, d, leng, r, cnt, pre) \
    + exp(k, i+1, i0, d, leng, r, cnt, pre)
  else:
    return exp(k, i-1, i0, d, leng, r, cnt, pre) + exp(k, i+1, i0, d, leng, r, cnt, pre)

r = [0]*N
for i in range(N):
  if i == X-1:
    r[i] = Y-1
  if i == Y-1:
    r[i] = X-1

d = {}
for i in range(1, N):
  d[i] = []

for i in range(1, N):
  for j in range(N):
    exp(i, j, j, d, N, r, pre=[])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
ans = [0] * N
def BFS(s):
	cnt = [0] * (N+1)
	flg = [-1] * (N+1)
	flg[s] = 0
	q = deque([s])
	while q:
		cp = q.popleft()
		for d in [-1,1]:
			tmp = cp + d
			if (0 <= tmp < N) and (flg[tmp] == -1):
				flg[tmp] = flg[cp] + 1
				ans[flg[tmp]] += 1
				q.append(tmp)
		if cp == X:
			if flg[Y] == -1:
				flg[Y] = flg[cp] + 1
				ans[flg[Y]] += 1
				q.append(Y)
		if cp == Y:
			if flg[X] == -1:
				flg[X] = flg[cp] + 1
				ans[flg[X]] += 1
				q.append(X)
	return cnt

for i in range(N):
	C = BFS(i)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
def BFS(s):
	cnt = [0] * (N+1)
	flg = [-1] * (N+1)
	flg[s] = 0
	q = deque([s])
	while q:
		cp = q.popleft()
		for d in [-1,1]:
			if (0 <= cp + d < N) and (flg[cp + d] == -1):
				flg[cp + d] = flg[cp] + 1
				cnt[flg[cp+d]] += 1
				q.append(cp + d)
		if cp == X:
			if flg[Y] == -1:
				flg[Y] = flg[cp] + 1
				cnt[flg[Y]] += 1
				q.append(Y)
		if cp == Y:
			if flg[X] == -1:
				flg[X] = flg[cp] + 1
				cnt[flg[X]] += 1
				q.append(X)
	return cnt
ans = [0] * (N)
for i in range(N):
	C = BFS(i)
	for j in range(1,N):
		ans[j] += C[j]

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import math
n, x, y = map(int,input().split())
num = [0 for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        num[min([j-i,int(math.fabs(j-y+1))+1+int(math.fabs(i-x+1))])] += 1

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

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
x = x - 1
y = y - 1
dist = [float('inf')]*n
queue = []
def push(v, d):
    if dist[v] == float('inf'):
        dist[v] = d
        queue.append(v)
ans = [0]*n 
for i in range(n):
    push(i, 0)
    while len(queue) > 0:
        v = queue.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
    dist = [float('inf')]*n
ans = list(map(lambda x: x//2, ans))
print('\n'.join(map(str, ans[1:])))

Submission status: Time Limit Exceeded

Solution code:
import queue
n, x, y = input().split()
n = int(n)
x = int(x)
y = int(y)
l = [[[] for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
    if i == 1: l[i] = [i + 1]
    elif i == n: l[i] = [i - 1]
    else : l[i] = [i - 1, i + 1]
    if i == x: l[i].append(y)
    elif i == y: l[i].append(x)

dis = [[3000 for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
    q = queue.Queue()
    q.put(i)
    visited = [False] * (n + 1)
    visited[i] = True
    dis[i][i] = 0
    while q.empty() == False:
        x = q.get()
        for j in l[x]:
            if visited[j] == False:
                q.put(j)
                visited[j] = True
                dis[i][j] = min(dis[i][j], dis[i][x] + 1)

ans = [0] * (n + 1)
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if dis[i][j] >= n: continue
        ans[dis[i][j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import queue
n, x, y = input().split()
n = int(n)
x = int(x)
y = int(y)
l = [[[] for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
    if i == 1: l[i] = [i + 1]
    elif i == n: l[i] = [i - 1]
    else : l[i] = [i - 1, i + 1]
    if i == x: l[i].append(y)
    elif i == y: l[i].append(x)

dis = [[1000 for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
    q = queue.Queue()
    q.put(i)
    visited = [False] * (n + 1)
    visited[i] = True
    dis[i][i] = 0
    while q.empty() == False:
        x = q.get()
        for j in l[x]:
            if visited[j] == False:
                q.put(j)
                visited[j] = True
                dis[i][j] = min(dis[i][j], dis[i][x] + 1)

ans = [0] * (n + 1)
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if dis[i][j] >= n: continue
        ans[dis[i][j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
N, X, Y = list(map(int, input().split()))

distance_lis = [0]*(N-1)
for i in range(1, N + 1):
    for j in range(i+1, N + 1):
        # XYを使わない場合
        a = j - i
        b = np.abs(X - i) + np.abs(Y - j) + 1
        distance = min(a, b)
        distance_lis[distance-1] += 1
for dis in distance_lis:
    print(dis)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
N, X, Y = list(map(int, input().split()))

distance_lis = np.zeros(N-1, dtype=np.int32)
for i in range(1, N + 1):
    for j in range(i+1, N + 1):
        # XYを使わない場合
        a = j - i
        b = np.abs(X - i) + np.abs(Y - j) + 1
        distance = min(a, b)
        distance_lis[distance-1] += 1
for dis in distance_lis:
    print(dis)

Submission status: Time Limit Exceeded

Solution code:
# Problem D - Line++

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

# initialization
graph = [[float('INF')]*(N+1) for i in range(N+1)]
for i in range(1, N):
    graph[i][i+1] = 1
graph[X][Y] = 1
kyori = [0]*N

# dp
for i in range(1, N):
    for j in range(i+1, N+1):
        if j<=X:
            graph[i][j] = min(graph[i][j], abs(j - i))
        else:
            graph[i][j] = min(graph[i][j], abs(j - i), abs(X - i)+1+abs(j - Y))

# kyori count
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if not graph[i][j]==float('INF'):
            kyori[graph[i][j]] += 1

# output
for i in range(1, N):
    print(kyori[i])

Submission status: Time Limit Exceeded

Solution code:
import queue
N,X,Y=map(int,input().split())
X -= 1
Y -= 1
INF = 1001001001
ans=[0]*N
def push(v, d):
  if dist[v]!= INF:
    return
  dist[v]=d
  q.put(v)

for sv in range(N):
  q=queue.Queue()
  dist=[INF]*N
  push(sv,0)
  while(not q.empty()):
    v=q.get()
    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(1,N):
  print(int(ans[i]/2))

Submission status: Time Limit Exceeded

Solution code:
import queue


n,x,y = map(int, input().split())
INF = 10**4
road = {i:[i-1,i+1] for i in range(n)}
road[n-1].pop()
road[0].pop(0)
road[x-1].append(y-1)
road[y-1].append(x-1)
ans = [0 for i in range(n-1)]
for i in range(0,n):
    res = [INF if t!=i else 0 for t in range(n)]
    s = queue.Queue()
    s.put(i)
    check = set()
    while not s.empty():
        a = s.get()
        for j in road[a]:
            res[j] = min(res[a]+1,res[j])
            if not j in check:
                s.put(j)
                check.add(j)
    for j in range(i,n):
        if res[j] != 0:
            ans[res[j]-1] += 1           

[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
import queue


n,x,y = map(int, input().split())
INF = 10**4
road = {i:[i-1,i+1] for i in range(n)}
road[n-1].pop()
road[0].pop(0)
road[x-1].append(y-1)
res = [[INF if t!=i else 0 for t in range(n)] for i in range(n)]
ans = [0 for i in range(n-1)]
for i in range(0,n):
    s = queue.Queue()
    s.put(i)
    check = set()
    while not s.empty():
        a = s.get()
        for j in road[a]:
            res[i][j] = res[j][i] = min(res[i][a]+1,res[i][j])
            if not j in check:
                s.put(j)
                check.add(j)
    for j in res[i]:
        if j != 0:
           ans[j-1] += 1

[print(i//2) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
import queue


n,x,y = map(int, input().split())
INF = 10**4
road = {i:[i-1,i+1] for i in range(n)}
road[n-1].pop()
road[0].pop(0)
road[x-1].append(y-1)
res = [[INF if t!=i else 0 for t in range(n)] for i in range(n)]
ans = [0 for i in range(n-1)]
for i in range(0,n-1):
    s = queue.Queue()
    s.put(i)
    check = set()
    while not s.empty():
        a = s.get()
        for j in road[a]:
            res[i][j] = res[j][i] = min(res[i][a]+1,res[i][j])
            if not j in check:
                s.put(j)
                check.add(j)

for i in res:
    for j in i:
        if j != 0:
           ans[j-1] += 1

[print(i//2) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
#定数
#3≦n≦2*10^3
n, x, y = map(int, input().split())

#答えの計算
A = [0 for i in range(n)]   #Answers
for i in range(n):  #O(n)
    Q = deque([i])  #Queue BFSのためのもの
    #Record 位置iからの距離を記録
    R = [-1 for i in range(n)]  
    R[i] = 0
    #BFS O(n)
    while len(Q) != 0:
        t = Q[0]    #target
        d = R[t]    #distance(target)
        Q.popleft()
        #Queueに値を入れるとともに距離を更新する
        def push_and_record(t:int, d:int):
            if R[t] < 0:
                R[t] = d
                Q.append(t)
            else:
                pass
        #+方向
        if t < n-1:
            push_and_record(t+1, d+1)
        else:
            pass
        #-方向
        if t > 0:
            push_and_record(t-1, d+1)
        else: 
            pass
        #xとy
        if t == x-1:
            push_and_record(y-1, d+1)
        elif t == y-1:
            push_and_record(x-1, d+1)
        else:
            pass
    #Ansに距離の結果を入れる
    for i in range(n):
        A[R[i]] += 1

#答えの出力
for i in range(1, n):
    print(A[i] // 2)    #組み合わせ