Problem:


Score : 800 points

Problem Statement

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 1

3 2

Sample Output 1

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).

Sample Input 2

2 4

Sample Output 2

1 2 2 2

Sample Input 3

5 14

Sample Output 3

3 3 3 3 3 3 3 3 3 3 3 3 2 2 



Sample input:
3 2


Sample output:
2 1

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
from itertools import chain,repeat
K,N = 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(range(1,K+1),repeat=i) for i in range(1,N+1)))
  return ' '.join(map(str, s[(len(s)-1)//2]))

print(solve())
# print(naive())

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
input = raw_input
range = xrange
k, n = map(int,input().split())
if k%2 == 0:
    print k//2,
    for i in range(n-1): print k,
    exit()
seq = [k//2+1]*n
for i in range(n//2):
    seq[-1]-= 1
    if seq[-1] == 0: seq.pop()
    else: seq.extend([k]*(n-len(seq)))
for x in seq: print x,

Submission status: Accepted

Solution code:

def brute(k,n):
	def gen(k,p):
		ret = []
		if p==0:
			return [()]
		for seq in gen(k,p-1):
			for i in xrange(1,k+1):
				ret.append(seq+(i,))
		return ret
	seqs = []
	for i in xrange(1,n+1):
		seqs += gen(k,i)
	X = len(seqs)
	Y = (X-1)/2
	seqs.sort()
	#if len(seqs)<100:print seqs
	return seqs[Y]

def down_onestep(seq,k,n):
	if seq[-1]==1:
		seq.pop()
		return
	seq[-1]-=1
	while len(seq)<n:
		seq.append(k)

def f(k,n):
	if k%2==0:
		return (k/2,)+(k,)*(n-1)
	if k==1:
		return (1,)*((n+1)/2)
	else:
		seq = [(k+1)/2]*n
		for i in xrange( (n)/2 ):
			down_onestep(seq, k, n)
		return tuple(seq)
	return None

def test():
	for k in xrange(1,6):
		for n in xrange(1,8):
			if f(k,n)==brute(k,n):continue
			print k,n
			print brute(k,n)
			print f(k,n)
			print

def main():
	k,n = map(int, raw_input().split())
	print " ".join(map(str, f(k,n) ))

main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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()
    if k%2:
        ans=[k//2+1]*n
        end=n-1
        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()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
K, N = map(int,input().split())
#K, N = map(int,"3 14".split())
def findprev(s,N):
	if s[len(s)-1] == 1:
		z = s[0:len(s)-1]
	else:
		s[len(s)-1] -= 1
		k = N - len(s)
		z = s + [K for _ in range(N - len(s))]
	return z

import math

t = ""
if K % 2 == 0:
	z = list(K/2) + [K for _ in range(N-1)]
else:
	s = [(K+1)//2 for _ in range(N-1)]
	z = findprev(s,math.floor((N-1)/2))
for i,v in enumerate(z):
	t = t + str(v) + " "
print(t)

Submission status: Runtime Error

Solution code:
K, N = map(int,input().split())
def m(K,N): return (K**(N+1)-1)//(K-1)
S = m(K,N)//2 - 1
s = ""
while S >= 0:
	t = m(K,N-1)
	s = s + str(S//t+1) + " "
	S = S-(S//t)*t-1 # remove ""
	N = N-1
print(s)

Submission status: Runtime Error

Solution code:
K, N = map(int,input().split())
# K, N = map(int,"5 14".split())
# 1 11 12 13 2 21 22 23 3 31 32 33
# def l(K,N): return (K**(N+1)-1)//(K-1) - 1 #=K**N+K**(N-1)+...+K
def m(K,N): return (K**(N+1)-1)//(K-1)

# X = l(K,N)
S = m(K,N)//2 - 1
s = ""
while S >= 0:
	t = m(K,N-1)
	s += str(S//t+1)
	s += " "
	#print((S,t,S//t+1))
	S = S-(S//t)*t-1 # remove ""
	N = N-1
print(s)

Submission status: Runtime Error

Solution code:
import itertools
import math

K, N = map(int, input().split())
integer = [(i + 1) for i in range(K)]

# 重複順列計算
#answer = []
#for i in range(N):
#    for j in itertools.product(integer, repeat=(i+1)):
#        # ソートのために文字列変換
#        answer.append(list(map(str, j)))

# 重複順列計算
answer = [list(map(str, j)) for i in range(N) for j in itertools.product(integer, repeat=(i+1))]
        
# 辞書順にソート
answer.sort()

# X/2を出力
p = answer[math.ceil(len(answer)/2.0) - 1]
print(' '.join(map(srt, p)))

Submission status: Runtime Error

Solution code:
import math

K, N = map(int, input().split())
ans = []

if K % 2 == 0:
    for i in range(N):
        if i == 0:
            ans[i] = K // 2
        else:
            ans[i] = K
elif K == 1:
    n2 = math.ceil(N / 2)
    for i in range(n2):
        ans.append(1)
else:
    K2 = math.ceil(K / 2)
    n2 = math.floor(N / 2)
    ans = [K2] * N
    i = 0
    nx = 0
    last = True
    while n2 > 0:
        i += 1
        ans[N - i] = max(K2 - n2 % (K + 1) - nx, 0)
        if ans[N - i] == 0 and last:
            ans.pop()
        else:
            last = False
        n2 //= K + 1
        if K2 - n2 % (K + 1) - nx < 0:
            nx = 1
        else:
            nx = 0

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

Submission status: Runtime Error

Solution code:
def solve(k, n):
    if k & 1 == 0:
        return [k // 2] + [k] * (n - 1)
    xs = [((k ** i - 1) // (k - 1)) for i in range(1, -1)]
    xs = [((k ** i - 1) // (k - 1)) for i in range(n + 1, 1, -1)]
    tgt = xs[0] // 2 - 1
    mk1 = k // 2
    mk2 = mk1 + 1
    l = xs[1] * mk1
    ans = []
    for i in range(1, n - 1):
        if l == tgt:
            return ans
        nxt = l + xs[i + 1] * mk1 + 1
        if nxt > tgt:
            ans.append(mk1)
            l = nxt - xs[i + 1]
        else:
            ans.append(mk2)
            l = nxt
    if l == tgt:
        return ans
    return ans + [tgt - l]


k, n = map(int, input().split())

print(*solve(k, n))

Submission status: Runtime Error

Solution code:
from math import ceil
k, n = [int(x) for x in input().strip().split()]
li = [pow(k, i) for i in range(1, n+1)]
for i in range(1, n):
    li[i] += li[i-1]
li.reverse()
li.append(0)
li.append(-1)
target = ceil(li[0] / 2)
results = []
#print(li)
def f(i, target):
    if target == 0:
        return
    if li[i] == -1:
        return
    div = (target - 1) // (li[i] + 1)
    results.append(div + 1)
    #print(i, target, results)
    f(i+1, (target - 1) % (li[i] + 1))

f(1, target)
print(" ".join(map(str, results)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100500)

def F(n):
	return (k**n - 1) // (k - 1)

l = 0
def go(x, n):
	global l
	if (x == 1): return
	x -= 1
	t = F(n)
	c = ((x - 1) // t)
	print(c + 1, end = ' ')
	go(x - c * t, n - 1)


k, n = [int(i) for i in input().split()]

if k % 2 == 0:
	print(k // 2. end = ' ')
	for i in range(n - 1):
		print(k, end = ' ')
	exit()

res = F(n) * k
go((res + 1) // 2 + 1, n)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100500)

def F(n):
	return (k**n - 1) // (k - 1)

l = 0
def go(x, n):
	global l
	if (x == 1): return
	x -= 1
	t = F(n)
	c = ((x - 1) // t)
	print(c + 1, end = ' ')
	go(x - c * t, n - 1)


k, n = [int(i) for i in input().split()]
res = F(n) * k
go((res + 1) // 2 + 1, n)

Submission status: Runtime Error

Solution code:
def solve(k, n):
    if k & 1 == 0:
        return [k // 2] + [k] * (n - 1)
    xs = [((k ** i - 1) // (k - 1)) for i in range(n + 1, 1, -1)]
    tgt = xs[0] // 2 - 1
    mk = k // 2 + 1
    l = xs[1] * (k // 2)
    for i in range(1, n - 1):
        if l == tgt:
            return [mk] * i
        if l > tgt:
            return [mk] * i + [mk - 1] * (n - i)
        l += xs[i + 1] * (k // 2) + 1
    if l == tgt:
        return [mk] * (n - 1)
    return [mk] * (n - 1) + [tgt - l]


k, n = map(int, input().split())

print(*solve(k, n))

Submission status: Runtime Error

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

def dec(seq):
  if seq[-1] == 1:
    seq.pop()
  else:
    seq[-1] -= 1
    if len(seq) < N:
      seq += list(repeat(K,N-len(seq)))
  return seq

if K % 2 == 0:
  print(' '.join(chain((K-1,),repeat(K,N-1))))
else:
  seq = list(repeat(K//2+1,N))
  d = (N-1)//2
  for _ in range(d+1):
    seq = dec(seq)
  print(' '.join(map(str, seq)))

Submission status: Runtime Error

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

def dec(seq):
  if seq[-1] == 1:
    seq.pop()
  else:
    seq[-1] -= 1
    if len(seq) < N:
      seq += list(repeat(K,N-len(seq)))
  return seq

if K % 2 == 0:
  print(' '.join(chain((K-1,),repeat(K,N-1))))
else:
  seq = list(repeat(K//2+1,N))
  d = (N-1)//2
  for _ in range(d):
    seq = dec(seq)
  print(' '.join(map(str, seq)))

Submission status: Runtime Error

Solution code:
K,N=map(int,input().split())
if K%2==0:
  L=[K//2]+[K]*(N-1)
  print(' '.join(map(str, L)))
else:
  l=K//2
  L=[K//2+1]*(N-l)+[l]*l
  pri