/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
正整数 N,K が与えられます．
1 以上 N 以下の整数がそれぞれ K 回ずつ登場する長さ NK の整数列を good な整数列と呼ぶことにします．
good な整数列の個数を S とおきます． 辞書順で \operatorname{floor}((S+1)/2) 番目の good な整数列を求めてください． なお，\operatorname{floor}(x) は x を超えない最大の整数を表します．
数列の辞書順とは？
数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは，下記の 1. と 2. のどちらかが成り立つことを言います． ここで，|S|, |T| はそれぞれ S, T の長さを表します．
- |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})．
- ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して，下記の 2 つがともに成り立つ．
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい．
制約
- 1 \leq N \leq 500
- 1 \leq K \leq 500
- 入力される値はすべて整数
入力
入力は標準入力から以下の形式で与えられる．
N K
出力
答えの整数列を，要素を空白区切りにして出力せよ．
入力例 1
2 2
出力例 1
1 2 2 1
good な整数列は以下の 6 通りです．
- (1,1,2,2)
- (1,2,1,2)
- (1,2,2,1)
- (2,1,1,2)
- (2,1,2,1)
- (2,2,1,1)
よって，この中で辞書順で 3 番目の (1,2,2,1) が答えになります．
入力例 2
1 5
出力例 2
1 1 1 1 1
入力例 3
6 1
出力例 3
3 6 5 4 2 1
入力例 4
3 3
出力例 4
2 2 2 1 3 3 3 1 1
Score : 400 points
Problem Statement
You are given positive integers N and K.
An integer sequence of length NK where each integer from 1 to N appears exactly K times is called a good integer sequence.
Let S be the number of good integer sequences. Find the \operatorname{floor}((S+1)/2)-th good integer sequence in lexicographical order. Here, \operatorname{floor}(x) represents the largest integer not exceeding x.
What is lexicographical order for sequences?
A sequence S = (S_1,S_2,\ldots,S_{|S|}) is lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) if either 1. or 2. below holds. Here, |S| and |T| represent the lengths of S and T, respectively.
- |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- There exists an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i is (numerically) smaller than T_i.
Constraints
- 1 \leq N \leq 500
- 1 \leq K \leq 500
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
Output
Print the desired integer sequence, with elements separated by spaces.
Sample Input 1
2 2
Sample Output 1
1 2 2 1
There are six good integer sequences:
- (1,1,2,2)
- (1,2,1,2)
- (1,2,2,1)
- (2,1,1,2)
- (2,1,2,1)
- (2,2,1,1)
Therefore, the answer is the 3rd sequence in lexicographical order, (1,2,2,1).
Sample Input 2
1 5
Sample Output 2
1 1 1 1 1
Sample Input 3
6 1
Sample Output 3
3 6 5 4 2 1
Sample Input 4
3 3
Sample Output 4
2 2 2 1 3 3 3 1 1