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: Runtime Error

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

m = [[0 for i in range(n)] for j in range(n)]

def check(i, j):
    if -1 < i and i < n and -1 < j and j < n and i < j:
        if m[i][j] == 0:
            return True
    return False

def mark(i, j, c):
    if check(i-1, j):
        m[i-1][j] = c
    if check(i+1, j):
        m[i+1][j] = c
    if check(i, j-1):
        m[i][j-1] = c
    if check(i, j+1):
        m[i][j+1] = c

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

m[x-1][y-1] = 1

for c in range(n-1):
    for i in range(n-1):
        for j in range(n-1):
            if 1 < c and m[i][j] == c-1:
                mark(i, j, c)

import numpy
l=numpy.arrange(m)

for i in range(n-1):
    print(l.count(i+1))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
n, x, y = map(int, input().split())



def warshall_floyd(n , x, y):
    d = [0] * n

    for i in range(n):
        d[i] = [0] * n
        for j in range(n):
            if abs(i - j) == 1 or (i == x and j == y ) or (j == x and i == y):
                d[i][j] = 1
            else:
                d[i][j] = 100000
    
    # for k in range(n):
    #     for i in range(n):
    #         for j in range(i+1, n):
    #             next_distance = d[i][k]+d[k][j]
    #             if next_distance < d[i][j]:
    #                 d[i][j] = next_distance
    G = csgraph_from_dense(d, null_value=100000, directed=False)
    d = floyd_warshall(G)
    
    distance_map = {i: 0 for i in range(1, n)}
    for i in range(n):
        for j in range(i + 1,n):
            if d[i][j] != 100000:
                distance_map[d[i][j]] += 1  

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

warshall_floyd(n, x-1, y-1)

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))


A = list(map(int, input().split()))
N = A[0]
X = A[1]
Y = A[2]

graph = [[1 if j == i+1 or j+1 == i else floaot('inf') for j in range(1,N+1)] for i in range(1,N+1)]
graph[X-1][Y-1] = 1
graph[Y-1][X-1] = 1

dist = []

d = Dijkstra()

for i in range(N):
  for j in range(N):
    if i == j: continue
    dist.append(len(d.dijkstra(graph, i, j))-1)
    
for i in range(N-1):
  print((int)(dist.count(i+1)/2))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import collections 
N,X,Y = map(int,input().split())
d = [[0]*(N+1) for _ in range(N+1)]
for i in range(1,N):#i => j
    for j in range(i+1,N+1):
        if(i>=Y or j<=X):
            d[i][j] = j-i
        elif(i<=X and j>=Y):
            d[i][j] = (X-i)+1+(j-Y)
        else:
            a_path = j-i
            b_path = abs(X-i)+1+abs(Y-j)
            d[i][j] = min(a_path,b_path)

ans = [0]
for i in range(N+1):
    ans += d[i]
c = Counter(ans)
for k in range(1,N): 
    print(c[k])

Submission status: Runtime Error

Solution code:
number_vertices, x, y = map(int, input().split())
connections = {}
for i in range(1, number_vertices+1):
    next_vertices = []
    if i != 1:
        next_vertices.append(i-1)
    if i != number_vertices:
        next_vertices.append(i+1)
    connections[i] = next_vertices
connections[x].append(y)
connections[y].append(x)


def count_distance(v_i, k, history):
    if k == 1:
        return len(set(connections[v_i]) - history)
    else:
        nexts = list(set(connections[v_i]) - history)
        sum_count = 0
        for v_n in nexts:
            h = history.copy()
            h.add(v_i)
            sum_count += count_distance(v_n, k-1, h)
        return sum_count


print(number_vertices)  # k=1の出力
for k in range(2, number_vertices):  # k=2, N-1まで
    count = 0
    print(f'{k=}')
    for i in range(1, number_vertices+1):
        print(f'{i=}')
        count += count_distance(i, k, set())
        print(f'{count=}')
    print(count)

Submission status: Runtime Error

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

ans=[0]*n

def func2(np, nd, state):
    #print(np, nd, state)
    nxp=[]
    for p in np:
        if p > 0 and not state[p-1]:
            nxp.append(p-1)
            ans[nd]+=1
        if p < n-1 and not state[p+1]:
            nxp.append(p+1)
            ans[nd]+=1
        if p == x-1 and not state[y-1]:
            nxp.append(y-1)
            ans[nd]+=1
        if p == y-1 and not state[x-1]:
            nxp.append(x-1)
            ans[nd]+=1
#    if nd == 1:
#        print(nd, nxp)

    nxp=list(set(nxp))
    for i in nxp:
        state[i]=True
    if len(nxp) == 0:
        return
    else:
        func2(nxp, nd+1, state)

for i in range(n):
    st=[False]*n
    st[i]=True
    func2([i], 0, st)

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

Submission status: Runtime Error

Solution code:
N, X, Y = map(int, input().split(' '))
distance = [] * N - 1
for i in range(N-1):
  for j in range(1, N):
    if i >= Y or j <= X:
      distance[j - i] += 1
    elif i <= X and j >= Y:
      distance[j - Y + X - i] += 1
    else:
      distance[j-Y + X-i] += 1

for d in distance:
  print(d)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

#a = cmb(n, r)

N, X, Y = map(int, input().split())
c = cmb(N, 2)
#A = [0 for i in range(c)]
#A = [[0 for i in range(2)] for j in range(c)]
#A[0][1] = 1
A = []
#print(A)


for i in range(N):
	for j in range(N):
		if j > i:
			A.append(j-i)

for i in range(N):
	for j in range(N):
		if range(X,Y) in range(i,j):
			A[i][j] = A[i][j] - (Y-X -1)

for i in range(N):
	for j in range(N):
		print(A[i][j])

"""
for i in range(c):
	for j in range(2):
		if i > j:
			A[i][j] = i - j
"""

"""
for i in range(2):
	for j in range(c):
		if j == (i+1):
			A[i][j] = 1
"""

Submission status: Runtime Error

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 = int(input())
n,x,y = map(int,input().split())
# A = list(map(int,input().split()))
# An = [list(map(int,input().split())) for i in range(n)]
l = np.zeros((n,n))
l[0][1] = 1
l[n-1][n-2] = 1
l[x-1][y-1] = 1
l[y-1][x-1] = 1
for i in range(n-3):
    l[i+1][i] = 1
    l[i+1][i+2] = 1

for i in range(n-1):
    print(np.count_nonzero(shortest_path(l)==j))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

INF = int(1e9+7)


OPEN = 1
CLOSE = 0

class State:
    def __init__(self, v, p, g, kind = OPEN):
        self.v = v         
        self.p = p         
        if p is None:
            self.d = 0     
        else:
            self.d = p.d + dt[p.v][v]
        self.cost = self.d + 1
        self.kind = kind

    def __cmp__(x, y):
        return x.cost - y.cost

def make_path_astar(state):
    path = []
    while state is not None:
        path.append(state.v)
        state = state.p
    return path

def a_star_search(start, goal, size):
    q = deque()
    visited = [None] * size
    a = State(start, None, goal)
    q.push(a)
    visited[start] = a
    while not q.isEmpty():
        a = q.pop()
        if a.kind == CLOSE: continue
        for x in adj[a.v]:
            b = visited[x]
            if b:
                l = a.d + dt[a.v][x]
                if b.d > l:
                    if b.kind == OPEN:
                        b.kind = CLOSE        
                        b = State(x, a, goal) 
                        visited[x] = b        
                    else:
                        b.p = a
                        b.d = l
                        b.cost = b.d + 1
                        b.kind = OPEN
                    q.push(b)
            else:
                b = State(x, a, goal)
                if x == goal:
                    return make_path_astar(b)
                q.push(b)
                visited[x] = b
        a.kind = CLOSE

def main():
    n, x, y = na()
    cost = [[INF for i in range(n)] for i in range(n)] 
    for i in range(n-1):
        cost[i][i+1] = 1
        cost[i+1][i] = 1
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1

    kyo = 1
    for i in range(n):
        for j in range(n):
            print(a_star_search(i, j, kyo))
        kyo += 1


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

tri=y-x+1
linear=x+N-y+1

nl=[0]*(N-1)
# triangle is gusu
if tri%2==0:
    # triangle
    for i in range(tri//2-1):
        nl[i]+=tri

    nl[i+1]+=tri//2

    # before,x,y,after
    for i in range(linear-1):
        if i==0:
            nl[i]+=min(0,linear-(i+1)-1)
        else:
            nl[i]+=linear-(i+1)
    
    # before,tri
    half_tri=(tri-2)//2
    mind=min(x-1,half_tri)
    maxd=max(x-1,half_tri)
    for i in range(mind+2,maxd+2):
        nl[i]+=mind
    for i in range(mind+3,maxd+3):
        nl[i]+=mind

    mind=min(N-y,half_tri)
    maxd=max(N-y,half_tri)
    for i in range(mind+2,maxd+2):
        nl[i]+=mind
    for i in range(mind+3,maxd+3):
        nl[i]+=mind

elif tri%2==1:
    # triangle
    for i in range(tri//2):
        nl[i]+=tri

    # before,x,y,after
    for i in range(linear-1):
        if i==0:
            nl[i]+=min(0,linear-(i+1)-1)
        else:
            nl[i]+=linear-(i+1)
    
    # before,tri
    half_tri=(tri-2)//2
    mind=min(x-1,half_tri)
    maxd=max(x-1,half_tri)
    for i in range(mind+2,maxd+2):
        nl[i]+=mind
    
    half_tri=min(0,half_tri-1)
    mind=min(x-1,half_tri)
    maxd=max(x-1,half_tri)
    for i in range(mind+3,maxd+3):
        nl[i]+=mind

    mind=min(N-y,half_tri)
    maxd=max(N-y,half_tri)
    for i in range(mind+2,maxd+2):
        nl[i]+=mind

    half_tri-=1
    mind=min(N-y,half_tri)
    maxd=max(N-y,half_tri)
    for i in range(mind+3,maxd+3):
        nl[i]+=mind

for s in nl:
    print(s)

Submission status: Runtime Error

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

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

E = []
for i in range(n-1):
    E.append([i,i+1,1])
E.append([X-1,Y-1,1])

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    for e in E:
        x,y,z = map(int,e)
        edge[x].append([z,y])
        edge[y].append([z,x])

for i in range(1,n):
    cnt = 0
    for j in range(n):
        tmp = dijkstra_heap(j,edge)
        for t in tmp[j:]:
            if t==i:
                cnt += 1
    print(cnt)

Submission status: Runtime Error

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

def f(l, k):
  if l+1 <= k:
    return 0
  else:
    return l-k+1

def g(l, k):
  if l < 2*k:
    return 0
  elif l==2*k:
    return l/2
  else:
    return l

def h(l, m, k):
  M = 0
  for i in range(1,k):
    if i<=l:
      M += g(m,k-i)*2/m
  return M

A=[n]
for i in range(2, n):
  c=f(n+x-y,k)+g(y-x+1,k)+h(x-1,y-x+1,k)+h(n-y,y-x+1,k)
  A.append(c)
for i in range(n-1):
  print(A[i])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

INF = int(1e9+7)


OPEN = 1
CLOSE = 0

class State:
    def __init__(self, v, p, g, kind = OPEN):
        self.v = v         
        self.p = p         
        if p is None:
            self.d = 0     
        else:
            self.d = p.d + dt[p.v][v]
        self.cost = self.d + 1
        self.kind = kind

    def __cmp__(x, y):
        return x.cost - y.cost

def make_path_astar(state):
    path = []
    while state is not None:
        path.append(state.v)
        state = state.p
    return path

def a_star_search(start, goal, size):
    q = deque.deque()
    visited = [None] * size
    a = State(start, None, goal)
    q.push(a)
    visited[start] = a
    while not q.isEmpty():
        a = q.pop()
        if a.kind == CLOSE: continue
        for x in adj[a.v]:
            b = visited[x]
            if b:
                l = a.d + dt[a.v][x]
                if b.d > l:
                    if b.kind == OPEN:
                        b.kind = CLOSE        
                        b = State(x, a, goal) 
                        visited[x] = b        
                    else:
                        b.p = a
                        b.d = l
                        b.cost = b.d + 1
                        b.kind = OPEN
                    q.push(b)
            else:
                b = State(x, a, goal)
                if x == goal:
                    return make_path_astar(b)
                q.push(b)
                visited[x] = b
        a.kind = CLOSE

def main():
    n, x, y = na()
    cost = [[INF for i in range(n)] for i in range(n)] 
    for i in range(n-1):
        cost[i][i+1] = 1
        cost[i+1][i] = 1
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1

    kyo = 1
    for i in range(n):
        for j in range(n):
            print(a_star_search(i, j, kyo))
        kyo += 1


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, X, Y = list(map(int, input().split()))
table = [[0 for i in range(N)] for j in range(N)]

for i in range(N):
    for j in range(i, N):
        table[i][j] = j-i
#print(table)

dif = Y-X-1
#print('dif', dif)

for i in range(0, X):
    for j in range(Y-1, N):
        table[i][j] -= dif
#print(table)

for i in range(0, X):
    for j in range(Y-1, 0, -1):
        #print('j',j)
        if table[i][j] < table[i][j-1]-1:
            #print('j-1', j-1)
            table[i][j-1] = 1+table[i][j]

for i in range(Y-1, N):
    for j in range(X-1, N-1):
        #print('j',j)
        if table[j][i] < table[j+1][i]-1:
            #print('j+1', j+1)
            table[j+1][i] = 1+table[j][i]
#print(table)

cnt = collections.Counter(str(table))

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

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.sparse
N,X,Y = (int(x) for x in input().split())
lil = scipy.sparse.lil_matrix((N, N), dtype=int)
for i in range(N-1):
    lil[i, i+1] = 1
    lil[i+1, i] = 1
lil[X, Y] = 1
lil[Y, X] = 1
shortest = scipy.sparse.csgraph.floyd_warshall(lil)
for i in range(N-1):
    print(np.count_nonzero(shortest == i))

Submission status: Runtime Error

Solution code:
N, X, Y = list(map(int, input().split()))
table = [[0 for i in range(N)] for j in range(N)]

for i in range(N):
    for j in range(i, N):
        table[i][j] = j-i
print(table)

dif = Y-X-1
print('dif', dif)

for i in range(0, X):
    for j in range(Y-1, N):
        table[i][j] -= dif
print(table)

for i in range(0, X):
    for j in range(Y-1, 0, -1):
        #print('j',j)
        if table[i][j] < table[i][j-1]-1:
            #print('j-1', j-1)
            table[i][j-1] = 1+table[i][j]

for i in range(Y-1, N):
    for j in range(X-1, N-1):
        #print('j',j)
        if table[j][i] < table[j+1][i]-1:
            print('j+1', j+1)
            table[j+1][i] = 1+table[j][i]
print(table)

cnt = collections.Counter(str(table))

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

Submission status: Runtime Error

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

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

E = []
for i in range(n-1):
    E.append([i,i+1,1])
E.append([X-1,Y-1,1])

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    for e in E:
        x,y,z = map(int,e)
        edge[x].append([z,y])
        edge[y].append([z,x])

for i in range(1,n):
    cnt = 0
    for j in range(n):
        tmp = dijkstra_heap(j)
        for t in tmp[j:]:
            if t==i:
                cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
from pprint import pprint
from collections import Counter
from functools import lru_cache

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

@lru_cache(maxsize=100000)
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

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

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

Submission status: Runtime Error

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

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

M = np.zeros((N,N))

for i in range(1,N):
    M[i-1][i] = 1
    M[i][i-1] = 1
    M[X-1][Y-1] = 1
    M[Y-1][X-1] = 1

M_diff = shortest_path(M)

for i in range(1,N):
    ans = 0
    for k in range(0,N):
        for l in range(0,N):
            if int(M_diff[k][l]) == i:
                ans += 1
    print(int(ans/2))

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
#from collections import OrderedDict
n, x, y = map(int, sys.stdin.readline().split())

#隣接グラフ
L = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(1, n):
    L[i][i+1] = 1
    L[i+1][i] = 1
L[x][y] = 1
L[y][x] = 1
#pprint.pprint(L)
dic = {}
def dfs(p, visit):
    for c in range(p+1, n+1):
        if L[p][c] !=0 and not c in visit:
            #print(c)
            dfs(c, visit+[c])
    #print(visit[0], visit[-1], len(visit)-1)
    if visit[0] !=visit[-1]:
        dic[(visit[0], visit[-1])] = len(visit)-1

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

ans = list(Counter(dic.values()).values())
for i in ans[::-1]:
    print(i)
print(0)

Submission status: Runtime Error

Solution code:
n,x,y=map(int,input().split())
adlist=[[1,2]]
for i in range(n-2):
    adlist.append([i+1,i+2,i+3])
adlist.append([n-1,n])

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


def dfs(start,count,goal,finish,ans):
    finish.add(start)#もう訪れたところ
   
   # print(finish)
    if count==goal:
        #print("DFGH")
        ans+=1
        #print(ans)
        count=0
    for i in adlist[start-1]:
        #print("DFG")
        if i not in finish:#通ったところに入っていないなら通れるということ   
            #print(i)
            dfs(i,count+1,goal,finish,ans)
    return ans

#print(adlist)
global ans
for i in range(1,n):
    
    ans=0
    finish=set()
    print(dfs(1,0,i,finish,0))

#print(adlist)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
n, x, y = map(int, input().split())
x -= 1
y -= 1
GRAPH = [[0]*n for _ in range(n)]
for i in range(n-1):
    GRAPH[i][i+1] = GRAPH[i+1][i] = 1
GRAPH[x][y] = GRAPH[y][x] = 1
G = csr_matrix(GRAPH)
sp = shortest_path(G)

ans = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        path = int(sp[i][j])-1
        ans[path] += 1
print(*ans, sep="\n")

Submission status: Runtime Error

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

import numpy as np
# N = 5
# X = 2
# Y = 4

dist = np.full(N*N, float("inf")).reshape((N, N))
np.fill_diagonal(dist, 0)
# np.fill_diagonal(dist[1:], 1)
np.fill_diagonal(dist[:, 1:], 1)
dist[X, Y] = 1
# dist[Y, X] = 1
for i in range(N):
    for j in range(i+1, N):
        for k in range(0, N):
            print(i, k, j, dist[i, k]+dist[k, j])
            dist[i, j] = min(dist[i, j], dist[i, k]+dist[k, j])
for i in range(1, N):
    count = np.count_nonzero(dist == i)
    print(count)

Submission status: Runtime Error

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

def warshall_floyd(d, n):
    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 main():
    N, X, Y = list(map(int, input().split()))
    
    d = [[0] * N for i in range(N)]
    for i in range(N - 1):
        d[i][i + 1] = 1
        d[i + 1][i] = 1
        # d[i][i] = 0
    # d[N - 1][N - 1] = 0

    d[X - 1][Y - 1] = 1
    d[Y - 1][X - 1] = 1
    d = np.array(d).astype(np.float)
    d = csr_matrix(d)

    d = shortest_path(d).astype(np.int)
    
    unique, counts = np.unique(d, return_counts=True)
    for i, c in zip(unique, counts):
        if not 0 <= i < N:
            print('0')
        else:
            print(c // 2)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

n = a
w = a #n:頂点数　w:辺の数

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

for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
    
warshall_floyd(d)

for i in range(1,n):
    ans = 0
    if i >= b + a - c + 1:
        print(ans)
        continue
    for j in range(n):
        ans += def[j].count(i)
    print(ans)

Submission status: Runtime Error

Solution code:

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


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


l = [[0] * n for _ in range(n)]

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

#print(l)
l = np.array(l)
ans = shortest_path(l)

dic = {}
for i in range(n):
    dic[i] = 0

for i in range(n):
    for j in range(i,n):
        keiro = int(ans[i][j])
        dic[keiro] += 1

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

Submission status: Runtime Error

Solution code:
#pragma region header
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
template <class T> ll size(const T& x) { return x.size(); }
#define rep(i,a,b) for(ll i = (a); i < (b); i++)
#define iter(it,c) for(auto it = (c).begin(); it != (c).end();++it)
#define pb push_back
#define fs first
#define sc second
#define MOD 1000000007;
#define MOD2 998244353;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
template <class T> T smod(T a, T b) {
	return (a % b + b) % b;
}

const int INF = ~(1 << 31);
const double pi = acos(-1);
const double EPS = 1e-9;

#pragma endregion

/*vector<int> edg[100100];
bool active[100100];
int depth[100100];
bool vis[100100];
bool print = false;
vector<int> ans;
void dfs(int at, int dep){
	if(vis[at]) return;
	if(print){
		ans.pb(at);
		return;
	}
	if(active[at] && dep-depth[at] >= 2){
		print = true;
		ans.pb(at);
		return;
	}
	depth[at] = dep;
	active[at] = true;
	vis[at] = true;
	rep(i,0,edg[at].size()){
		dfs(edg[at][i],dep+1);
	}
	active[at] = false;
}*/

vector<int> edg[300050];
bool vis[300050];
int dist[300050];

void bfs(int start) {
	memset(vis, 0, sizeof(vis));
	memset(dist, -1, sizeof(dist));
	queue<int> q;
	q.push(start);
	dist[start] = 0;
	vis[start] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		rep(i, 0, edg[cur].size()) {
			int nxt = edg[cur][i];
			if (!vis[nxt]) {
				vis[nxt] = true;
				dist[nxt] = dist[cur] + 1;
				q.push(nxt);
			}
		}
	}
}


int main() {
	ll n, x, y;
	cin >> n >> x >> y;
	rep(i, 0, n - 1)
	{
		edg[i].pb(i + 1);
		edg[i + 1].pb(i);
	}
	x--; y--;
	edg[x].pb(y);
	edg[y].pb(x);
	vi K(n);
	rep(i, 0, n)
	{
		bfs(i);
		rep(j, 0, n)
		{
			if (i == j) continue;
			K[dist[j]]++;
		}
	}
	rep(i, 1, n) cout << K[i]/2 << endl;
}

Submission status: Runtime Error

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

graph = [[False for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    graph[i][i+1] = graph[i+1][i] = True
graph[X-1][Y-1] = graph[Y-1][X-1] = True

ans = [0] * N

def dfs(pos, goal, cnt, visited):
    ans = N
    for i in range(N):
        if not graph[pos][i]: continue
        if visited[i]: continue

        if i == goal:
            return cnt + 1

        visited[i] = True
        ret = dfs(i, goal, cnt + 1, visited)
        if ret is not None:
            ans = min(ans, ret)
        visited[i] = False

    if ans == N:
        return None
    else:
        return ans

visited = [False] * N
for i in range(N):
    for j in range(i+1, N):
        distance = dfs(i, j, 0, visited)
        if distance is not None:
            ans[distance] += 1

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

Submission status: Runtime Error

Solution code:
#n = int(input())
n,x,y = map(int,input().split())
#a_L = list(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 = [[0] * n for _ in range(n)]

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

#print(l)
l = np.array(l)
ans = shortest_path(l)

dic = {}
for i in range(n):
    dic[i] = 0


for i in range(n):
    for j in range(i,n):
        keiro = int(ans[i][j])
        dic[keiro] += 1

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

Submission status: Runtime Error

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

def warshall_floyd(d, n):
    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 main():
    N, X, Y = list(map(int, input().split()))
    
    d = [[0] * N for i in range(N)]
    for i in range(N - 1):
        d[i][i + 1] = 1
        d[i + 1][i] = 1
        # d[i][i] = 0
    # d[N - 1][N - 1] = 0

    d[X - 1][Y - 1] = 1
    d[Y - 1][X - 1] = 1
    d = np.array(d).astype(np.float)

    d = shortest_path(d).astype(np.int)
    
    unique, counts = np.unique(d, return_counts=True)
    for i in unique:
        if not 0 <= i < N:
            print('0')
        else:
            print((d == i).sum() // 2)


if __name__ == "__main__":
    main()