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=map(int, raw_input().split())

tb=[[0]*(n+1) for i in xrange(n+1)]
tb[x][y]=1
for i in xrange(1, n+1):
    for j in xrange(i+1,n+1):
        # if i<=x and j==y:
        #     tb[i][j]=min(tb[i][j-1]+1-(y-x)+1, j-i)
        # elif i>x and i<y and j==y:
        #     tb[i][j]=min(j-i, j-x+1)
        # else:
        #     tb[i][j]=min(tb[i][j-1]+1, j-i)
        if i<x:
            # print i,j, x-i+1+abs(y-j)
            tb[i][j]=min(j-i, x-i+1+abs(y-j))
        elif i>=x and i<=y:
            tb[i][j]=min(j-i, i-x+1+abs(y-j))

res=[0]*(n+1)

for i in xrange(1 ,n+1):
    for j in xrange(i+1, n+1):
        res[tb[i][j]]+=1

s=''
for i in xrange(1, n):
    s+=str(res[i])+'\n' 

# for i in tb:
#     print i
print s

Submission status: Wrong Answer

Solution code:
n, x, y = map(int, input().split())
king_li = []
for i in range(1, n+1):
    for j in range(i+1,n+1):
        li = []
        if i > x:
            if j<y:
                d = j-i
            else:
                li.append(i-x+1+j-y)
                li.append(j-i)
                d = min(li)
        else:
            if j<y:
                li.append(y-j+1+x-i)
                li.append(j-i)
                d = min(li)
            else:
                d = x-i+j-y+1
        king_li.append(d)
for z in range(1,n):
    print(king_li.count(z))

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
		if i == N-2:
			print(0)
			continue
		if i == N-3:
			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:
def main():
    n,x,y = tuple([int(t)for t in input().split()])
    x -=1
    y -=1
    dmin = [[n]*n for _ in [0]*n]

    nlist = list(range(n))

    for i in range(n):
        for j in range(i,n):
            dmin[i][j] = j-i
            dmin[j][i] = j-i
    
    check = []
    check.extend(nlist[:x+1])
    check.extend(nlist[y:])


    for i in range(len(check)):
        for j in range(i,len(check)):
            dmin[check[i]][check[j]] = dmin[check[i]][check[j]]  if j-i>dmin[check[i]][check[j]] else j-i
            dmin[check[j]][check[i]] = dmin[check[i]][check[j]]  if j-i>dmin[check[i]][check[j]] else j-i

    check = []
    check.extend(nlist[y-1:x-1:-1])
    check.extend(nlist[y:])


    for i in range(len(check)):
        for j in range(i,len(check)):
            dmin[check[i]][check[j]] = dmin[check[i]][check[j]]  if j-i>dmin[check[i]][check[j]] else j-i
            dmin[check[j]][check[i]] = dmin[check[i]][check[j]]  if j-i>dmin[check[i]][check[j]] else j-i

    check = []
    check.extend(nlist[x+1:y+1])
    check.extend(nlist[x::-1])

    for i in range(len(check)):
        for j in range(i,len(check)):
            dmin[check[i]][check[j]] = dmin[check[i]][check[j]]  if j-i>dmin[check[i]][check[j]] else j-i
            dmin[check[j]][check[i]] = dmin[check[i]][check[j]]  if j-i>dmin[check[i]][check[j]] else j-i


    for i in range(1,n):
        t = sum(l.count(i) for l in dmin)
        print(t//2)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,x,y=map(int,input().split())
a=x-1 #Xより左側
b=y-x-1 #XとYの間
c=n-y #Yより右側

ans=0
ans+=a+c+1 #X,Yもカウント
ans+=b+1
print(ans)

for i in range(2,n):
    ans=0
    if i<a+c+2: #aとc(X,Yもカウント)
        ans+=a+c+2-i
    if i<(b+2)//2+a+1 and a>0: #aとb
        if i-1<=a:
            ans+=min(i-1,(b+2)//2)*2-1
        else:
            ans+=min((b+2)//2+a-i+1,a)*2
    if i<(b+2)//2+c+1 and c>0: #bとc
        if i-1<=c:
            ans+=min(i-1,(b+2)//2)*2-1
        else:
            ans+=min((b+2)//2+c-i+1,c)*2
    if i<=(b+2)//2: #bとb(X,Yもカウント)
        if i==(b+2)/2:
            ans+=(b+2)//2
        else:
            ans+=b+2
    print(ans)

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
    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
		if i == N-2:
			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 = map(int, input().split())

#N <=2*10**3
#総当たりはN*(N-1) = 4*10**6　間に合う

ans_dict = {i:0 for i in range(1,N+1)}

for i in range(1,N+1):
    for j in range(i+1,N+1):
        #print(i,j)
        #ストレートで行くパターン
        straight = j - i
        #XYを経由するパターン
        throught_XY = min(abs(X-i),abs(Y-i)) + min(abs(X-j),abs(Y-j)) + 1
        
        distance = min(straight,throught_XY)
        
        ans_dict[distance] += 1
        
#デフォルトの距離x毎の値はN-x
        
for i in range(1,N+1):
    print(ans_dict[i])

Submission status: Wrong Answer

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

tb=[[0]*(n+1) for i in xrange(n+1)]
tb[x][y]=1
for i in xrange(1, n+1):
    for j in xrange(i+1,n+1):
        # if i<=x and j==y:
        #     tb[i][j]=min(tb[i][j-1]+1-(y-x)+1, j-i)
        # elif i>x and i<y and j==y:
        #     tb[i][j]=min(j-i, j-x+1)
        # else:
        #     tb[i][j]=min(tb[i][j-1]+1, j-i)
        if i<x:
            print i,j, x-i+1+abs(y-j)
            tb[i][j]=min(j-i, x-i+1+abs(y-j))
        elif i>=x and i<=y:
            tb[i][j]=min(j-i, i-x+1+abs(y-j))

res=[0]*(n+1)

for i in xrange(1 ,n+1):
    for j in xrange(i+1, n+1):
        res[tb[i][j]]+=1

s=''
for i in xrange(1, n):
    s+=str(res[i])+'\n' 

for i in tb:
    print i
print s

Submission status: Wrong Answer

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

dist_map = []
for i in range(N):
    dist_map.append([0 for _ in range(N)])

result = [0 for _ in range(N-1)]
for i in range(N-1):
    for j in range(i+1, N):
        if i <= X-1 and j == Y-1:
            dist_map[i][j] = dist_map[i][X-1] + 1
            result[0] += 1
            # print(str(dist_map[i][j]))
        else:
            dist_map[i][j] = dist_map[i][j-1] + 1
            result[dist_map[i][j]-1] += 1
            # print(str(dist_map[i][j]))

print('\n'.join(list(map(str, result))))

Submission status: Wrong Answer

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

# x, yを使うルート＋飛ばされたところを含むルート
# x, yを使った場合の端から端の距離
dis_xy = n - (y - x) + 1
# x,y間の数aについて、xに近い点数、yに近い点数、等距離の点数を計算
near_x = (y - x - 1) // 2
near_y = (y - x - 1) // 2
equal_xy = (y - x - 1) % 2

for k in range(1, n):
    c_xy = max(0, dis_xy - k)
    tmp1 = max(0, near_x + 1 - k)
    tmp2 = max(0, min(near_x, x + near_x - k)) - tmp1
    tmp3 = max(0, min(near_x, (n - y + 2) + near_x - k)) - tmp1
    tmp4 = max(0, near_y + 1 - k)
    tmp5 = max(0, min(near_y, (n - y + 1) + near_y - k)) - tmp4
    tmp6 = max(0, min(near_y, (x + 1) + near_y - k)) - tmp4
    tmp7 = 0
    if equal_xy == 1:
        z = (x + y) // 2
        if z - k > 0:
            tmp7 += 1
        if (n - z + 1) - k > 0:
            tmp7 += 1
    tmp8 = 0
    if (y - x + 1) >= 2 * k:
        tmp8 = (y - x + 1) - tmp1 - tmp4
        if equal_xy == 1:
            if z - k >= x:
                tmp8 -= tmp7
        z = (x + y) // 2
        if (y - (z + 1) + 1) >= k:
            tmp8 -= 2
        tmp8 = max(0, tmp8)
    else:
        tmp8 = 0

    print(c_xy + tmp1 + tmp2 + tmp3 + tmp4 + tmp5 + tmp6 + tmp7 + tmp8)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections
from collections import defaultdict

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

skip_d = abs(X - Y)
d_count = defaultdict(lambda: 0)
d_table = []
for i in range(N):
    d_list = []
    for j in range(N):
        if i == j:
            d = 0
            d_count[d] += 1
            d_list.append(d)
            continue
        # Normal
        min_index = min(i, j)
        max_index = max(i, j)

        if min_index <= X - 1 and Y - 1 <= max_index:
            # 両方外にいる
            d = abs(i - j) - skip_d + 1
        elif X - 1 < max_index < Y - 1 and min_index <= X - 1:
            d_1 = abs(i - j)
            d_2 = (abs(min_index - (Y - 1)) - skip_d + 1) + abs((Y - 1) - max_index)
            d = min(d_1, d_2)
        elif X - 1 < min_index < Y - 1 and Y - 1 <= max_index:
            d_1 = abs(i - j)
            d_2 = (abs(max_index - (X - 1)) - skip_d + 1) + abs((X - 1) - min_index)
            d = min(d_1, d_2)
        else:
            d = abs(i - j)

        d_list.append(d)
        d_count[d] += 1
    d_table.append(d_list)

ans_s = []
for k in range(1, N):  # 2 * 10 ** 3
    c = d_count[k]
    c = c // 2
    ans_s.append(str(c))
ans = "\n".join(ans_s)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, Counter

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
d = defaultdict(int)
for i in range(N-1):
    for j in range(i+1, N):
        d[(i, j)] = j-i
for i in range(X+1):
    for j in range(Y, N):
        d[(i, j)] = X-i+1+j-Y
for i in range(X+1, X+Y//2):
    for j in range(Y, N):
        if d[(i, j)] > i-X+1+j-Y:
            d[(i, j)] = i-X+1+j-Y
for i in range(X+1):
    for j in range((X+Y)//2, Y):
        if d[(i, j)] > X-i+1+Y-j:
            d[(i, j)] = X-i+1+Y-j
cnt = defaultdict(int)
for i in range(N-1):
    for j in range(i+1, N):
        cnt[d[(i, j)]] += 1
for i in range(1, N):
    print(cnt[i])

Submission status: Wrong Answer

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

while k <= N-1:
  print(0)
  k += 1

Submission status: Wrong Answer

Solution code:
def main():
    n, x, y = map(int, input().split())
    # n, x, y = 7, 3, 7
    edge = [[] for _ in range(n+1)]
    dist = [[abs(i-j) for i in range(n+1)] for j in range(n+1)]
    counter = [0 for i in range(n)]
    for i in range(1, n):
        edge[i].append(i+1)
        edge[i+1].append(i)
    edge[x].append(y)
    edge[y].append(x)
    # print(edge)
    for i in range(x):
        for j in range(y, n+1):
            dist[i][j] = j-y + x-i +1
            dist[j][i] = j-y + x-i +1
    for i in range(x, x+(y-x)//2):
        for j in range(y, n+1):
            dist[i][j] = j-y + i-x + 1
            dist[j][i] = j-y + i-x + 1
    for i in range(x):
        for j in range(y-(y-x)//2+1, y):
            dist[i][j] = y-j + x-i + 1
            dist[j][i] = y-j + x-i + 1
    for i in range(x, x+(y-x)//4):
        for j in range(y-(y-x)//4, y):
            dist[i][j] = y-j + i-x + 1
            dist[j][i] = y-j + i-x + 1

    for i in range(1, n+1):
        for num in dist[i][1:]:
            counter[num] += 1
    # print(dist)

    for num in counter[1:]:
        print(num//2)
    
if __name__=='__main__':
    # import time
    # start = time.time()
    main()
    # print(f"{time.time()-start}[s]")

Submission status: Wrong Answer

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

left_range = [1,X]
right_range = [Y, N]
mid_range = [X+1, Y-1]
width = Y - X


for k in range(1, N):
    if k > N - 1 - (Y - X - 1):
        print(0)
    else:
        left_n = (left_range[1] + width -1  - left_range[0] + 1) - k
        right_n = (right_range[1] - (right_range[0] - width+ 1) + 1 ) - k
        mid_n = (N - width +1 ) -k
        ret = 0
        if k <= X -1 :
            # 左側の処理
            left_sub = (X - 1 + 1) - k
            left_n -= left_sub

        if k <= N - Y :
            # 右側の処理
            right_sub = (N - Y + 1) - k
            right_n -= right_sub
            pass
        print(left_n + mid_n + right_n)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N, X, Y = (int(n) for n in input().split(' '))

shortests = [0]*(N - 1)

for i, j in combinations(list(range(1, N + 1)), 2):
  dist = j - i
  if i <= X <= Y <= j:
    dist -= Y - X - 1
  elif i <= X <= j < Y:
    dist = min(dist, X - i + 1 + Y - j)
  elif X <= i <= Y <= j:
    dist = min(dist, i - X + 1 + j - Y)
  shortests[dist - 1] += 1

for val in shortests:
  print(val)

Submission status: Wrong Answer

Solution code:
N, X, Y = map(int,input().split())
one = list(range(1,N+1))
two = list(range(1,X+1)) + list(range(Y,N+1))
thr = list(range(1,X+1)) + list(range(Y,X,-1))
fou = list(range(Y-1,X-1,-1)) + list(range(Y,N+1))
start = 2
saitan = []

for i in range(1,N):
    for j in range(start,N+1):
        if i == j:
            continue
        kyori = [abs(i-j)]
        if (not X < i < Y) and (not X < j < Y):
            kyori.append(abs(two.index(i) - two.index(j)))
        if i <= Y and j <= Y:
            kyori.append(abs(thr.index(i) - thr.index(j)))
        if i >= X and j >= X:
            kyori.append(abs(fou.index(i) - fou.index(j)))
        saitan.append(min(kyori))
    start += 1

for i in range(1,N):
    print(saitan.count(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])

'''
以上グラフの準備
'''


#距離の羅列用  
l_d =deque([])  
for point in range(1,N+1):
  #seenとtodoの初期設定
  l_seen = {i:False for i in l_chouten}
  l_todo = []
  dist = {i:-1 for i in l_chouten}


  #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:
n,x,y = map(int,input().split())
l = [0]*(n-1)
for i in range(1,n):
    for j in range(i+1,n+1):
        #print(i,j)
        '''
        1 2,1 3,1 4
        2 3,2 4
        3 4
        '''
        if i<=x and j>=y:
            dis = min(j-i,x-i +1+ j-y)
            l[dis-1] += 1
            #print(i,j,dis-1)
        elif i<=x and x<=j<=y:
            dis = min(j-i,x-i+y-j+1)
            l[dis-1] += 1
        elif x<=i<=y and j>=y:
            dis = min(j-i,i-x+j-y+1)
            l[dis-1] += 1
        else:
            dis = min(j-i,i-x+y-j+1)
            l[dis-1] += 1
for kkk in l:
    print(kkk)

Submission status: Wrong Answer

Solution code:
n,x,y=map(int,input().split())
for i in range(n-1):
  center=max(0,n+x-y+1-(i+1))
  doub_center=max(0,y-x-1-(i+1))

  left=max(0,y-1-(i+1))
  doub_left=max(0,x-(i+1))

  right=max(0,n-x-(i+1))
  doub_right=max(0,n-y+1-(i+1))
  ans=center+left+right-doub_left-doub_right-doub_center
  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(N-1):
  for j in range(i+1, N):
    if i <= X and j <= X:
      ans[j-i-1] += 1
    elif i <=  X and 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
    else:
      ans[j-i-1] += 1
for i in range(N-1):
  print(ans[i])

Submission status: Wrong Answer

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

def solve():
    N, X, Y = map(int, input().split())
    def n(k):
        return (X-k if X-1 > k-1 else 0)\
         + (N-Y-k+1 if N-Y > k-1 else 0)\
         + ((Y-X+1 if (Y-X+1)%2 else (Y-X+1)//2) if (Y-X+1)>=2*k else 0)\
         + (N-(Y-X)-k+1 - (X-k if X-1 > k-1 else 0) - (N-Y-k+1 if N-Y > k-1 else 0) if N-(Y-X) > k-1 > 0 else 0)\
         + (sum(2 if (Y-X+1)>2*l and l > 1 else 1 if (Y-X+1)>=2*l else 0 for l in range(1,k) if X-1 > k-l-1) if X-1 > k-3 else 0)\
         + (sum(2 if (Y-X+1)>2*l and l > 1 else 1 if (Y-X+1)>=2*l else 0 for l in range(1,k) if N-Y > k-l-1) if N-Y > k-3 else 0)
    res_l = [n(k) for k in range(1,N)]
    res = '\n'.join(map(str, res_l))
    return res

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
from collections import deque

n,x,y = map(int,input().split())
cnt = [0]*(n)
path = [(i, i+1) for i in range(n-1)]
path.append((x-1, y-1))
res = []

for i in range(n):
    d = [float('inf')]*n
    que = deque([(i, 0)])
    while que:
        idx, c = que.popleft()
        if d[idx]!=float('inf'):
            continue
        else:
            d[idx] = c
            for s,g in path:
                if s==idx:
                    que.appendleft((g, c+1))
                if g==idx:
                    que.appendleft((g, c+1))
    res.append(d)

for r in res:
    for i in range(n-1):
        cnt[i] += r.count(i)
for c in cnt[1:]:
    print(c)

Submission status: Wrong Answer

Solution code:
import pprint
n, x, y = (int(each) for each in input().split(' '))

table1 = [[0] * n for i in range(n)]
table2 = [[0] * n for i in range(n)]
pprint.PrettyPrinter().pprint(table1)

# 点iから点jまでの距離をテーブルにする

# 抜け道を通らないルートの場合
for i in range(n):
    for j in range(n):
        if j-i > 0:
            table1[i][j] = j-i

# 抜け道を通るルートの場合
for i in range(n):
    for j in range(n):
        # if j-i > 0:
        table2[i][j] = abs(j-y)-abs(i-x)+1

pprint.PrettyPrinter().pprint(table1)
pprint.PrettyPrinter().pprint(table2)