순열 p 의 맨해튼 값 을 표현식 |p_1−1|+|p_2−2|+…+|p_n−n|의 값이라고 하자.
예를 들어, 순열 [1,2,3] 의 맨해튼 값은 ∣1−1∣+∣2−2∣+∣3−3∣=0 이며, 순열 [3,1,2] 의 맨해튼 값은 ∣3−1∣+∣1−2∣+∣2−3∣=2+1+1=4 이다.
정수 n 과 k 가 주어졌을 때, 길이 n 의 순열 p 의 맨해튼 값이 k 와 같은 순열을 찾거나, 그러한 순열이 존재하지 않음을 결정하시오.
순열이란?
길이 n 의 순열은 1 부터 n 까지의 n 개의 서로 다른 정수로 이루어진 배열이다. 예를 들어, [2,3,1,5,4] 는 순열이지만, [1,2,2] 는 순열이 아니며 (2 가 배열에 두 번 나타남), [1,3,4] 또한 순열이 아니다 (n=3 인데 배열에 4 가 있음).
입력
각 테스트는 여러 개의 테스트 케이스로 구성된다.
첫 번째 줄에는 테스트 케이스의 수 t (1≤t≤10^4) 가 포함된다. 테스트 케이스의 설명이 뒤따른다.
각 테스트 케이스의 유일한 줄에는 두 개의 정수 n 과 k (1≤n≤2⋅10^5,0≤k≤10^{12}) 가 포함된다 — 순열의 길이와 필요한 맨해튼 값이다.
모든 테스트 케이스에 대한 n 의 합은 2⋅10^5 를 초과하지 않음이 보장된다.
출력
각 테스트 케이스에 대해 적합한 순열이 없으면 "No" 를 출력한다. 그렇지 않으면, 첫 번째 줄에 "Yes" 를 출력하고, 두 번째 줄에 nnn 개의 서로 다른 정수 p_1,p_2,…,p_n (1≤p_i≤n) 를 출력한다 — 적합한 순열.
여러 가지 해결책이 있는 경우, 그 중 하나를 출력한다. 대소문자 구분 없이 정답을 출력할 수 있다 (예: "yEs", "yes", "Yes", "YES" 모두 인식됨).
Example
input
8
3 4
4 5
7 0
1 1000000000000
8 14
112 777
5 12
5 2
output
Yes
3 1 2
No
Yes
1 2 3 4 5 6 7
No
Yes
8 2 3 4 5 6 1 7
No
Yes
5 4 3 1 2
Yes
2 1 3 4 5예제
첫 번째 테스트 케이스에서, 순열 [3,1,2] 는 적합하며, 그 맨해튼 값은 ∣3−1∣+∣1−2∣+∣2−3∣=2+1+1=4 이다.
두 번째 테스트 케이스에서는 길이 4의 순열 중 맨해튼 값이 5인 순열은 존재하지 않음을 증명할 수 있다.
세 번째 테스트 케이스에서, 순열 [1,2,3,4,5,6,7] 는 적합하며, 그 맨해튼 값은 ∣1−1∣+∣2−2∣+∣3−3∣+∣4−4∣+∣5−5∣+∣6−6∣+∣7−7∣=0 이다.
풀이
for i in range(n):
if k >= (far-i)*2 and i < far:
k -= (far-i)*2
p[i+1] = far+1
p[far+1] = i+1
far -= 1
정답 코드
import sys
def input():
return sys.stdin.readline().strip()
for _ in range(int(input())):
n, k = map(int, input().split())
p = {}
ex = True
far = n-1
for i in range(n):
if k >= (far-i)*2 and i < far:
k -= (far-i)*2
p[i+1] = far+1
p[far+1] = i+1
far -= 1
if k==0:
print('Yes')
for i in range(1, n+1):
if i in p:
print(p[i], end=' ')
else:
print(i, end=' ')
print()
else:
print('No')