AtCoder Regular Contest 084 - Finite Encyclopedia of Integer Sequences

In Finite Encyclopedia of Integer Sequences (FEIS), all integer sequences of lengths between 1 and N (inclusive) consisting of integers between 1 and K (inclusive) are listed.
Let the total number of sequences listed in FEIS be X. Among those sequences, find the (X/2)-th (rounded up to the nearest integer) lexicographically smallest one.

-----Constraints-----
 - 1 \leq N,K \leq 3 × 10^5
 - N and K are integers.

-----Input-----
Input is given from Standard Input in the following format:
K N

-----Output-----
Print the (X/2)-th (rounded up to the nearest integer) lexicographically smallest sequence listed in FEIS, with spaces in between, where X is the total number of sequences listed in FEIS.

-----Sample Input-----
3 2

-----Sample Output-----
2 1 

There are 12 sequences listed in FEIS: (1),(1,1),(1,2),(1,3),(2),(2,1),(2,2),(2,3),(3),(3,1),(3,2),(3,3).
The (12/2 = 6)-th lexicographically smallest one among them is (2,1).

Difficulty: VERY_HARD

Starter code:

Solutions:
import math

def main():
	[K, N] = list(map(int, input().split()))
	r = []
	if K == 1:
		r = [1] * ((N + 1) // 2)
	elif K % 2 == 0:
		r = [K // 2]
		r += [K] * (N - 1)
	else:
		t = N // 2
		x = int(math.log(N * (K - 1) + 1, K) - 1)
		while t < ((K ** (x + 1) - 1) / (K - 1) + x) // 2:
			x -= 1
		x += 1
		r = [(K + 1) // 2] * (N - x)
		r += [0] * x
		t = ((K ** (x + 1) - 1) / (K - 1) + x) // 2 - t
		for i in range(x, 0, -1):
			r[N - i] = 1
			t -= 1
			for j in range(K - 1):
				if t == 0:
					break
				if K ** i - 1 <= t * (K - 1):
					r[N - i] += 1
					t -= (K ** i - 1) // (K - 1)
			if t == 0:
				break
		for i in range(len(r) - 1, -1, -1):
			if r[i] == 0:
				r.pop()
			else:
				break
	print(' '.join(list(map(str, r))))
main()


(k, n) = map(int, input().split())
if k % 2 == 0:
	ans = [k // 2] + [k] * (n - 1)
else:
	t = n // 2
	ans = [k // 2 + 1] * n
	for i in range(t):
		if ans[-1] == 1:
			ans.pop()
		else:
			ans[-1] -= 1
			while len(ans) < n:
				ans.append(k)
print(*ans)


def solve(k, n):
	if k & 1 == 0:
		return [k // 2] + [k] * (n - 1)
	ans = [k // 2 + 1] * n
	l = n
	for i in range((n - 2) // 2 + 1):
		if ans[-1] == 1:
			ans.pop()
			l -= 1
		else:
			ans[-1] -= 1
			if l < n:
				ans += [k] * (n - l)
				l = n
	return ans
(k, n) = map(int, input().split())
print(*solve(k, n))


import math

def main(K, N):
	ans = []
	if K % 2 == 0:
		for i in range(N):
			if i == 0:
				ans.append(K // 2)
			else:
				ans.append(K)
	elif K == 1:
		n2 = math.ceil(N / 2)
		for i in range(n2):
			ans.append(1)
	else:
		K2 = math.ceil(K / 2)
		ans = [K2] * N
		n = N // 2
		for i in range(n):
			if ans[-1] == 1:
				ans.pop()
			else:
				ans[-1] -= 1
				while len(ans) < N:
					ans.append(K)
	return ' '.join(map(str, ans))
(K, N) = map(int, input().split())
print(main(K, N))


import sys
sys.setrecursionlimit(10 ** 6)
(k, n) = map(int, input().split())

def calc_x(K, N):
	return (pow(K, N + 1) - K) // (K - 1)

def lexico(K, N, X):
	global ans
	if X == 0:
		return
	q = calc_x(K, N - 1) + 1
	if N > 1:
		ans.append(X // q + 1)
	else:
		ans.append(X // q)
	lexico(K, N - 1, (X - 1) % q)
if k == 1:
	print(*[1 for _ in range((n + 1) // 2)])
elif n == 1:
	print((k + 1) // 2)
elif k % 2 == 0:
	ans = [k // 2] + [k] * (n - 1)
	print(*ans)
else:
	if n % 2 == 1:
		(cur, i) = (1, n)
	else:
		(cur, i) = (0, n)
	while cur <= i:
		i -= 1
		cur += pow(k, n - i)
	ans = [(k + 1) // 2] * i
	ind = (cur - i) // 2
	lexico(k, n - i, ind)
	print(*ans)


def main():
	(K, N) = map(int, input().split())
	if K % 2 == 0:
		ans = [K // 2]
		for i in range(N - 1):
			ans.append(K)
	else:
		back = N // 2
		mid = K // 2 + 1
		ans = [mid for i in range(N)]
		for i in range(back):
			if ans[-1] == 1:
				ans.pop()
			else:
				ans[-1] -= 1
				while len(ans) < N:
					ans.append(K)
	print(' '.join(map(str, ans)))
main()


(K, N) = map(int, input().split())
if K % 2 == 0:
	print(K // 2, end=' ')
	for i in range(1, N):
		if i != N - 1:
			print(K, end=' ')
		else:
			print(K)
else:

	def superlist(L, n):
		if n % 2 == 1:
			return [L // 2 + 1] + superlist(L, n - 1)
		else:
			Ax = [L // 2 + 1 for i in range(n)]
			j = n - 1
			for i in range(n // 2):
				Ax[j] -= 1
				if Ax[j] == 0:
					j -= 1
				else:
					for m in range(j + 1, n):
						Ax[m] = L
					j = n - 1
			return Ax
	if K == 1:
		for i in range((N - 1) // 2 + 1):
			if i != (N - 1) // 2:
				print(1, end=' ')
			else:
				print(1)
	else:
		A = superlist(K, N)
		for _ in range(N):
			if _ != N - 1 and A[_] != 0:
				print(A[_], end=' ')
			elif _ == N - 1 and A[_] != 0:
				print(A[_])


(K, N) = list(map(int, input().split()))
if K % 2 == 0:
	ans = [K // 2] + [K] * (N - 1)
else:
	ans = [(K + 1) // 2] * N
	for i in range(N // 2):
		if ans[-1] == 1:
			ans.pop()
		else:
			ans[-1] -= 1
			ans += [K] * (N - len(ans))
print(' '.join(map(str, ans)))


(N, K) = map(int, input().split())
if N % 2 == 0:
	L = [str(N)] * K
	L[0] = str(N // 2)
	print(' '.join(L))
	exit()
L = [N // 2 + 1] * K
for i in range(K // 2):
	if L[-1] == 1:
		L.pop(-1)
	elif len(L) != K:
		L[-1] -= 1
		L += [N] * (K - len(L))
	else:
		L[-1] -= 1
L = list(map(str, L))
print(' '.join(L))


from itertools import chain, repeat
(K, N) = list(map(int, input().split()))

def solve():
	if K % 2 == 0:
		return ' '.join(map(str, chain((K // 2,), repeat(K, N - 1))))
	else:
		seq = [K // 2 + 1] * N
		d = N // 2
		for _ in range(d):
			if seq[-1] == 1:
				seq.pop()
			else:
				seq[-1] -= 1
				seq.extend(repeat(K, N - len(seq)))
		return ' '.join(map(str, seq))

def naive():
	from itertools import product
	s = sorted(chain.from_iterable((product(list(range(1, K + 1)), repeat=i) for i in range(1, N + 1))))
	return ' '.join(map(str, s[(len(s) - 1) // 2]))
print(solve())


import sys
input = sys.stdin.readline
(K, N) = map(int, input().split())
if K % 2 == 0:
	L = K // 2
	R = L + 1
	arr = [L] + [K] * (N - 1)
else:
	arr = [(K + 1) // 2] * N
	x = N // 2
	for i in range(x):
		arr[-1] -= 1
		if arr[-1] == 0:
			arr.pop()
			continue
		L = len(arr)
		if L < N:
			arr += [K] * (N - L)
answer = ' '.join(map(str, arr))
print(answer)


import sys
readline = sys.stdin.readline
INF = 10 ** 9 + 7

def calc(n, k):
	if k == 1:
		return n
	if n > 20:
		return INF
	return min(INF, (pow(k, n) - 1) // (k - 1))
(K, N) = map(int, readline().split())
if K % 2 == 0:
	ans = [K // 2] + [K] * (N - 1)
	print(*ans)
else:
	ans = []
	cnt = 0
	half = True
	for l in range(N, 0, -1):
		clk = calc(l, K)
		if half:
			c = 1 + K // 2
			if l % 2 == 0:
				cnt += 1
			if clk // 2 == cnt:
				ans.append(c)
				break
			if clk // 2 < cnt:
				c -= 1
				half = False
				cnt -= clk // 2 + 1
				while cnt >= clk:
					cnt -= clk
					c -= 1
				if cnt == clk - 1:
					ans.append(c)
					break
		else:
			c = K
			while cnt >= clk:
				cnt -= clk
				c -= 1
			if cnt == clk - 1:
				ans.append(c)
				break
		ans.append(c)
	print(*ans)


(k, n) = map(int, input().split())
if k % 2 == 0:
	print(k // 2, end=' ')
	for i in range(n - 1):
		print(k, end=' ')
else:
	l = [(k + 1) // 2 for i in range(n)]
	for i in range(n // 2):
		if l[-1] == 1:
			l.pop()
		else:
			l[-1] -= 1
			for j in range(n - len(l)):
				l.append(k)
	print(*l, sep=' ')


(a, n) = map(int, input().split())
if a % 2 == 0:
	print(*[a // 2] + [a] * (n - 1))
else:
	d = [(a + 1) // 2] * n
	for i in range(n // 2):
		if d[-1] == 1:
			d.pop()
		else:
			d[-1] -= 1
			d.extend([a] * (n - len(d)))
	print(' '.join((str(i) for i in d)))


(K, N) = map(int, input().split())
if K % 2 == 0:
	print(*[K // 2] + [K] * (N - 1))
else:
	X = [(K + 1) // 2] * N
	for i in range(N // 2):
		if X[-1] == 1:
			X.pop()
		else:
			X[-1] -= 1
			X.extend([K] * (N - len(X)))
	print(*X)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
(k, n) = map(int, read().split())
if k % 2 == 0:
	print(*[k // 2] + [k] * (n - 1))
	exit()
if k == 1:
	print(*[1] * ((n + 1) // 2))
	exit()
ans = [(k + 1) // 2] * n
d = 0

def f(k, i, d):
	v = 1
	for j in range(i):
		v *= k
		v += 1
		if v > d:
			return True
	return False

def g(k, i):
	v = 1
	for j in range(i):
		v *= k
		v += 1
	return v
for i in range(1, n):
	if f(k, n - i - 1, d):
		d += 1
		continue
	v = (g(k, n - i) + d + 1) // 2 - d - 1
	for j in range(i, n):
		if v == 0:
			ans[j] = 0
			continue
		p = g(k, n - j - 1)
		q = (v - 1) // p
		ans[j] = q + 1
		v -= 1 + q * p
	break
while ans[-1] == 0:
	ans.pop()
print(*ans)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def main():
	(k, n) = MI()
	end = n - 1
	if k % 2:
		ans = [k // 2 + 1] * n
		for _ in range(n // 2):
			if ans[end] == 1:
				end -= 1
			else:
				ans[end] -= 1
				if end != n - 1:
					for i in range(end + 1, n):
						ans[i] = k
					end = n - 1
	else:
		ans = [k // 2] + [k] * (n - 1)
	print(*ans[:end + 1])
main()