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

Solution code:
# coding: utf-8
# Your code here!
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):
    # d <= 1+k+...+k^i?
    v = 1
    for j in range(i):
        v *= k
        v += 1
        if v > d: return True
    return False

def g(k,i):
    # 1+k+...+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
    """
    以下　300000 >= d >= 1+k+...+k^(n-i-1)
    i 番目の項から真ん中にならない    
    v 番目を目指す
    """
    v = (g(k,n-i)+d)//2 - d - 1
    
    for j in range(i,n):
        #print(v)
        if v==0:
            ans[j] = 0
            continue

        p = g(k,n-j-1)
        q = (v-1)//p 
        #print(v,j,p,q)
        
        ans[j] = q+1
        v -= 1+q*p        
    break


while ans[-1]==0:
    ans.pop()
print(ans)

Submission status: Wrong Answer

Solution code:
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 len(ans) < n:
      ans[-1] -= 1
      ans.append(k)
    elif ans[-1] > 1:
      ans[-1] -= 1
    else:
      ans.pop()
print(*ans)

Submission status: Wrong Answer

Solution code:
k,n = map(int,input().split())
if k%2 == 0:
  ans = [k//2]+[k//2+1]*(n-1)
else:
  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: Wrong Answer

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)

main()

Submission status: Wrong Answer

Solution code:
from itertools import product
k, n = map(int, input().split())
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
	l = []
	for r in range(1, n-i+1):
		for p in product(range(1, k+1), repeat=r):
			l.append("".join(list(map(str, p))))
	l.sort()
	ans += list(l[ind-1])
	print(*ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    [K, N] = list(map(int, input().split()))

    r = []
    if K % 2 == 0:
        r = [K // 2]
        r += [K] * (N - 1)
    else:
        t = N // 2
        s = []
        d = t
        while 0 < d:
            s.append(d % (K + 1))
            d //= K + 1
        s.append(0)
        m = [(K + 1) // 2] * len(s)
        for i in range(len(m)):
            mi = m[i] - s[i]
            if mi < 0:
                m[i + 1] -= 1
                mi += K + 1
            m[i] = mi
        m.reverse()
        r = [(K + 1) // 2] * (N - len(m))
        r += m
        for i in range(len(r) - 1, -1, -1):
            if r[i] == 0:
                r.pop()
            else:
                break


    print(' '.join(list(map(str, r))))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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] ==-1:
      ans[j] = k
      j-=1    
      ans[j]-=1
  while True:
    try:
      ans.remove(0)
    except:
      break
  print(*ans)

Submission status: Wrong Answer

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-1)//2
  for i in range(sage):
    ans[-1] -=1
    j = -1
    while ans[j] ==0:
      ans[j] = k
      j-=1
  print(*ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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-1)//2):
        if X[-1] == 1:
            X.pop()
        else:
            X[-1] -= 1
            X.extend([K]*(N-len(X)))
    print(*X)

Submission status: Wrong Answer

Solution code:
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-1)//2+1):
        if X[-1] == 1:
            X.pop()
        else:
            X[-1] -= 1
            X.extend([K]*(N-len(X)))
    print(*X)

Submission status: Wrong Answer

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

# X/2を出力
print(answer)
print(len(answer))
print(answer[math.ceil(len(answer)/2.0) - 1])

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]

K, N = rdi()

if K == 1:
        print " ".join(["1"] * ((N+1)/2))
        sys.exit(0)

if K % 2 == 0:
        print K/2,
        for i in range(N-1):
                print K,
        print
        sys.exit(0)

t = [ K/2+1 ] * N
for i in range(N/2):
        print t
        if t[-1] == 1:
                #if t[-2] == 1:
                        t = t[:-1]
                #else:
                #       t[-2] -= 1
                #       t = t[:-1] + [ K ] * (N - len(t) + 1)
        else:
                t[-1] -= 1
                t = t + [ K ] * (N - len(t))
        print t
print " ".join([ str(x) for x in t])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
k, n = map(int, input().split())
xs = [ 1 ]
for i in range(n):
    xs += [ xs[-1] + pow(k, i + 1) ]
if k == n == 1:
    acc = [ 1 ]
else:
    acc = []
    y = xs[n]
    for i in range(n):
        q = (2 * y - xs[-1]) // (2 * xs[n - i - 1])
        if q >= k:
            break
        y -= q * xs[n - i - 1]
        acc += [ k - q ]
print(*acc)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
k, n = map(int, input().split())
xs = [ 0 ]
for i in range(n):
    xs += [ xs[-1] + pow(k, i + 1) ]
acc = []
y = xs[n]
for i in range(n):
    c = k
    while (c - 1) >= 0 and 2 * (y - xs[n - i - 1] - 1) >= xs[-1]:
        c -= 1
        y -= xs[n - i - 1] + 1
    if c == 0:
        acc.pop()
        break
    acc += [ c ]
print(*acc)

Submission status: Wrong Answer

Solution code:
import math
import random


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)
        n2 = math.floor(N / 2)
        ans = [K2] * N
        i = 0
        nx = 0
        last = True
        while n2 > 0 or nx == 1:
            i += 1
            ans[N - i] = max(K2 - n2 % (K + 1) - nx, 0)
            if ans[N - i] == 0 and last:
                ans.pop()
            else:
                last = False
            if K2 - n2 % (K + 1) - nx < 0:
                nx = 1
            else:
                nx = 0
            n2 //= K + 1

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


K, N = map(int, input().split())
main(K, N)

Submission status: Wrong Answer

Solution code:
import math
import random


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)
        n2 = math.floor(N / 2)
        ans = [K2] * N
        i = 0
        nx = 0
        last = True
        while n2 > 0 or nx == 1:
            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)))


K, N = map(int, input().split())
main(K, N)

Submission status: Wrong Answer

Solution code:
import math
import random


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)
        n2 = math.floor(N / 2)
        ans = [K2] * N
        i = 0
        nx = 0
        last = True
        while n2 > 0 and nx == 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)))


K, N = map(int, input().split())
main(K, N)

Submission status: Wrong Answer

Solution code:
import math
import random


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


K, N = map(int, input().split())
main(K, N)

Submission status: Wrong Answer

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

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()[-30:])
# print(naive())

Submission status: Wrong Answer

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

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

  if K % 2 == 0:
    return ' '.join(map(str, chain((K//2,),repeat(K,N-1))))
  else:
    seq = [K//2+1]*N
    d = (N + 1)//2
    for _ in range(d):
      seq = dec(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)//2-1]))

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

Submission status: Wrong Answer

Solution code:
def solve(k, n):
    if k & 1 == 0:
        return [k // 2] + [k] * (n - 1)
    ans = [k // 2 + 1] * n
    for i in range((n - 1) // 2 + 1):
        if ans[-1] == 1:
            ans.pop()
        else:
            ans[-1] -= 1
            if len(ans) < n:
                ans += [k] * (n - len(ans))
    return ans


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

print(*solve(k, n))

Submission status: Wrong Answer

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

def solve():
  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(map(str, chain((K//2,),repeat(K,N-1)))))
  else:
    seq = list(repeat(K//2+1,N))
    d = (N - 1)//2 + 1
    for _ in range(d):
      seq = dec(seq)
    print(' '.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)))
  print(' '.join(map(str, s[len(s)//2-1])))

solve()
# naive()

Submission status: Wrong Answer

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

def solve():
  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(map(str, chain((K//2,),repeat(K//2+1,N-1)))))
  else:
    seq = list(repeat(K//2+1,N))
    d = (N - 1)//2 + 1
    for _ in range(d):
      seq = dec(seq)
    print(' '.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)))
  print(' '.join(map(str, s[len(s)//2-1])))

solve()

Submission status: Wrong Answer

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:
  seq = [K//2+1]
else:
  seq = list(repeat(K//2+1,N))
d = (N - 1 + K%2)//2
for _ in range(d):
  seq = dec(seq)
print(' '.join(map(str, seq)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

tmp = input()
K, N = [int(a) for a in tmp.split()]

nums = [K]
for i in range(N-1):
    nums.append((nums[-1] + 1) * K)
i = N-1
a = nums[-1] // 2 + (nums[-1] % 2)
ans = []
while i >= 0:
    num = nums[i]
    if i == 0:
        ans.append(a)
        break
    b_num = nums[i-1]
    ap = (a - 1) // (b_num + 1) + 1
    if ap != 0:
        ans.append(ap)
    else:
        break
    a = (a - 1) % (b_num + 1)
    i -= 1

print(*ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
  print(' '.join(map(str, L)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

tmp = input()
K, N = [int(a) for a in tmp.split()]

nums = [K]
for i in range(N-1):
    nums.append((nums[-1] + 1) * K)
i = N-1
a = nums[-1] // 2 + (nums[-1] % 2)
ans = []
while i >= 0:
    num = nums[i]
    if i == 0:
        ans.append(a)
        break
    b_num = nums[i-1]
    ans.append((a - 1) // (b_num + 1) + 1)
    a = (a - 1) % (b_num + 1)
    i -= 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
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:
	x = calc_x(k, n)
	ans = []
	lexico(k, n, (x+1)//2)
	print(*ans)

Submission status: Time Limit Exceeded

Solution code:
k, n = map(int, input().split())
def next_lexico(K, N, L):
	if len(L) < N:
		return L + [1]
	else:
		IND = N-1
		while L[IND] == K and IND > 0:
			IND -= 1
		if IND == 0:
			return [L[0]+1]
		else:
			return L[:IND] + [L[IND]+1]

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
	l = [1]
	for _ in range(ind-1):
		l = next_lexico(k, n-i, l)
	ans += l
	print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]

K, N = rdi()

if K == 1:
        print " ".join(["1"] * ((N+1)/2))
        sys.exit(0)

if K % 2 == 0:
        print K/2,
        for i in range(N-1):
                print K,
        print
        sys.exit(0)

t = [ K/2+1 ] * N
for i in range(N/2):
        #print t
        if t[-1] == 1:
                #if t[-2] == 1:
                        t = t[:-1]
                #else:
                #       t[-2] -= 1
                #       t = t[:-1] + [ K ] * (N - len(t) + 1)
        else:
                t[-1] -= 1
                t = t + [ K ] * (N - len(t))
        #print t
print " ".join([ str(x) for x in t])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

tmp = input()
K, N = [int(a) for a in tmp.split()]

nums = [0 for i in range(N)]
a = 0
for i in range(N):
    a = (a+1) * K
    nums[i] = a

i = N-1
j = 0
a = nums[-1] // 2 + (nums[-1] % 2)
ans = [0 for i in range(N)]
while i >= 0:
    num = nums[i]
    if i == 0:
        if a != 0:
            ans[j] = a
            j += 1
        ans = ans[:j]
        break
    b_num = nums[i-1]
    ap = (a - 1) // (b_num + 1) + 1
    if ap != 0:
        ans[j] = ap
        j += 1
    else:
        ans = ans[:j]
        break
    a = (a - 1) % (b_num + 1)
    i -= 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

tmp = input()
K, N = [int(a) for a in tmp.split()]

nums = [K]
for i in range(N-1):
    nums.append((nums[-1] + 1) * K)
i = N-1
a = nums[-1] // 2 + (nums[-1] % 2)
ans = []
while i >= 0:
    num = nums[i]
    if i == 0:
        if a != 0:
            ans.append(a)
        break
    b_num = nums[i-1]
    ap = (a - 1) // (b_num + 1) + 1
    if ap != 0:
        ans.append(ap)
    else:
        break
    a = (a - 1) % (b_num + 1)
    i -= 1

print(*ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
#1 2 3...N
if N%2==0:
  L=[str(N)]*K
  L[0]=str(N//2)
  print(" ".join(L))
  exit()
#L[0]=N//2+1
#N//2のずれ？
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))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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):
    # d <= 1+k+...+k^i?
    v = 1
    for j in range(i):
        v *= k
        v += 1
        if v > d: return True
    return False

def g(k,i):
    # 1+k+...+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
    """
    以下　300000 >= d >= 1+k+...+k^(n-i-1)
    i 番目の項から真ん中にならない    
    v 番目を目指す
    """
    v = (g(k,n-i)+d+1)//2 - d - 1
    
    for j in range(i,n):
        #print(v)
        if v==0:
            ans[j] = 0
            continue

        p = g(k,n-j-1)
        q = (v-1)//p 
        #print(v,j,p,q)
        
        ans[j] = q+1
        v -= 1+q*p        



    
    break


while ans[-1]==0:
    ans.pop()
print(*ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

K,N = map(int,input().split())

if K % 2 == 0:
    L = K // 2
    R = L + 1
    # 先頭の文字が L のものの最後、R のものの最初、で境界
    arr = [L] + [K] * (N-1)
else:
    """
    [3,3,3,3,3] だと 手前に3 33 333 3333 が余分。2歩戻る。
    """
    arr = [(K+1)//2] * N
    x = N//2# x歩 戻る
    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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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):
    if ans[-1] == 1:
      ans.pop()
    else:
      ans[-1] -= 1
      while len(ans) < n:
        ans.append(k)
  print(*ans)

Submission status: Accepted

Solution code:
K, N = 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)))

Submission status: Accepted

Solution code:
# seishin.py
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)

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]

K, N = rdi()

if K == 1:
        print " ".join(["1"] * ((N+1)/2))
        sys.exit(0)

if K % 2 == 0:
        print K/2,
        for i in range(N-1):
                print K,
        print
        sys.exit(0)

t = [ K/2+1 ] * N
j = N-1
for i in range(N/2):
        if t[j] == 1:
                j -= 1
        else:
                t[j] -= 1
                for k in range(j+1, N):
                        t[k] = K
                j = N-1
        #print t
print " ".join([ str(x) for x in t[:j+1]])