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 collections
import heapq

class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]
      
n, x, y = [int(i) for i in input().split()]

dij = Dijkstra()

for i in range(n-1):
  dij.add(i, i+1, 1)
dij.add(x-1, y-1, 1)

d = []
for i in range(n):
  d += list(dict(dij.Dijkstra_search(i)[0]).values())

from collections import Counter
c = Counter(d)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
    import sys
    input = sys.stdin.readline
    def flatten_2dim(array): return [item for sublist in array for item in sublist]

    n, x, y = map(int, input().split())
    f_inf = float('inf')
    dist = [[f_inf] * n for _ in range(n)]

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

    G = csgraph_from_dense(dist, null_value=10**9)
    dist = floyd_warshall(G)

    counter = Counter(flatten_2dim(dist))
    counter = sorted(counter.most_common())[1:]

    for key, val in counter: print(val//2)
    for _ in range(n - len(counter)-1): print(0)
if __name__ == "__main__": main()

Submission status: Time Limit Exceeded

Solution code:
from collections import OrderedDict


if __name__ == "__main__":
    N, X, Y = map(int, input().split())
    k_dict = OrderedDict()

    for i in range(1, N):
        k_dict[i] = 0

    for i in range(1, N):
        for j in range(i+1, N+1):
            if i <= X and j <= X:
                d = j - i
                k_dict[d] += 1
                # print('{} {} {} debug 1'.format(i, j, d))
                continue

            if i <= X and X < j and j < Y:
                d = min(j-i, X-i + 1 + Y-j)
                k_dict[d] += 1
                # print('{} {} {} debug 2'.format(i, j, d))
                continue

            if i <= X and Y <= j:
                d = X-i + 1 + j-Y
                k_dict[d] += 1
                # print('{} {} {} debug 3'.format(i, j, d))
                continue

            if X < i and i < Y and X < j and j < Y:
                d = min(j-i, i-X + 1 + Y-j)
                k_dict[d] += 1
                # print('{} {} {} debug 4'.format(i, j, d))
                continue

            if X < i and i < Y and Y <= j:
                d = min(j-i, i-X + 1 + j - Y)
                k_dict[d] += 1
                # print('{} {} {} debug 5'.format(i, j, d))
                continue

            if Y <= i and Y <= j:
                d = j-i
                k_dict[d] += 1
                # print('{} {} {} debug 6'.format(i, j, d))
                continue

    for k, v in k_dict.items():
        # print('{} {}'.format(k, v))
        print(v)

Submission status: Time Limit Exceeded

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

ans = [0]*(n-1)
d = {}
for i in range(n-1):
    Q = deque()
    Q.append((i,-1,0))
    flag = [False]*n
    while Q:
        cur,prev,dist = Q.popleft()
        flag[i] = True
        for nxt in to[cur]:
            if nxt == prev: continue
            if flag[nxt]: continue
            flag[nxt] = True
            if (i,nxt) not in d: ans[dist] += 1
            Q.append((nxt,cur,dist+1))
            d[(i,nxt)] = 1
            d[(nxt,i)] = 1

print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main2():
	n, x, y = IN()
	al=[[-1]*n for _ in range(n)]
	ol=queue.Queue()
	for i in range(n):
		for j in range(n-i):
			al[i][i+j]=j
		for j in range(i+1):
			al[i][i-j]=j
	
	al[x-1][y-1]=1
	
	print(al)

def main():
	n, x, y = IN()
	al=[[-1]*n for _ in range(n)]
	ol=queue.Queue()
	for i in range(n):
		al[i][i]=0
	
	for i in range(n-1):
		al[i][i+1]=1
		ol.put((i,i+1))
		al[i+1][i]=1
	al[x-1][y-1]=1
	ol.put((x-1, y-1))
	al[y-1][x-1]=1
	while not ol.empty():
		#print(ol.qsize())
		fp, tp = ol.get()
		for i, dist in enumerate(al[tp]):
			nd = al[fp][tp] + dist
			if dist > 0 and (al[fp][i] == -1 or al[fp][i] > nd) and fp < i:
				al[fp][i]=nd
				al[i][fp]=nd
				ol.put((fp,i))
			
		fp,tp=tp,fp
		for i, dist in enumerate(al[tp]):
			nd = al[fp][tp] + dist
			if dist > 0 and (al[fp][i] == -1 or al[fp][i] > nd) and fp < i:
				al[fp][i]=nd
				al[i][fp]=nd
				ol.put((fp,i))
			
	rr=[0]*n
	for i in range(n):
		for j in range(i+1,n):
			rr[al[i][j]]+=1
	
	for v in rr[1:]:
		print(v)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np


n, x, y = map(int, input().split())
ans = [0] * (n - 1)

table = []
for i in range(n):
  l = [0] * n
  if i + 1 < n:
    l[i + 1] = 1
  if i - 1 > -1:
    l[i - 1] = 1
  if i == x - 1:
    l[y - 1] = 1
  if i == y - 1:
    l[x - 1] = 1
  table.append(l)

a = shortest_path(np.array(table))
for i in a:
  for j in i:
    ans[int(j) - 1] += 1

ans = list(map(lambda x: x // 2, ans))
ans[-1] = 0
for i in range(n - 1):
  print(ans[i])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
Es=[(i,i+1) for i in range(N-1)]
Es.append((X-1,Y-1)) 
for i in range(len(Es)):
    aa,bb=Es[i]
    Es.append((bb,aa))
#print(Es)
c=[[N+1 for _ in range(N)]for _ in range(N)]
#print(c)
for each in Es:
    f,t=each
    c[f][t]=1

COST=tuple(c)
D=tuple([N+1 for _ in range(N)])
USED=tuple([False for _ in range(N)])
ans=[]
ans_2=[0 for _ in range(N-1)]
for i in range(N):
    cost= list(COST)
    d=list(D)
    used=list(USED)
    d[i]=0
    while True:
        v=-1
        for u in range(N):
            if not used[u] and ( v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(N):
            d[u] = min(d[u],d[v]+cost[v][u])
    #print(d)
    ans+=d[i:]
    for j in range(N-1):
        ans_2[j]+=d[i:].count(j+1)
#print(ans_2)
#for i in range(N-1):
#    print(ans.count(i+1))
for each in ans_2:
    print(each)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import numpy as np
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    n, x, y = map(int, input().split())
    netw = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            if abs(j-i) == 1:
                netw[i][j] = 1
    netw[x-1][y-1] = 1
    netw[y-1][x-1] = 1
    netw = np.array(netw)
    ans = {}
    a = shortest_path(netw)
    for i in range(n-1):
        for j in range(i+1, n):
            if a[i][j] in ans:
                ans[a[i][j]] += 1
            else:
                ans[a[i][j]] = 1
    for i in range(1, n):
        if i in ans:
            print(ans[i])
        else:
            ans[i] =0
            print(ans[i])
        
resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
def solve():
    N, X, Y = map(int, input().split())
    cnter = defaultdict(int)

    for start in range(N-1):
        deq = deque()
        deq.append(start)
        n_step = [float('inf')] * N
        n_step[start] = 0
        visited = [False] * N

        while len(deq) > 0:
            fr = deq.popleft()
            visited[fr] = True

            if fr == X-1:
                if not visited[Y-1] or n_step[Y-1] > n_step[X-1]+1:
                    n_step[Y-1] = n_step[X-1]+1
                    deq.append(Y-1)
                    visited[Y-1] = True

            if fr == Y-1:
                if not visited[X-1] or n_step[X-1] > n_step[Y-1]+1:
                    n_step[X-1] = n_step[Y-1]+1
                    deq.append(X-1)
                    visited[X-1] = True
                    
            if fr != N-1:
                if not visited[fr+1] or n_step[fr+1] > n_step[fr]+1:
                    deq.append(fr+1)
                    n_step[fr+1] = n_step[fr]+1
                    visited[fr+1] = True

            if fr != 0:
                if not visited[fr-1] or n_step[fr-1] > n_step[fr]+1:
                    deq.append(fr-1)
                    n_step[fr-1] = n_step[fr]+1
                    visited[fr-1] = True
        
        for i in range(start,N):
            if n_step[i] == float('inf'):
                continue
            cnter[n_step[i]] += 1
            
    for i in range(1,N):
        print(cnter[i])

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n,x,y = map(int,input().split()) #n:頂点数　w:辺の数
w = n
cost = [[float("inf") for i in range(n)] for i in range(n)]
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
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
di = []
ans = {1:n}
for i in range(2,n):
    ans[i]=0


for i in range(n):
    dij = dijkstra(i,n,w,cost)
    di.append(dij)
    for j in range(2,n):
        ans[j] += dij.count(j)




print(ans[1])
for k, v in ans.items():
    if k==1:continue
    print(v//2)

Submission status: Time Limit Exceeded

Solution code:

n, x, y = (int(x) for x in input().split())
if y < x:
    x, y = y, x

# def count(k):
#     sol = 0
#     sol += max(0, n - (y-x-1) - k)
#     d = y-x+1
#     if 2*k <= d:
#         if d > 2:
#             sol += d
#
#             if k == 1:
#                 sol -= d

import collections
nei = collections.defaultdict(set)
for i in range(1, n):
    nei[i].add(i+1)
    nei[i+1].add(i)

nei[x].add(y)
nei[y].add(x)

def bfs(source):
    visited_dist = {source: 0}
    q = collections.deque([source])
    while q:
        node = q.popleft()
        for node2 in nei[node]:
            if node2 not in visited_dist:
                visited_dist[node2] = visited_dist[node] + 1
                q.append(node2)
    return visited_dist

sol = [0]*n

for source in range(1, n+1):
    visited_dist = bfs(source)
    for x in visited_dist.values():
        sol[x] += 1

for i in range(1, n):
    print(sol[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 shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

l = np.zeros((n,n),dtype=int)

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

a = shortest_path(l)
# print(a)
b = np.triu(a)
# print(b)
c = b.reshape(1,n**2)
# print(c[0])
d = list(map(int,c[0]))

e = [ i for i in d if i!=0 ]
print(n)
for i in range(2,n):
    print(e.count(i))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import deque
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        D[i][j] = abs(j-i)
        D[j][i] = abs(j-i)
D[X][Y] = 1
D[Y][X] = 1
# print(*D, sep="\n")
queue = deque([[X, Y]])
visited = [[False for _ in range(N)] for _ in range(N)]
visited[X][Y] = True 
while queue:
    x,y = queue.popleft()
    for i, j in zip([1, 0, -1, 0], [0, 1, 0, -1]):
        nx, ny = x+i, y+j
        if nx < 0 or nx >= N or ny < 0 or ny >= N:
            continue
        if visited[nx][ny]:
            continue
        else:
            visited[nx][ny] = True
            D[nx][ny] = min(D[nx][ny], D[x][y]+1)
            queue.append([nx, ny])
# print(*D, sep="\n")
ans = [0 for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        # cnt += 1
        v = D[i][j]
        # print(i,j, v)
        ans[v-1] += 1
print(*ans[:-1], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path,floyd_warshall,dijkstra,bellman_ford,johnson
from scipy.sparse import csr_matrix
N,X,Y = map(int,input().split())

#隣接リストの整備
route_list = [[0]*N]
route_list[0][1] = 1
for i in range(1,N-1):
    route_list.append([0]*N)
    route_list[i][i-1] = 1
    route_list[i][i+1] = 1
route_list.append([0]*N)
route_list[-1][-2] = 1
route_list[X-1][Y-1] = 1
route_list[Y-1][X-1] = 1
route_list = np.array(route_list)

shortest = shortest_path(route_list)

for i in range(1,N):
    print(np.count_nonzero(shortest == i)//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

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

ans = shortest_path(np.array(graph))

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

Submission status: Time Limit Exceeded

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

dis = []

for i in range(n):
    for j in range(i+1, n):
        kyori = min(j-i, abs(x - (i+1)) + 1 + abs(y - (j+1)))
        dis.append(kyori)

for k in range(1, n):
    print(dis.count(k))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from copy import deepcopy

import sys
sys.setrecursionlimit(100000)

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

# neighbor = {}
# for i in range(1, N):
#     neighbor[i] = [i+1]
# for i in range(X+4, Y):
#     neighbor[i] = [i-1, i+1]
# neighbor[X] = [X+1, Y]
# neighbor[Y] = [Y-1, Y+1]
# neighbor[N] = [] if Y < N else [N-1] 
# print(neighbor)

neighbor = {}
for i in range(1, X):
    neighbor[i] = [i+1]
for i in range(Y+1, N):
    neighbor[i] = [i+1]
for i in range(X+1, Y):
    neighbor[i] = [i-1, i+1]
neighbor[X] = [X+1, Y]
neighbor[Y] = [Y-1, Y+1]
neighbor[N] = [] if Y < N else [N-1]
# print(neighbor)

# print(neighbor)

# neighbor = {i: [i-1, i+1] for i in range(2, N)}
# neighbor[1] = [2]
# neighbor[N] = [N-1]
# neighbor[X].append(Y)
# neighbor[Y].append(X)

# appeared_st = set([])
appeared_st = [set([]) for _ in range(N+1)]
appeared_st[0] = 0


def rec(n, dist, s, k, appeared):
    # print(appeared_st)
    if dist == k:
        # if k == 2:
        #     input()
        if s < n and n not in appeared_st[s]:
            appeared_st[s].add(n)
            appeared_st[0] += 1
            # print(appeared_st)

    toes = [node for node in neighbor[n] if node not in appeared]
    for to in toes:
        appeared_copy = deepcopy(appeared)
        appeared_copy.add(to)
        rec(to, dist+1, s, k, appeared_copy)


for k in range(1, N):
    tmp = appeared_st[0]

    for s in range(1, N+1):
        rec(s, 0, s, k, {s})

    print(appeared_st[0] - tmp)

# print(appeared_st)
# print(len(appeared_st))

Submission status: Time Limit Exceeded

Solution code:
import sys


n, x, y = map(int, sys.stdin.readline().split())
dist = []
for i in range(n):
    dist.append([])
    for j in range(n):
        dist[i].append(abs(j - i))

dist[x-1][y-1] = 1
dist[y-1][x-1] = 1

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

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

for one in final:
    print(one)

Submission status: Time Limit Exceeded

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

counts = [0 for i in range(N-1)]

distances = [[] for i in range(N-1)] 

for i in range(N):
    for j in range(i+1, N):
        dis = j-i
        if i <= X-1 :
            if j >= Y-1:
                dis -= Y-X-1
            elif j < Y-1:
                dis = min([j-i, (X-1)-i+1+abs(j-(Y-1))])             
        else:
            dis = min([j-i, i-(X-1)+1+abs(j-(Y-1))])
        
        distances[i].append(dis)
for i in range(N-1):
    for j in range(N-i-1):
        k = distances[i][j]-1
        counts[k] += 1
        
for k in range(N-1):
    print(counts[k])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
 
x,y,z=list(map(int, input().split()))
a= [[0] * x for i in range(x)]
 
for i in range(x-1):
	a[i][i+1]=1
	a[i+1][i]=1
 
a[y-1][z-1]=1
a[z-1][y-1]=1
 
b = np.array(a)
c=shortest_path(b)
t=[0]*x
for i in range(x):
	for j in range(i,x):
		t[int(c[i][j])]=t[int(c[i][j])]+1
for i in range(1,x):
	print(t[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, X, Y = map(int, input().split())
dists = defaultdict(lambda: N)
for k in range(1, N):
    for i in range(1 + k, N + 1):
        dists[(i - k, i)] = min(dists[(i - k, i)], k)
    for i in range(k):
        for a, b in (
            (X - i, Y + k - 1 - i),
            (X - i, Y - (k - 1 - i)),
            (X + i, Y + k - 1 - i),
            (X + i, Y - (k - 1 - i)),
        ):
            if 1 <= a <= N and 1 <= b <= N and a < b:
                dists[(a, b)] = min(dists[(a, b)], k)

d = defaultdict(int)
for v in dists.values():
    d[v] += 1
for k in range(1, N):
    print(d.get(k, 0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

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

ans = shortest_path(np.array(graph))
u= np.unique(ans)

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
#from scipy.special import comb
import itertools

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

combi = list(itertools.combinations(range(1,N+1), 2))
#print(combi)
dist = {}
for i in range(1, N):
    dist[i] = 0

for kyori in combi:
    a = kyori[1] - kyori[0]
    b = int(abs((kyori[1] - Y))) + 1 + int(abs((X - kyori[0])))
    c = min([a, b])
    dist[c] += 1
    #print(c, kyori)
dist2 = sorted(dist.items())
#print(dist, dist2)
for i in range(0, N-1):
    print(dist2[i][1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

N, X, Y = map(int, input().split())
A = csr_matrix((N, N), dtype=np.int8).toarray()
for idx in range(N - 1):
    A[idx][idx + 1] = 1
    A[idx + 1][idx] = 1

A[X - 1][Y - 1] = 1
A[Y - 1][X - 1] = 1

graph = csr_matrix(A)
dist_matrix = floyd_warshall(csgraph=graph, directed=False, unweighted=True, return_predecessors=False)
for k in range(1, N):
    c = np.count_nonzero(dist_matrix == k)
    print(c // 2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, X, Y = map(int,input().split())
X = X-1
Y = Y-1
NN = np.array([np.zeros(N,dtype='int')]*N)
NN2 = np.array([np.zeros(N,dtype='int')]*N)

  
for i in range(N):
  for j in range(i,N):
    NN[i][j] = j-i
for i in range(N):
  for j in range(i+1,N):
    NN2[i][j] = abs(i-X)+abs(j-Y)+1
#print(NN)
#print(NN2)
NN_max = np.minimum(NN, NN2)
#print(NN_max)
for i in range(1,N):
  print(len(np.where(NN_max==i)[0]))

Submission status: Time Limit Exceeded

Solution code:
import sys
N, X, Y = map(int, sys.stdin.readline().split())
print(N)
k = 2
while k <= X + N-Y:
  a = N-k
  if Y-X-2 >= k:
    a += Y-X-k
  print(a)
  k += 1
while k <= N:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
from collections import Counter

sys.setrecursionlimit(10**6)

def DFS(i,v,d):
  global dist
  
  if d > N:
    return
  # 頂点vに隣接する頂点でvより大きいものが未発見
  for u in adj[v]:
    # distは最短距離なので上書き禁止
    if i != u:
      #print(i,u,d)
      if dist[i][u] > d:
        dist[i][u] = d
        dist[u][i] = d
        # その先は追加で探索
      DFS(i,u,d+1)

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

# 隣接リストを作成する
adj = [[] for _ in range(N)]

# adjに入力
for i in range(N-1):
  adj[i].append(i+1)
  adj[i+1].append(i)

# X,Yをadj入力
adj[X-1].append(Y-1)
adj[Y-1].append(X-1)

# 頂点間の最短距離を保持するdist
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for i in range(N):
  DFS(i,i,1)

  
# print(dist)
# distを１次元化
dist = list(itertools.chain.from_iterable(dist))
c = Counter(dist)

# 結果出力
for k in range(1,N):
  print(c[k]//2)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import numpy as np
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    n, x, y = map(int, input().split())
    netw = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if abs(j-i) == 1:
                netw[i][j] = 1
    netw[x-1][y-1] = 1
    netw[y-1][x-1] = 1
    netw = np.array(netw)
    ans = {}
    a = shortest_path(netw)
    for i in range(n-1):
        for j in range(i+1, n):
            if a[i][j] in ans:
                ans[a[i][j]] += 1
            else:
                ans[a[i][j]] = 1
    for i in range(1, n):
        if i in ans:
            print(ans[i])
        else:
            ans[i] =0
            print(ans[i])
        
resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, x, y = map(int, input().split())
dist = np.array([[i for i in range(n+1)] for _ in range(n+1)])

r = abs(x - y) - 1


for i in range(1, n+1):
    dist[i] = abs(dist[i] - i)
dist[x][y] = 1
dist[y][x] = 1
dist[x] = np.minimum(dist[x], dist[x][y] + dist[y])
dist[y] = np.minimum(dist[y], dist[y][x] + dist[x])

for i in range(n+1):
    dist[i] = np.minimum(dist[i], dist[i][y] + 1 + dist[x], dist[i][x] + 1 + dist[y])
    if i <= x:
        dist[i] = np.minimum(dist[i], dist[i][x] + 1 + dist[y])
    elif y <= i:
        dist[i] = np.minimum(dist[i], dist[i][y] + 1 + dist[x])
    else:
        dist[i] = np.minimum(dist[i],
                             dist[i][y] + 1 + dist[x]
                             )
        dist[i] = np.minimum(dist[i],
                             dist[i][x] + 1 + dist[y]
                             )



ans = np.zeros(n+1)
for row in dist[1:, 1:]:
    for j in row:
        if 0 <= j <= n-1:
            ans[j] += 1


for w in ans[1:n]:
    print(int(w//2))

Submission status: Time Limit Exceeded

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