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: Wrong Answer

Solution code:
N, X, Y = [int(n) for n in input().split()]
C = (X + Y + 1) / 2

ans = [0] * (N - 1)
for i in range(1,N):
    for j in range(i+1,N+1):
        if i <= X:
            if j < C:
                k = j - i
            elif j < Y:
                k = X - i + 1 + Y - j
            else:
                k = X - i + 1 + j - Y
        elif i <= Y:
            if j < Y:
                if j < i + C:
                    k = j - i
                else:
                    k = i - X + 1 + Y - j
            else:
                if i < (X + Y - 1) / 2:
                    k = i - X + 1 + j - Y
                else:
                    k = j - i
        else:
            k = j - i
        ans[k-1] += 1

print("\n".join([str(n) for n in ans]))

Submission status: Wrong Answer

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
5 2 4
'''

def solve(n,x,y):
	adj = [[] for i in range(n+1)]
	adj[x].append(y)
	adj[y].append(x)
	for i in range(1,n):
		adj[i].append(i+1)
		adj[i+1].append(i)
	# print(adj)
	ans = []
	d = {}
	for i in range(1,n):
		d[i] = 0
	for k in range(1,n+1):
		q = [k]
		dis = [maxsize]*(n+1)
		dis[k] = 0
		while(q):
			src = q.pop()
			for nn in adj[src]:
				if(nn > k or nn == X or nn == Y):
					if(dis[nn] > dis[src]+1):
						# if(src == 4):
							# print('src:',src,'nn:',nn)
						dis[nn] = dis[src] + 1
						q.append(nn)
				# else:
				# 	dis[nn] = 
			# if(k == 3):
			# 	print('src:',src)
			# 	print('dis:',dis)
		curr = 0
		# if(k == 3):
		# print('k:',k,dis)
		for ii in range(k+1,n+1):
			d[dis[ii]] += 1
	return d

N,X,Y = list(map(int, stdin.readline().rstrip().split()))
ans = solve(N,X,Y)
for i in range(1,N):
	print(ans[i])

Submission status: Wrong Answer

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)
      # その先は追加で探索
      elif u in [X-1, Y-1]:
        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: Wrong Answer

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

p = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if j<=X:
            p.append(j-i)
        elif j<=Y:
            if i <= X:
                p.append(min(j-i, X-i+1+Y-j))
            else:
                p.append(min(j-i, i-X+1+Y-j))
        else:
            if i <= X:
                p.append(j-i-(Y-X)+1)
            elif i <=Y:
                p.append(min(j-i, i-X+1+j-Y))
            else:
                p.append(j-i)

Submission status: Wrong Answer

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

ans = {}
for i in range(n-1):
  ans[i+1] = 0
  
for i in range(n):
  for j in range(i+1,n):
    if i <= x-i and j < x-1:
      t=j-i
      ans[t] += 1
    elif i <= x-1 and j >= x-1 and j <= y-1:
      t = min(j-i, (x-1)-i + 1 + (y-1) -j)
      ans[t] += 1
    elif i <= x-1 and j > y-1:
      t = (x-1)-i + 1 + j -(y-1)
      ans[t] += 1
    elif i > x-1 and i < y-1 and j < y-1:
      t = min(j-i, i-(x-1) + 1 + (y-1) -j)
      ans[t] += 1
    elif i > x-1 and i < y-1 and j >= y-1:
      t = min(j-i, i-(x-1) + 1 + j - (y-1))
      ans[t] += 1
    elif i >= y-1:
      t=j-i
      ans[t] += 1
    else:
      print("error")

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,X,Y = inputMap()
	g2 = Graph()

	for i in range(N):
		if i == 0:
			continue

		g2.add_edge(i-1, i, 1)
		#if i >= X:
			#g2.add_edge(i, i-1, 1)

	g2.add_edge(X-1, Y-1, 1)
	#g2.add_edge(Y-1, X-1, 1)

	for i in range(1,N):
		if i == 1:
			print(N)
			continue
		if i == N-1:
			print(0)
			continue

		ans2 = 0
		ans = []
		for ii in range(N):
			d2 = Dijkstra(g2, ii)
			for jj in range(N):
				if ii >= jj:
					continue
				tmp2 = d2.shortest_distance(jj)

				if tmp2 == i:
					if (jj,ii) in ans:
						continue
					#print("{} {}".format(ii+1,jj+1))
					ans2 += 1
					ans.append((ii,jj))
		print(ans2)
		#print("{} {}".format(ans,ans2))





#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N,X,Y = [int(i.strip()) for i in input().split(' ')]
X = X-1
Y = Y - 1
diff = (Y-X-1)//2
result = [0]*N
for i in range(N):
    for j in range(i+1,N):
        if i <= X and j >= Y:
            dist = X-i + j - Y +1
        elif i <=X + diff  and j >= Y: 
            # print('A')
            dist = i-X + 1 + j - Y
        elif i <= X and j >= Y - diff:
            # print('B')
            # print(X,i,diff,1)
            dist = X - i + Y - j + 1
        elif i <= X + diff and j >= Y - diff:
            if 2*diff + 1 > j - i:
                dist = j - i
            else:
                dist = i-X + Y- j + 1
        else:
            dist = j - i
        # print(i,j,dist)
        result[dist-1] += 1

L = len(result) - 1
for i,j in enumerate(result):
    if not i == L:
        print(j)

Submission status: Wrong Answer

Solution code:
N,X,Y=map(int,input().split())
a=list(range(N))
b=a[:X]
c=a[Y-1:]
d=b+c

def routes(x):
    if len(b)-x < 0 and len(c)-x > 0:
        if len(d)-x<0:
            return len(a)-x
        else:
            return len(a)+len(d)-2*x
    elif len(b)-x < 0:
        return len(a)+len(c)+len(d)-x
    elif len(c)-x < 0:
        return len(a)+len(b)+len(d)-x
    else:
        return len(a)+len(b)+len(c)+len(d)

for i in range(N):
    print(routes(i+1))

Submission status: Wrong Answer

Solution code:
def min_distance(a,b,x,y):
  if a <= x and y <= b:
    # ショートカットをはさむ場合
    return (b-a - (y-x)+1)
  else:
    if x <= a and y <= b:
      # 左端がショートカットの中の場合
      s1 = b - a
      s2 = (a-x) + 1 + (b-y)
      if s1 < s2:
        # 順周り
        return s1
      else:
        # 戻って
        return s2
    elif a <= x and b <= y:
    # ショートカットの中の場合
      s1 = (b-a)
      s2 = (x-a) + 1 + (y-b)
      if s1 < s2:
        return s1
      else:
        return s2
    else:
      return (b-a)
nxy = input('').split(' ')
n = int(nxy[0])
x = int(nxy[1])
y = int(nxy[2])

for k in range(1,n):
  cnt = 0
  for i in range(1,n+1):
    for j in range(i+1,n+1):
      s = min_distance(i,j,x,y)
      if s == k:
        print("{} {}:{} -> {}".format(k,i,j,s))
        cnt+=1
  print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
n, x, y = map(int, input().split())

neighbor = np.array([[0] * n for _ in range(n)])

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

dist = shortest_path(neighbor)
d = [0] * (n)
for i in range(n):
    for j in range(n):
        if dist[i][j] < 10**3 and dist[i][j] != 0:
            d[int(dist[i][j])] += 1
for i in range(len(d)):
    if i == 0:
        continue
    print(d[i])

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np
from collections import Counter

N, X, Y = map(int, input().split())
F = [[0 for i in range(N)] for j in range(N)]

for i in range(N - 1):
    F[i][i + 1] = 1
    F[i + 1][i] = 1
F[X - 1][Y - 1] = 1
F[Y - 1][X - 1] = 1

G = csgraph_from_dense(F, null_value=0)
d = dijkstra(G)

# print(F)
# print(d)

# print(np.count_nonzero(d == 1))
s = Counter(d.flatten().astype(np.int64))
print(s)
for i in range(1, N):
    if i in s:
        print(s[i] // 2)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
N,X,Y = [int(i.strip()) for i in input().split(' ')]
X = X-1
Y = Y - 1
diff = (Y-X-1)//2
result = [0]*N
for i in range(N):
    for j in range(i+1,N):
        if i <= X and j >= Y:
            dist = X-i + j - Y +1
        elif i <=X + diff  and j >= Y: 
            # print('A')
            dist = i-X + 1 + j - Y
        elif i <= X and j >= Y - diff:
            # print('B')
            # print(X,i,diff,1)
            dist = X - i + Y - j + 1
        elif i <= X + diff and j >= Y - diff:
            if 2*diff + 1 > j - i:
                dist = j - i
            else:
                dist = 2*diff + 1
        else:
            dist = j - i
        # print(i,j,dist)
        result[dist-1] += 1

L = len(result) - 1
for i,j in enumerate(result):
    if not i == L:
        print(j)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,X,Y = inputMap()
	g = Graph()
	g2 = Graph()

	for i in range(N):
		if i == 0:
			continue

		g2.add_edge(i-1, i, 1)
		g.add_edge(i, i-1, 1)
		#if i >= X:
			#g.add_edge(i, i-1, 1)

	g2.add_edge(X-1, Y-1, 1)
	g.add_edge(Y-1, X-1, 1)

	for i in range(1,N):
		if i == 1:
			print(N)
			continue
		if i == N-1:
			print(0)
			continue

		ans2 = 0
		ans4 = 0
		ans = []
		for ii in range(N):
			d2 = Dijkstra(g2, ii)
			d4 = Dijkstra(g, ii)
			for jj in range(N):
				if ii == jj:
					continue
				tmp2 = d2.shortest_distance(jj)
				tmp4 = d4.shortest_distance(jj)
				#print(tmp4)

				if tmp2 == i:
					if (jj,ii) in ans:
						continue
					#print("{} {}".format(ii+1,jj+1))
					ans2 += 1
					ans.append((ii,jj))
				if tmp4 == i:
					if (jj,ii) in ans:
						continue
					#print("{} {}".format(ii+1,jj+1))
					ans4 += 1
					ans.append((ii,jj))
					#print("dddd")
		print(ans2+ans4)
		#print("{} {}".format(ans,ans2))





#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

def check(i, j):
    a = j-i
    short = abs(x-i) + 1 + abs(j-y)
    if a==short:
        ans[a-1] += 2
    else:
        mini = min(a, short)
        ans[mini-1] += 1
for i in range(1, n):
    for j in range(i+1, n+1):
        check(i,j)


print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np
n, x, y = map(int, input().split())
if x==1 and y==n:
    for i in range(1, n//2+1):
        print(n-(i-1))
    for i in range(n//2+1, n):
        print(0)
else:
    a = np.array([[1 if j==i+1 or j==i-1 else 0 for j in range(n)] for i in range(n)])
    a[x-1, y-1] = 1
    a[y-1, x-1] = 1
    b = shortest_path(a).astype(np.int32)
    c = [b[i][j] for i in range(n) for j in range(n) if j>i]
    for i in range(1, n):
        print(c.count(i))

Submission status: Wrong Answer

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

ans = {}
for i in range(n-1):
  ans[i+1] = 0
  
for i in range(n):
  for j in range(i+1,n):
    if i <= x-i and j < x-1:
      t=j-i
      ans[t] += 1
    elif i <= x-1 and j >= x-1 and j <= y-1:
      t = min(j-i, (x-1)-i + 1 + (y-1) -j)
      ans[t] += 1
    elif i <= x-1 and j > y-1:
      t = (x-1)-i + 1 + j -(y-1)
      ans[t] += 1
    elif i > x-1 and i < y-1 and j < y-1:
      t=j-i
      ans[t] += 1
    elif i > x-1 and i < y-1 and j >= y-1:
      t = min(j-i, i-(x-1) + 1 + j - (y-1))
      ans[t] += 1
    else: #i >= y-1:
      t=j-i
      ans[t] += 1
    #else:
      #print("error")

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

Submission status: Wrong Answer

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

result = [0] * n
for i in range(n):
    for j in range(i, n, 1):
        if i == j:
            continue
        if i <= x:
            if j <= x:
                result[(j - i - 1)] += 1 # 普通に+1
            elif x < j and j <= y:
                minij = min([(j - i - 1), ((x - i + 1) + (y - j) - 1)])
                result[minij] += 1
            elif y < j:
                minij = min([(j - i - 1), ((x - i + 1) + (j - y) - 1)])
                result[minij] += 1
        elif x < i and i <= y:
            if x < j and j <= y:
                result[(j - i - 1)] += 1 # 普通に+1
            elif y < j:
                minij = min([(j - i - 1), ((i - x + 1) + (j - y) - 1)])
                result[minij] += 1
        elif y < i:
            result[(j - i - 1)] += 1  # 普通に+1
for i in range(n-1):
    print(result[i])

Submission status: Wrong Answer

Solution code:
import collections
from collections import deque

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

#辺のリスト
n = N
l_hen = [[i,i+1] for i in range(1,n)]+[[X,Y]]

#頂点のラベルリスト
l_chouten =list( set(sum(l_hen, [])) )

#G={頂点:[頂点に繋がっている点たち],... } を取得する
G = dict( [ (key,[]) for key in l_chouten]  )
for i in range(n):
   G[l_hen[i][0]].append(l_hen[i][1])

#無効グラフの場合両方から見ているので以下のコードも実行する
for i in range(n):
   G[l_hen[i][1]].append(l_hen[i][0])

'''
以上グラフの準備
'''
#seenとtodoの初期設定
l_seen = {i:False for i in l_chouten}
l_todo = []
dist = {i:-1 for i in l_chouten}
#距離の羅列用  
l_d =deque([])  

for point in range(1,N+1):
  #seenとtodoの初期設定
  for key in l_seen:
    l_seen[key] = 0
  l_todo = []  
  for key in dist:
    dist[key] = 0

  #seenに出発地点pを決めてやる、出発点の隣接リストもtodoに入れる
  p = point
  l_seen[p] = True #pはチェック済み
  for i in G[p]:
    l_seen[i] = True #pに隣接する頂点もチェック済み
  l_todo = l_todo + G[p] #pに隣接する頂点をtodoリストに追加
  l_todo = deque(l_todo)
  dist[p] = 0
  for i in G[p]:
    dist[i] = 1 #pに隣接する頂点とpとの距離を1とする
    l_d.append(dist[i])
  

  #探索
  while len(l_todo) != 0:
    #幅優先探索
    v = l_todo.popleft() #todoの左端つまりindex0から処理しているので
    for i in G[v]:
      #回り込まれて先越された時
      if l_seen[i] == True:
        if dist[i]==dist[v]+1:
          l_d.append(dist[i])
        else:
          continue
      else:
        l_seen[i] = True
        l_todo.append(i)
        dist[i]=dist[v]+1
        l_d.append(dist[i])
###
c = collections.Counter(l_d)
for i in range(1,N):
  print(c[i]//2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import shortest_path
import numpy as np

NXY = input().split()
N = int(NXY[0])
X = int(NXY[1])
Y = int(NXY[2])

adj_matrix = np.zeros((N,N))
for i in range(N-1):
    adj_matrix[i,i+1] = 1

adj_matrix[X-1,Y-1] = 1
result = np.ravel(shortest_path(adj_matrix))
for i in range(1,N):
    print(np.count_nonzero(result == i))

Submission status: Wrong Answer

Solution code:
N, X, Y = [int(n) for n in input().split()]
C = (X + Y + 1) / 2

ans = [0] * (N - 1)
debug = [[] for n in range(N-1)]
for i in range(1,N):
    for j in range(i+1,N+1):
        if i <= X:
            if j < C:
                k = j - i
            elif j < Y:
                k = X - i + 1 + Y - j
            else:
                k = X - i + 1 + j - Y
        elif i < Y:
            if j < Y:
                if j < i + C:
                    k = j - i
                else:
                    k = i - X + 1 + Y - j
            else:
                if i < (X + Y - 1) / 2:
                    k = i - X + 1 + j - Y
                else:
                    k = j - i
        else:
            k = j - i
        ans[k-1] += 1
        debug[k-1].append((i,j))

print("\n".join([str(n) for n in ans]))

Submission status: Wrong Answer

Solution code:
N,x,y = [int(a) for a in input().split()]
print(N)

l = y-x

for i in range(2,N):
  ans = N- (i+1)+1
  if (i < l):
  	ans+= 1
  elif (i == l):
    ans-= 1
  elif (l < i):
    ans-= 1
  if ((x-1) == i - 1):
    ans += 1
  if(N-y == i - 1):
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, X, Y = map(int, input().split())
K = Y - X
ans = np.zeros(N-1,dtype = int)
for i in range(X-1):
  ans[i] += X-i-1
for i in range(N-Y-1):
  ans[i] += N-Y-i-1
for i in range(1,N):
  for j in range(i+1, N):
    if i <=  X and  X < j <= Y:
      tmp = min(j-i,Y-j + 1 + X -i)
      ans[tmp-1] += 1
    elif i <= X and j > Y:
      ans[j-Y + X - i] += 1
    elif X < i and i<= Y:
      tmp = min(j-i, i-X + 1 + abs(j-Y))
      ans[tmp-1] += 1
for i in range(N-1):
  print(ans[i])

Submission status: Wrong Answer

Solution code:


n,x1,y1 = map(int,input().split())
x = min(x1,y1)
y = max(x1,y1)

def ans(k):
    c = 0
    for i in range(1,x):
        if (y-x+1)/2.==k-i and k-i>0:
            c+=1
        elif (y-x+1)//2 >= k-i and k-i>0:
            c+=2

    # print(c)

    for i in range(1,n-y+1):
        if (y-x+1)/2.==k-i and k-i>0:
            c+=1
        elif (y-x+1)//2 >= k-i and k-i>0:
            c+=2

    # print(c)

    c+= (n-y+x+1-k)

    # print(c)

    if (y-x +1)/2. == k:
        c += k
    elif (y-x+1)//2 >=k:
        c += y-x+1
    # print(c)
    if x-1 >= k-1 and c>0:
        c-=1
    if n-y >= k-1 and c>0:
        c-=1
    # print(c)
    if c<0: return 0

    return c+1 if k==1 else c
    # return c


for k in range(n-1):
    print(ans(k+1))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def update_distance(d, num, N):
    minn = num
    maxx = num
    # 要素数の小さい方に向けて
    while True:
        if minn > 0:
            minn -= 1
        else:
            break
        if d[minn] > d[minn+1] + 1:
            d[minn] = d[minn+1] + 1
        else:
            break
    # 要素数の大きいほうに向けて
    while True:
        if maxx < (N - 1):
            maxx += 1
        else:
            break
        if d[maxx] > d[maxx-1] + 1:
            d[maxx] = d[maxx-1] + 1
        else:
            break

(N, X, Y) = (int(i) for i in input().split())
X = X-1
Y = Y-1

# まずは経路情報をd[N][N]の二次元配列に格納
# (i, j)がつながっていれば1, つながってなければ2*10^3

d = []
for i in range(N):
    dd = []
    for j in range(N):
        dd.append(abs(i - j))
    d.append(dd)

# XとYがつながることで最短経路を修正していく
for i in range(N):
    dd = d[i]
    dd[X] = min(dd[X], dd[Y] + 1)
    dd[Y] = min(dd[Y], dd[X] + 1)
    update_distance(dd, X, N)
    update_distance(dd, Y, N)
print(d)

# dの全リストを連結してあとは0~N-1までカウントする
d_list = []
for i in range(N - 1):
    d_list += d[i][i+1:]

#print(d_list)

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

Submission status: Wrong Answer

Solution code:
N,X,Y = [int(i.strip()) for i in input().split(' ')]
X = X-1
Y = Y - 1
diff = (Y-X-1)//2
print(diff)
result = [0]*N
for i in range(N):
    for j in range(i+1,N):
        if i <= X and j >= Y:
            dist = X-i + j - Y +1
        elif i <=X + diff  and j >= Y: 
            # print('A')
            dist = diff + 1 + j - Y
        elif i <= X and j >= Y - diff:
            # print('B')
            # print(X,i,diff,1)
            dist = X - i + Y - j + 1
        elif i <= X + diff and j >= Y - diff:
            if 2*diff + 1 > j - i:
                dist = j - i
            else:
                dist = 2*diff + 1
        else:
            dist = j - i
        # print(i,j,dist)
        result[dist-1] += 1

L = len(result) - 1
for i,j in enumerate(result):
    if not i == L:
        print(j)