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 numpy as np


# input the data
n, X, Y = (int(x) for x in input().split())
edge = [1 for e in range(n)]


# create a matrix to decide each distance between Vs
table1 = np.array([5000 for ij in range((n-1) * n)])
table2 = np.array([5000 for ij in range((n-1) * n)])
table3 = np.array([5000 for ij in range((n-1) * n)])

distance = table1.reshape(((n-1), n))
prepare_distance = table2.reshape(((n-1), n))
secret_distance = table3.reshape(((n-1), n))

# renew the value by X, Y
# traunsform X, Y into index
x = X - 1
y = Y - 1
# between X, Y
secret_distance[x][y] = 1
# input all of distances
# between i, j
count = 0
for k in range(n):
    if k > 0:
        print(count)
        count = 0
    for i in range(n-1):
        for j in range(i+1, n):
            prepare_distance[i][j] = np.sum(edge[i:j])
            secret_distance[i][j] = 1 + abs(x-i) + abs(y-j)
            if prepare_distance[i][j] < secret_distance[i][j]:
                distance[i][j] = prepare_distance[i][j]
            else:
                distance[i][j] = secret_distance[i][j]
            # count ans
            if distance[i][j] == k + 1:
                count += 1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


# input the data
n, X, Y = (int(x) for x in input().split())
edge = [1 for e in range(n)]


# create a matrix to decide each distance between Vs
table1 = np.array([5000 for ij in range((n-1) * n)])
table2 = np.array([5000 for ij in range((n-1) * n)])
table3 = np.array([5000 for ij in range((n-1) * n)])

distance = table1.reshape(((n-1), n))
prepare_distance = table2.reshape(((n-1), n))
secret_distance = table3.reshape(((n-1), n))

# renew the value by X, Y
# traunsform X, Y into index
x = X - 1
y = Y - 1
# between X, Y
secret_distance[x][y] = 1
for p in range(n-1):
    for q in range(p+1, n):
        secret_distance[p][q] = 1 + abs(x-p) + abs(y-q)

# input all of distances
# between i, j
for i in range(n-1):
    for j in range(i+1, n):
        prepare_distance[i][j] = np.sum(edge[i:j])

# choose the smaller value
compare = prepare_distance < secret_distance
for i in range(n-1):
    for j in range(n):
        if compare[i][j] == True:
            distance[i][j] = prepare_distance[i][j]
        else:
            distance[i][j] = secret_distance[i][j]

# show results
count = 0
for k in range(n):
    if k > 0:
        print(count)
    count = 0
    for i in range(n-1):
        for j in range(n):
            if distance[i][j] == k + 1:
                count += 1

Submission status: Time Limit Exceeded

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

ans = defaultdict(int)
for i, j in combinations(range(1,N+1),2):
    d = min(abs(i-j),abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
    ans[d] += 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 s in range(1, n): #start
    for g in range(s+1, n+1): #goal
        a.append(min(g-s, abs(x-s)+1+abs(g-y), abs(y-s)+1+abs(g-x)))

#print(a)
for i in range(1, n):
    print(a.count(i))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def count(k, n):
  counter = 0
  for i in range(1, n):
    for j in range(i+1, n+1):
      if k == min(abs(j - i),abs(x - i)+1+abs(j - y),abs(y - i)+1+abs(j - x)):
        counter += 1
  return counter

def main():
  for k in range(1, n):
    print(count(k, n))
    
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def distance(i,j,x,y):
    return min(j-i,abs(x-i)+abs(y-j)+1,abs(y-i)+abs(x-j)+1)


n,x,y=map(int,input().split())
for k in range(1,n):
    ans=0
    for i in range(1,n+1):
        for j in range(i,n+1):
            if distance(i,j,x,y)==k:
                ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
ans = []
for i in range(1, N+1):
    for j in range(i+1, N+1):
        # 使わない場合
        a = abs(j - i)
        # 使う場合
        b = abs(i - X) + abs(j - Y) + 1
        ans.append(min(a, b))
for i in range(1, N):
    print(ans.count(i))

Submission status: Time Limit Exceeded

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

for i in range(1,n+1):
    for j in range(i+1,n+1):
        dist.append(min(j-i,abs(j-y)+1+abs(i-x)))
for i in range(1,n):
    print(dist.count(i))

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = (int(i) for i in input().split())


NUM = [0] * (N-1)

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


for i in range(len(NUM)):
    print(NUM[i])

Submission status: Time Limit Exceeded

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

l = [0 for _ in range(N)]
line = []

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
n, x, y = map(int, input().split())
x -= 1
y -= 1
edges = [[] for _ in range(n)]
edges[x].append(y)
edges[y].append(x)
for i in range(n-1):
    edges[i].append(i+1)
    edges[i+1].append(i)


def bfs(init_v):
    queue = deque([init_v])
    INF = 10**10
    dist = [INF]*n
    dist[init_v] = 0
    while queue:
        v = queue.popleft()
        for v2 in edges[v]:
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            dd[dist[v2]] += 1
            queue.append(v2)


dd = defaultdict(int)
for i in range(n):
    bfs(i)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
n, x, y = map(int, input().split())
x -= 1
y -= 1
edges = [[] for _ in range(n)]
edges[x].append(y)
edges[y].append(x)
for i in range(n-1):
    edges[i].append(i+1)
    edges[i+1].append(i)


def bfs(init_v):
    queue = deque([init_v])
    INF = 10**10
    dist = [INF]*n
    dist[init_v] = 0
    while queue:
        v = queue.popleft()
        for v2 in edges[v]:
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            queue.append(v2)
    return dist


dd = defaultdict(int)
for i in range(n):
    sp = bfs(i)
    for x in sp:
        dd[x] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import queue

def push(n, dist, dist_list):
	if dist_list[n] > dist:
		dist_list[n] = dist
		q.put(n)



q = queue.Queue()
n, x, y = [int(i) for i in input().split()]
result = [0] * (n-1)

for p in range(n):
	dist_list = [111111] * n
	dist = 0
	q.put(p)
	dist_list[p] = dist 
	while not q.empty():
		p = q.get()
		dist = dist_list[p]
		if p+1 < n: push(p+1, dist+1, dist_list)
		if p-1 >= 0: push(p-1, dist+1, dist_list)
		if p == (x-1): push(y-1, dist+1, dist_list)
		if p == (y-1): push(x-1, dist+1, dist_list)
	
	for i in dist_list:
		if i != 0:
			result[i-1] += 1

for ans in result:
	print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import queue

def push(n, dist, dist_list):
	if dist_list[n] > dist:
		dist_list[n] = dist
		q.put(n)



q = queue.Queue()
n, x, y = [int(i) for i in input().split()]
result = [0] * (n-1)

for p in range(n):
	dist_list = [111111111111] * n
	dist = 0
	q.put(p)
	dist_list[p] = dist 
	while not q.empty():
		p = q.get()
		dist = dist_list[p]
		if p+1 < n: push(p+1, dist+1, dist_list)
		if p-1 >= 0: push(p-1, dist+1, dist_list)
		if p == (x-1): push(y-1, dist+1, dist_list)
		if p == (y-1): push(x-1, dist+1, dist_list)
	
	for i in dist_list:
		if i != 0:
			result[i-1] += 1

for ans in result:
	print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
def bfs(linkL, chckL, presN):
    chckL[presN] = 0
    nextNL = linkL[presN]
    breath = 1
    for item in nextNL:
        chckL[item] = breath
    
    breath = 2

    while(len(nextNL)!=0):
        tmpNextNL = []
        for item in nextNL:
            for chckItem in linkL[item]:
                if chckL[chckItem] == -1:
                    tmpNextNL.append(chckItem)
                    chckL[chckItem] = breath
        
        breath += 1
        nextNL = tmpNextNL
    
    return chckL


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

lList = []

for indx in range(N):
    tmpList = []
    if indx != 0:   tmpList.append(indx-1)
    if indx != N-1: tmpList.append(indx+1)
    if indx == X-1: tmpList.append(Y-1)
    if indx == Y-1: tmpList.append(X-1)
    lList.append(tmpList)

mySum = [0] * (N-1)

for baseIndx in range(N):
    chckList = [-1] * N

    chckList = bfs(lList, chckList, baseIndx)
    chckList = chckList[baseIndx+1:N]

    for sumIndx in range(N-1):
        mySum[sumIndx] += chckList.count(sumIndx+1)

for printIndx in range(N-1):
    print(mySum[printIndx])

Submission status: Time Limit Exceeded

Solution code:
def bfs(linkL, chckL, presN):
    nextNL = linkL[presN]
    breath = 1
    while(len(nextNL)!=0):
        for item in nextNL:
            chckL[item] = breath

        tmpNextNL = []
        for nextItem in nextNL:
            for chckItem in linkL[nextItem]:
                if chckL[chckItem] == -1:
                    tmpNextNL.append(chckItem)
                    chckL[chckItem] = -2
        
        breath += 1
        nextNL = tmpNextNL
    
    return chckL


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

lList = []

for indx in range(N):
    tmpList = []
    if indx != 0:   tmpList.append(indx-1)
    if indx != N-1: tmpList.append(indx+1)
    if indx == X-1: tmpList.append(Y-1)
    if indx == Y-1: tmpList.append(X-1)
    lList.append(tmpList)

mySum = [0] * (N-1)

for baseIndx in range(N):
    chckList = [-1] * N

    chckList[baseIndx] = 0

    chckList = bfs(lList, chckList, baseIndx)
    chckList = chckList[baseIndx+1:N]

    for sumIndx in range(N-1):
        mySum[sumIndx] += chckList.count(sumIndx+1)

for printIndx in range(N-1):
    print(mySum[printIndx])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
DATA = """
10 4 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N, X, Y = [int(i) for i in get_line().strip().split(" ")]
X-=1
Y-=1
INF = 10 * 20
m = [[0] * N for _ in range(N)]
tt = [0] * N

#print(ret)
#print(len(ret))

for r in range(N):
	for c in range(r+1, N):
		m[r][c] = c - r
		#m[c][r] = m[r][c]
		tt[m[r][c]] += 1
		m[c][r] = m[r][c]

def Set(r, c, v):
	tt[m[r][c]] -= 1
	m[r][c] = v
	tt[m[r][c]] += 1

for r in range(N):
	if m[r][X] < m[r][Y]:
		Set(r, Y, m[r][X]+1)
	for c in range(Y+1, N):
		if m[r][c] <= m[r][c-1]:
			break
		Set(r, c, m[r][c-1]+1)
	for c in range(Y-1, X, -1):
		if m[r][c] <= m[r][c+1]:
			break
		Set(r,c, m[r][c+1]+1)

for t in tt[1:]:
	print (t)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque 
from collections import defaultdict
n, x, y = map(int, input().split())
graph = [[] for _ in range(n)]     
for i in range(n-1):
  graph[i] += [i+1]
  graph[i+1] += [i]
graph[x-1] += [y-1]
graph[y-1] += [x-1]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0)) 

def bfs(s):
  dist = [float('inf')]*n
  dist[s] = 0
  q = deque([s])

  while q:
    u = q.popleft() 
    for v in graph[u]:
      if dist[v] == float('inf'):
        q += [v]
        dist[v] = dist[u] + 1

  return dist

ans = defaultdict(int)
for i in range(n):
  d = bfs(i)
  for j in range(i+1, n):
    ans[d[j]] += 1 

for i in range(1, n):
  if i in ans.keys():
    print(ans[i])
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N, X, Y = map(int, input().split())
X, Y = X-1, Y-1
d = np.zeros((N, N))

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

for k in range(1, N):
    print(np.sum(d==k))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N, X, Y = map(int, input().split())
X, Y = X-1, Y-1
d = np.zeros((N, N))

for i in range(N-1):
    for j in range(i+1, N):
        if i >= Y or j <= X:
            d[i, j] = j-i
            continue
        d[i, j] = min(j-i, abs(X-i)+1+abs(Y-j))

for k in range(1, N):
    print(np.sum(d==k))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
DATA = """
10 4 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N, X, Y = [int(i) for i in get_line().strip().split(" ")]
X-=1
Y-=1
INF = 10 **15
m = [[INF] * N for _ in range(N)]

ret = []
for i in range(N-1):
	m[i][i+1] = 1
	m[i+1][i] = 1
	ret.append((i, i+1))
ret.append((X, Y))
m[X][Y] = 1
m[Y][X] = 1

#print(ret)
#print(len(ret))

tt = [0] * N
for _ in range(N):
	tt2 = [0] * N
	for r in range(N):
		for c in range(r+1, N):
			if r == c:
				continue
			for k in range(N):
				m[r][c] = min(m[r][c], m[r][k] + m[k][c])
			#m[c][r] = m[r][c]
			if not m[c][r] == INF:
				tt2[m[r][c]] += 1
			m[c][r] = m[r][c]
	if tt2 == tt:
		break
	tt = tt2

# for i in m:
# 	print (i)

for t in tt[1:]:
	print (t)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
class Graph:
    edges = {}

    def append_edge(self, sv, ev, weight = 1):
        if sv in self.edges:
            self.edges[sv].append((ev, weight))
        else:
            self.edges[sv] = [(ev, weight)]

    def bfs(self, sv):
        dist = [-1]*len(self.edges.keys())
        q = deque([])   # キュー
        q.append(sv)
        dist[sv] = 0
        connect_vtxs = []
        while len(q) > 0:
            p = q.popleft()     # キュー取りだし（先頭）
            connect_vtxs.append(p)
            for (ev, w) in self.edges[p]:
                if dist[ev] != -1:
                    continue
                q.append(ev)    # キュー追加
                dist[ev] = dist[p] + 1
        return dist, connect_vtxs


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

g = Graph()
for i in range(N - 1):
    g.append_edge(i, i + 1)
    g.append_edge(i + 1, i)
g.append_edge(X - 1, Y - 1)
g.append_edge(Y - 1, X - 1)

dist_cnt = [0]*N
for sv in range(N):
    dist, connect_vtxs = g.bfs(sv)
    for j in range(len(dist)):
        if dist[j] == -1: continue
        dist_cnt[dist[j]] += 1

for i in range(N-1):
    print(int(dist_cnt[i+1]/2))

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+1,n+1):
        a1=abs(i-j)
        a2=abs(x-i)+1+abs(y-j)
        a3=abs(y-i)+1+abs(x-j)    
        d=min(a1,a2,a3)
        ans[d]+=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=[0]*n
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a1=abs(i-j)
        a2=abs(x-i)+1+abs(y-j)
        a3=abs(y-i)+1+abs(x-j)
        d=min(a1,a2,a3)
        ans[d]+=1

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

Submission status: Time Limit Exceeded

Solution code:
import itertools as it

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

dist_list = []
dist_a = dist_list.append
for i, j in it.combinations(list(range(n)), 2):
    warp_dist = abs(i - (x - 1)) + 1 + abs(j - (y - 1))
    if abs(j - i) < warp_dist:
        dist_a(abs(j - i))
    else:
        dist_a(warp_dist)

for i in range(1, n):
    print(dist_list.count(i))

Submission status: Time Limit Exceeded

Solution code:
import itertools as it

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

dist_list = []
for i, j in it.combinations(list(range(n)), 2):
    warp_dist = abs(i - (x - 1)) + 1 + abs(j - (y - 1))
    if abs(j - i) < warp_dist:
        dist_list.append(abs(j - i))
    else:
        dist_list.append(warp_dist)

for i in range(1, n):
    print(dist_list.count(i))

Submission status: Time Limit Exceeded

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

for c in count:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,x,y=map(int,input().split())
g = [[i-1,i+1] for i in range(1,n-1)]
g.insert(0,[1])
g.append([n-2])
g[x-1].append(y-1)
g[y-1].append(x-1)
dist = []


def bfs(i):
    d = [float("inf")]*n
    
    que = deque([])
    que.append(i)
    d[i] = 0

    while que:
        idx = que.popleft()
        l = g[idx]
        
        for j in l:
            if d[j] == float("inf"):
                d[j] = d[idx] + 1
                que.append(j)
            elif d[j] > d[idx] + 1:
                d[j] = d[idx] + 1
                que.append(j)
    
    dist.extend(d)

for i in range(n):
    bfs(i)

dist.sort()
for i in range(1,n):
    print(dist.count(i)//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
INF = 10 ** 5
n, x, y = (int(_) for _ in input().split())
dict = {}
table = [[INF] * (n+1) for i in range(n+1)]
res = [0] * n

def bfs(i): #頂点iから行ける場所を探す
  deq = deque()
  node_lst = [-1] * (n+1) #訪れた頂点を管理
  node_lst[i] = 0
  deq.extend(dict[i])
  for j in dict[i]:
    node_lst[j] = node_lst[i] + 1
  while deq:
    p = deq.popleft()
    for j in dict[p]:
      if node_lst[j] == -1:
        deq.append(j)
        node_lst[j] = node_lst[p] + 1
  for j in range(1, n+1):
    if node_lst[j] < 1:
      continue
    a, b = i, j
    if x > y:
      a, b = b, a
    table[a][b] = min(table[a][b], node_lst[j])
  
#入力
for i in range(1, n+1):
  if i == 1:
    dict[i] = [2]
  elif i == n:
    dict[i] = [n - 1]
  else:
    dict[i] = [i-1, i+1]
dict[x] += [y]
dict[y] += [x]

#bfs
for i in range(1, n+1):
  bfs(i)
for i in range(1, n+1):
  for j in range(i, n+1):
    if table[i][j] == INF:
      continue
    res[table[i][j]] += 1
    
#出力
for i in range(1, n):
  print(res[i])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

dist = []
for i in range(n):
    dist.append([110110] * n)

def dijkstra(s):
    h = []
    heapq.heappush(h, (0, s))
    dist[s][s] = 0
    while len(h) != 0:
        pair = heapq.heappop(h)
        now = pair[1]
        dis = pair[0]
        if dis < dist[s][now]:
            continue

        if now != 0:
            if dist[s][now] + 1 < dist[s][now-1]:
                dist[s][now-1] = dist[s][now] + 1
                heapq.heappush(h, (dist[s][now-1], now-1))
        if now != n-1:
            if dist[s][now] + 1 < dist[s][now+1]:
                dist[s][now+1] = dist[s][now] + 1
                heapq.heappush(h, (dist[s][now+1], now+1))
        if now == x:
            if dist[s][now] + 1 < dist[s][y]:
                dist[s][y] = dist[s][now] + 1
                heapq.heappush(h, (dist[s][y], y))
        if now == y:
            if dist[s][now] + 1 < dist[s][x]:
                dist[s][x] = dist[s][now] + 1
                heapq.heappush(h, (dist[s][x], x))

cnt = [0] * n

for i in range(n):
    dijkstra(i)
for i in range(n):
    for j in range(n):
        cnt[dist[i][j]] += 1
for i in range(1, n):
    print(cnt[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
n, x, y = list(map(int, input().split()))
x -= 1
y -= 1

dist = []
for i in range(n):
    dist.append([110110] * n)

def dfs(now, s):
    if now != 0:
        if dist[s][now] + 1 < dist[s][now-1]:
            dist[s][now-1] = dist[s][now] + 1
            dfs(now-1, s)
    if now != n-1:
        if dist[s][now] + 1 < dist[s][now+1]:
            dist[s][now+1] = dist[s][now] + 1
            dfs(now+1, s)
    if now == x:
        if dist[s][now] + 1 < dist[s][y]:
            dist[s][y] = dist[s][now] + 1
            dfs(y, s)
    if now == y:
        if dist[s][now] + 1 < dist[s][x]:
            dist[s][x] = dist[s][now] + 1
            dfs(x, s)

cnt = [0] * n

for i in range(n):
    dist[i][i] = 0
    dfs(i, i)

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys
sys.setrecursionlimit(10 ** 5)

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

G = [[] for _ in range(N + 1)]
for i in range(1, N):
    G[i].append(i + 1)
    G[i + 1].append(i)
G[Y].append(X)
G[X].append(Y)
#print(G)

seen = [False] * (N + 1)
todo = queue.Queue()
route = [0] * (N + 1)
def bfs(parent):
    seen[parent] = True
    #print(route)
    for child in G[parent]:
        if seen[child] == False:
            seen[child] = True
            route[child] = route[parent] + 1
            todo.put(child)
    if not todo.empty():
        bfs(todo.get())

bfs(1)
#print(route)

bucket = [0] * N
for i in range(1, N + 1):
    seen = [False] * (N + 1)
    route = [0] * (N + 1)
    bfs(i)
    for val in route:
        bucket[val] += 1
#print(bucket)
for i in range(1, N):
    print(bucket[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    ans = [0 for _ in range(N)]
    for s in range(N):
        dist = [-1 for _ in range(N)]
        dist[s] = 0

        d = deque([s])
        while(len(d) > 0):
            v = d.popleft()
            if v == X:
                if dist[Y] == -1:
                    d.append(Y)
                    dist[Y] = dist[v] + 1
            if v == Y:
                if dist[X] == -1:
                    d.append(X)
                    dist[X] = dist[v] + 1
            if v + 1 < N:
                if dist[v+1] == -1:
                    d.append(v+1)
                    dist[v+1] = dist[v] + 1
            if v - 1 >= 0:
                if dist[v-1] == -1:
                    d.append(v-1)
                    dist[v-1] = dist[v] + 1

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    matrix = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        matrix[i][i] = 0
    for s in range(N):
        d = deque([s])
        while(len(d) > 0):
            v = d.popleft()
            if v == X:
                if matrix[s][Y] == -1:
                    d.append(Y)
                    matrix[s][Y] = matrix[s][v] + 1
            if v == Y:
                if matrix[s][X] == -1:
                    d.append(X)
                    matrix[s][X] = matrix[s][v] + 1
            if v + 1 < N:
                if matrix[s][v+1] == -1:
                    d.append(v+1)
                    matrix[s][v+1] = matrix[s][v] + 1
            if v - 1 >= 0:
                if matrix[s][v-1] == -1:
                    d.append(v-1)
                    matrix[s][v-1] = matrix[s][v] + 1
    
    cnt = {k: 0 for k in range(1, N)}
    for h in range(N):
        for w in range(h+1, N):
            cnt[matrix[h][w]] += 1
    
    for k in range(1, N):
        print(cnt[k])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int, input().split())
dp = [[100000000 for j in range(n)] for i in range(n)]
re = [0]*n
for i in range(n):
  for j in range(n):
    if i==j:
      dp[i][j] = 0
    if abs(i-j)==1:
      dp[i][j] = 1
    if i==x-1 and j==y-1:
      dp[i][j] = 1
    if i==y-1 and j==x-1:
      dp[i][j] = 1
    

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


for i in range(n):
  for j in range(i):
    re[dp[i][j]] +=1
    
for i in range(n-1):
  print(re[i+1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,x,y = map(int, input().split())
dp = [[100000000 for j in range(n)] for i in range(n)]
re = [0]*n
for i in range(n):
  for j in range(n):
    if i==j:
      dp[i][j] = 0
    if abs(i-j)==1:
      dp[i][j] = 1
    if i==x-1 and j==y-1:
      dp[i][j] = 1
    if i==y-1 and j==x-1:
      dp[i][j] = 1
    

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


for i in range(n):
  for j in range(i):
    re[dp[i][j]] +=1
    
for i in range(n-1):
  print(re[i+1])

Submission status: Time Limit Exceeded

Solution code:
#N, X, Y = map(int, input().split())
#l = [0 for _ in range(N-1)]
#for i in range(1, N+1):
#    for j in range(i+1,N+1):
#        n = min(j-i, abs(i-X)+1 + abs(j-Y))
#        l[n-1] +=1
#for m in l:
#    print(m)
inf = 100000
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
ans = [0] *N
for i in range(N):
    queue = []
    dist = [inf] *N
    def push(n, d):
        if dist[n] == inf:
            dist[n] = d
            queue.append(n)
    push(i, 0)
    for q in queue:
        if q-1 >=0:
            push(q-1, dist[q] + 1)
        if q+1 <N:
            push(q+1, dist[q] + 1)
        if q == X:
            push(Y, dist[q] + 1)
        if q == Y:
            push(X, dist[q] + 1)
    for d in dist:
        ans[d] += 1
for i in range(1, N):
    print(int(ans[i]/2))

Submission status: Time Limit Exceeded

Solution code:
#N, X, Y = map(int, input().split())
#l = [0 for _ in range(N-1)]
#for i in range(1, N+1):
#    for j in range(i+1,N+1):
#        n = min(j-i, abs(i-X)+1 + abs(j-Y))
#        l[n-1] +=1
#for m in l:
#    print(m)
inf = 100000
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
ans = [0] *N
for i in range(N):
    queue = []
    dist = [inf] *N
    def push(n, d):
        if dist[n] == inf:
            dist[n] = d
            queue.append(n)
    push(i, 0)
    while queue != []:
        q = queue.pop(0)
        if q-1 >=0:
            push(q-1, dist[q] + 1)
        if q+1 <N:
            push(q+1, dist[q] + 1)
        if q == X:
            push(Y, dist[q] + 1)
        if q == Y:
            push(X, dist[q] + 1)
    for d in dist:
        ans[d] += 1
for i in range(1, N):
    print(int(ans[i]/2))

Submission status: Time Limit Exceeded

Solution code:
#N, X, Y = map(int, input().split())
#l = [0 for _ in range(N-1)]
#for i in range(1, N+1):
#    for j in range(i+1,N+1):
#        n = min(j-i, abs(i-X)+1 + abs(j-Y))
#        l[n-1] +=1
#for m in l:
#    print(m)
inf = 100000
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
ans = [0] *N
for i in range(N):
    queue = []
    dist = [inf] *N
    def push(n, d):
        if dist[n] == inf:
            dist[n] = d
            queue.append(n)
    push(i, 0)
    while len(queue) > 0:
        q = queue.pop(0)
        if q-1 >=0:
            push(q-1, dist[q] + 1)
        if q+1 <N:
            push(q+1, dist[q] + 1)
        if q == X:
            push(Y, dist[q] + 1)
        if q == Y:
            push(X, dist[q] + 1)
    for d in dist:
        ans[d] += 1
for i in range(1, N):
    print(int(ans[i]/2))

Submission status: Time Limit Exceeded

Solution code:
#N, X, Y = map(int, input().split())
#l = [0 for _ in range(N-1)]
#for i in range(1, N+1):
#    for j in range(i+1,N+1):
#        n = min(j-i, abs(i-X)+1 + abs(j-Y))
#        l[n-1] +=1
#for m in l:
#    print(m)
inf = 100000
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
ans = [0 for _ in range(N)]
for i in range(N):
    queue = []
    dist = [inf for _ in range(N)]
    def push(n, d):
        if dist[n] == inf:
            dist[n] = d
            queue.append(n)
    push(i, 0)
    while len(queue) > 0:
        q = queue.pop(0)
        if q-1 >=0:
            push(q-1, dist[q] + 1)
        if q+1 <N:
            push(q+1, dist[q] + 1)
        if q == X:
            push(Y, dist[q] + 1)
        if q == Y:
            push(X, dist[q] + 1)
    for d in dist:
        ans[d] += 1
for i in range(1, N):
    print(int(ans[i]/2))