← 返回题目列表

AtCoder · arc183_a

A. 良好序列的中位数

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你正整数 N 和 K.

长度的整数序列 NK 其中每个整数来自 1 to N 完全显示 K 次被称为 好 整数序列。

让 S 是良好整数序列的数量。 找到 \operatorname{floor}((S+1)/2)- 按字典顺序排列的第一个好整数序列。 在这里, \operatorname{floor}(x) 表示不超过的最大整数 x.

序列的字典顺序是什么?

一个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 如果下面的 1. 或 2. 成立。 在这里, |S| 和 |T| 代表的长度 S 和 T。

  1. |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两者成立:
    • (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

有六个好的整数序列:

  • (1,1,2,2)
  • (1,2,1,2)
  • (1,2,2,1)
  • (2,1,1,2)
  • (2,1,2,1)
  • (2,2,1,1)

因此,答案是按字典顺序排列的第三个序列, (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