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())

edges = [[] for _ in range(n)]
for i in range(n-1):
   edges[i].append(i+1)
   edges[i+1].append(i)

edges[x-1].append(y-1)
edges[y-1].append(x-1)

def bfs(v):
   dist = [-1] * n
   dist[v] = 0
   visit = [v]
   c = 1
   while visit:
      next = []
      for i in visit:
         for j in edges[i]:
            if dist[j] == -1:
               dist[j] = c
               next.append(j)
      visit = next
      c += 1

   return dist

minpath = []
for i in range(n):
   minpath.append(bfs(i))

for k in range(1, n):
   ans = 0
   for i in range(n):
      for j in range(i+1, n):
         if minpath[i][j] == k:
            ans += 1
   print(ans)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


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

    INF = 10 ** 5

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

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

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

    ans = [0] * (n - 1)

    d = warshall_floyd(d)

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

    for aa in ans:
        print(aa)

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

class Node:
    def __init__(self, idx):
        self.idx = idx
        self.a = []


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

for i in range(n):
    node = Node(i+1)
    nodes.append(node)

for i in range(n-1):
    cur = nodes[i]
    next = nodes[i+1]

    cur.a.append(next)
    next.a.append(cur)

X = nodes[x-1]
Y = nodes[y-1]
X.a.append(Y)
Y.a.append(X)
dp = [[None] * (n+1) for _ in range(n+1)]

for i in range(n):
    node = nodes[i]
    q = deque()
    q.append((node, 0))
    done = set()

    while q:
        t = q.popleft()
        node, d = t[0], t[1]

        if node.idx not in done:
            dp[i + 1][node.idx] = d
            done.add(node.idx)
            for adj in node.a:
                q.append((adj, d + 1))

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

for k in range(1, n):
    temp = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            if dp[i][j] == k:
                temp += 1
    print(temp//2)

Submission status: Time Limit Exceeded

Solution code:
def input_multiple_number():
    return map(int, input().split())

N,X,Y = input_multiple_number()

INF = 10000000
dist=[[INF] * (N+1) for i in range(N+1)]

toing = N
for froming in range(N):
	if froming == 0:
		continue
	toing = N
	while toing > froming:
		if toing<=froming:
			continue
		if toing == 0:
			continue
		shortcut = abs(froming-X)+abs(toing-Y)+1
		dist[froming][toing] = min(toing-froming,shortcut)

		toing -=1


ans = [0] * (N-1)
for i in range(N+1):
	for j in range(N+1):
		if dist[i][j] <= N:
			ans[dist[i][j]-1]+=1

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

Submission status: Time Limit Exceeded

Solution code:
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, start, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [float('inf') for i in range(self.N)]
        d[start] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True, d
        return False, d
      
n, x, y = [int(i) for i in input().split()]

bf = BellmanFord(n)

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

d = []
for i in range(n):
  d += bf.BellmanFord_search(i)

from collections import Counter
c = Counter(d)

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

Submission status: Time Limit Exceeded

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

dp = [[N+10] * N for i in range(N)]
for i in range(N-1):
    dp[i][i+1] = 1
for i in range(1, N):
    dp[i][i-1] = 1
dp[X-1][Y-1] = 1
dp[Y-1][X-1] = 1
    
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])

mindcnt = {}
for i in range(N):
    mindcnt[i] = 0

for i in range(N):
    for j in range(i+1, N):
        mind = dp[i][j]
        mindcnt[mind] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import collections
n,x,y=map(int,input().split())
w=n
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

################################

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
lst=[]
for i in range(n):
    d=dijkstra(i,n,w,cost)
    for j in range(len(d)):
        lst.append(d[j])
Lst=list(collections.Counter(lst).items())
Key=list(collections.Counter(lst).keys())
m=max(Key)
for i in range(1,m+1):
    print(Lst[i][1]//2)
for i in range(m+1,n):
    print(0)

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)}

# cost = [[float("inf") for i in range(n)] for i in range(n)]
# #cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
# for i in range(w - 1):
#     cost[i + 1][i] = 1
#     cost[i][i + 1] = 1
# cost[x - 1][y - 1] = 1
# cost[y - 1][x - 1] = 1

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:
n, x, y = map(int, input().split())
num_list = list(range(1,n+1))

ans_list = []

for i in range(1, n):
  for j in range(2, n+1):
    ans1 = j - i
    ans2 = abs(x-i) + 1 + abs(y-j)
    ans = min(ans1, ans2)
    ans_list.append(ans)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, x, y = map(int, input().split())
graph = dict()
for i in range(1, n+1):
    if i not in graph.keys():
        graph[i] = set()
    if i < n:
        graph[i].add(i+1)
    if i > 1:
        graph[i].add(i-1)
graph[x].add(y)
graph[y].add(x)
dist = [[]]
def bfs(source):
    q = deque()
    q.append(source)
    d = [pow(10, 4)] * (n+1)
    d[source] = 0
    vis = [0] * (n+1)
    while len(q):
        temp = q.popleft()
        for i in graph[temp]:
            if not vis[i]:
                q.append(i)
                vis[i] = 1
            d[i] = min(d[temp]+1, d[i])
    dist.append(d)
for i in range(1, n+1):
    bfs(i)
dp = dict()
for i in range(1, n):
    for j in range(i+1, n+1):
        if dist[i][j] not in dp.keys():
            dp[dist[i][j]] = 0
        dp[dist[i][j]] += 1
for i in range(1, n):
    if i not in dp.keys():
        print(0)
    else:
        print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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

sum_array = np.zeros((n - 1), dtype='int')

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        len_1 = j - i
        len_2_1 = np.abs(x-i) + 1 + np.abs(y-j)
        len_2_2 = np.abs(x-j) + 1 + np.abs(y-i)
        len_2 = min(len_2_1, len_2_2)
        len_min = min(len_1, len_2)
        sum_array[len_min - 1] += 1

for num in sum_array:
    print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

N, X, Y = map(int, input().split())
# 全探索でいけるのでは？
# 有向グラフとしてN回幅優先すれば良いのでは？
tree = [[] for _ in range(N)]
for i in range(N-1):
    tree[i].append(i+1)
    tree[i+1].append(i)
tree[X-1].append(Y-1)
tree[Y-1].append(X-1)
ans = defaultdict(int)
# 更新されない時はqに追加しない
for i in range(N):
    distant = [float("inf")]*N
    q = deque([i])  # 始まりのノード
    distant[i] = 0
    while len(q):
        # vは数字, 親のノードのインデックス
        v = q.pop()
        for e in tree[v]:
            if distant[e] < distant[v]+1:  # 到達済みなら次のノードへ
                continue
            distant[e] = min(distant[v]+1, distant[e])
            q.append(e)
    for i in range(1, N):
        ans[i] += distant.count(i)
for i in range(1, N):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import itertools

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
d[x-1][y-1] = 1
d[y-1][x-1] = 1
for i in range(n):
    d[i][i] = 0
warshall_floyd(d)
D = Counter(list(itertools.chain.from_iterable(d)))
for i in range(1, n):
    print(D[i]//2)

Submission status: Time Limit Exceeded

Solution code:
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

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

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行けそう
        # d[i][i] < 0 なら、グラフは負のサイクルを持つ
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        # for i in range(self.N):
        #     if self.d[i][i] < 0:
        #         hasNegativeCycle = True
        #         break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d

N,X,Y = map(int, input().split())
graph = WarshallFloyd(N)
for i in range(N - 1):
    graph.add(i, i + 1, 1)
graph.add(X - 1, Y - 1, 1)

result = graph.WarshallFloyd_search()
ans = []
for i in result[1]:
        ans.extend(i)

import collections
c = collections.Counter(ans)

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

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if (d[i][k] == 0 or d[k][j] == 0):
                    continue
                if (i == j):
                    continue
                if (d[i][j] == 0):
                    d[i][j] = d[i][k] + d[k][j]
                else:
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])

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

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

warshall_floyd(result, n)

result_hash = [0] * (n-1)
for i in range(n):
    for j in range(n):
        if result[i][j] == 0:
            continue
        result_hash[result[i][j] - 1] += 1

for i in range(n-1):
    print(int(result_hash[i] / 2))

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1,i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)
d = []
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    que = queue.Queue()
    que.put(start)
    while not que.empty():
        v = que.get()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v]+1
            que.put(nv)
    d.append(dist)
d = np.array(d).flatten()
for i in range(1,n):
    print(int(np.count_nonzero(d==i)/2))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
dists = [[-1] * N for _ in range(N)]
graph = [[1]]
graph .extend([i - 1, i + 1] for i in range(1, N - 1))
graph.append([N - 2])
graph[X - 1].append(Y - 1)
graph[Y - 1].append(X - 1)

d_count = [0] * N

for i in range(N):
    q = [i]
    dists[i][i] = 0
    while len(q) >= 1:
        n = q.pop(0)
        for n_next in graph[n]:
            if dists[i][n_next] >= 0:
                continue
            dists[i][n_next] = dists[i][n] + 1
            d_count[dists[i][n_next]] += 1
            q.append(n_next)

print("\n".join(str(d_count[i] // 2) for i in range(1, N)))

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,L,R=MI()
    edge = [ [] for i in range(N)]
    for i in range(N):
        if(i):
            edge[i].append(i-1)
        if(i<N-1):
            edge[i].append(i+1)
    L-=1
    R-=1
    edge[L].append(R)
    edge[R].append(L)
    ans = [0]*N
    for i in range(N):
        q = [i]
        visited = set()
        for step in range(N):
            tmp = []
            while(q):
                v = q.pop()
                if(v in visited):
                    continue
                ans[step] += 1
                visited.add(v)
                for to in edge[v]:
                    if(to in visited):
                        continue
                    tmp.append(to)
            q = tmp
    print(*[a//2 for a in ans[1:]],sep="\n")
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def sub(d):
    #listを引数にとる
    sub_ls = []
    #print("")
    for i in range(n):
        for j in range(i+1, n):
            #print(d[i][j])
            sub_ls.append(d[i][j])
    sub_ls.sort()
    #print(sub_ls)
    k = 1
    cnt = 0
    ll = 1
    #print("")
    for i in range(len(sub_ls)):
        if k == sub_ls[i]:
            cnt+=1
        else:
            print(cnt)
            cnt = 1
            k+=1
            ll+=1
    if cnt != 0:
        print(cnt)
        ll+=1
    for i in range(ll, n):
        print(0)
    return

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
for i in range(n):
    d[i][i] = 0
d[x-1][y-1] = 1
d[y-1][x-1] = 1
#print(d,"\n")
a = warshall_floyd(d)
#print(warshall_floyd(d))
sub(a)

Submission status: Time Limit Exceeded

Solution code:
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, a, b = map(int, input().split())

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

for i in range(n-1):
    # x,y,z = map(int,input().split())
    # cost[x][y] = z
    # cost[y][x] = z
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[a-1][b-1] = 1
cost[b-1][a-1] = 1


ANS = []
for i in range(n):
    ANS.extend(dijkstra(i, n, n, cost))

import collections

c = collections.Counter(ANS)

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

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):
      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:
import numpy as np
N, X, Y = map(int,input().split())

NN = np.array([np.zeros(N,dtype='bool')]*N)
count = 0
#initialize
for i in range(N-1):
  NN[i][i+1] = True
NN[X-1][Y-1] = True
print(N)
for _ in range(N-2):
  NN2 = np.array(NN)
  for i in range(N):
    for j in range(i+1,N):
      if NN[i][j] == True:
        #top
        if i !=0:
          if (not NN[i-1][j]) and (i-1<j):
            NN2[i-1][j] = True
        #bottom
        if i != N-1:
          if (not NN[i+1][j]) and (i+1<j):
            NN2[i+1][j] = True
            count += 1
        #left
        if j != 0:
          if (not NN[i][j-1]) and (i<j-1):
            NN2[i][j-1] = True
        #right
        if j != N-1:
          if (not NN[i][j+1]) and (i<j+1):
            NN2[i][j+1] = True
  count = np.sum(NN2)-np.sum(NN)
  if count==0:
    NN = NN2
    print(0)
  else:
    NN = NN2
    print(count)

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(x):
		t[int(c[i][j])]=t[int(c[i][j])]+1
for i in range(1,x):
	print(t[i]//2)

Submission status: Time Limit Exceeded

Solution code:
from itertools import tee

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


def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)


N, X, Y = map(int, input().split())
A = [[0 for _ in range(N)] for _ in range(N)]
for idx, row in enumerate(A, start=1):
    if idx < N:
        row[idx % N] = 1

A = np.array(A) + np.array(A).transpose()
A[X-1][Y-1] = 1
A[Y-1][X-1] = 1
# print(A)
graph = csr_matrix(A)
dist_matrix, predecessors = floyd_warshall(csgraph=graph, directed=False, return_predecessors=True)
# print(dist_matrix)
for k in range(1, N):
    c = np.count_nonzero(dist_matrix == k)
    print(c // 2)

Submission status: Time Limit Exceeded

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

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

d = defaultdict(int)

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

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

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)

def bfs(connections, node, result, source):
    visited = set()
    q = deque()
    q.append((node, 0))
    visited.add(node)
    while q:
        cur, dist= q.popleft()
        for next_node in connections[cur]:
            if next_node not in visited:
                q.append((next_node, dist + 1))
                visited.add(next_node)
                result[dist+1].add((min(source, next_node), max(source, next_node)))

ret = defaultdict(set)

for i in range(N):
    bfs(connections, i, ret, i)
    # print(ret)

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import floyd_warshall

    N,X,Y=map(int,input().split())
    # 距離行列の生成
    dist_matrix = [[0] * (N) for _ in range(N)]
    for i in range(N):
        dist_matrix[i][i] = 0
    for i in range(N-1):
        dist_matrix[i][i+1] = 1
        dist_matrix[i+1][i]=1
    dist_matrix[X-1][Y-1] = 1
    dist_matrix[Y-1][X-1] = 1


    graph = csr_matrix(dist_matrix)
    # ワーシャルフロイド
    dist_matrix = floyd_warshall(csgraph=graph, directed=False)
    ans = [0] * N
    for lst in dist_matrix:
        for i in range(len(lst)):
            ans[int(lst[i])] += 1

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






resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

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

L = [0] * (n**2)
for i in range(n):
    for j in range(n):
        L[n*i+j] = d[i][j]
D = Counter(L)
for i in range(1, n):
    print(D[i]//2)

Submission status: Time Limit Exceeded

Solution code:
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

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

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行けそう
        # d[i][i] < 0 なら、グラフは負のサイクルを持つ
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d

N,X,Y = map(int, input().split())
graph = WarshallFloyd(N)
for i in range(N - 1):
    graph.add(i, i + 1, 1)
graph.add(X - 1, Y - 1, 1)

result = graph.WarshallFloyd_search()
ans = []
for i in result[1]:
        ans.extend(i)

import collections
c = collections.Counter(ans)

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

Submission status: Time Limit Exceeded

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

def f(i,j):
  if j <= X:
    return j-i
  elif Y <= i:
    return j-i
  elif X <= i and j <= Y:
    return min(j-i,(i-X)+1+(Y-j))
  elif i <= X and Y <= j:
    return (X-i)+1+(j-Y)
  elif i <= X and X <= j and j <= Y:
    return (X-i)+min(j-X,1+(Y-j))
  else:
    return (j-Y)+min(Y-i,(i-X)+1)

A = []

for k in range(1,N,1):
  for l in range(k+1,N+1,1):
    A.append(f(k,l))

for k in range(1,N,1):
  print(A.count(k))

Submission status: Time Limit Exceeded

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


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

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

ans = [0] * n
for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1

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

dis = warshall_floyd(d)

for i in range(n):
    for j in range(n):
        if dis[i][j] != float("inf"):
            ans[dis[i][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())

diffs = []
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        diff_a = j - i
        diff_b = abs(x-i) + abs(y-j) + 1
        if diff_a <= diff_b:
            diffs.append(diff_a)
        else:
            diffs.append(diff_b)

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

Submission status: Time Limit Exceeded

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

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson

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)
#print(dist)
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:
import sys

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

d = [[sys.maxsize for _ in range(N)] for _ in range(N)]

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

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

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

answer = [0 for _ in range(N-1)]

for h in range(N):
  for i in range(N):
    if h != i:
      answer[d[h][i]-1] += 1

for k in range(N-1):
  print(answer[k]//2)

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
ans=[0]*(n-1)
for i in range(1,n):
  for j in range(i+1,n+1):
    d_o=j-i
    if i<=x and i<=y and j<=x and j<=y:
      d_d=10**9
    elif i>=x and i>=y and j>=x and j>=y:
      d_d=10**9
    elif i<=x and i<=y and j>=x and j>=y:
      d_d=x-i+1+j-y
    elif i<=x and i<=y and x<=j<=y:
      d_d=x-i+1+(y-j)
    elif x<=i<=y and j>=x and j>=y:
      d_d=i-x+1+j-y
    elif x<=i<=y and x<=j<=y:
      d_d=i-x+1+y-j
    else:
      print("###")
    tmp=min(d_o,d_d)
    ans[tmp-1]+=1

for i in ans:
  print(i)