这是问题的简单版本。版本之间的差异在于,在这个版本中,第二个测试是$$$n=100\,000$$$。这个问题不允许 hack。
让我们调用一个整数序列 $$$a_1, a_2, \ldots, a_n$$$ 距离凸 如果 $$$|a_{i} - a_{i-1}| \lt |a_{i+1} - a_{i}|$$$ 对于每个 $$$1 \lt i \lt n$$$。换句话说,如果您按顺序跳过数轴上的点 $$$a_1, a_2, \ldots, a_n$$$,则每次下一次跳跃都严格地比前一次更长。
给你两个整数 $$$n$$$ 和 $$$m$$$。寻找一个 距离凸 序列 $$$a$$$,长度为 $$$n$$$,包含 最多 $$$m$$$ 不同值。就跳跃顺序而言,这意味着您需要进行 $$$(n-1)$$$ 不断增加长度的跳跃,同时访问最多 $$$m$$$ 个不同点。 $$$-10^{18} \le a_i \le 10^{18}$$$ 应该适用于所有 $$$1 \le i \le n$$$。
输入
输入由单行上的两个整数 $$$n$$$ 和 $$$m$$$ 组成。
此问题只有 2 个测试。
- $$$n = 8$$$,$$$m = 6$$$;
- $$$n = 100\,000$$$,$$$m = 15\,000$$$。
此问题不允许进行黑客攻击。
输出
打印一个距离凸序列 $$$a_1, a_2, \ldots, a_n$$$ 最多包含 $$$m$$$ 个不同值。 $$$-10^{18} \le a_i \le 10^{18}$$$ 应该适用于所有 $$$1 \le i \le n$$$。
如果有多个解决方案,请打印其中任何一个。
示例
输入复制
8 6
输出复制
1 1 3 6 10 3 11 1
注意
序列$$$[1, 1, 3, 6, 10, 3, 11, 1]$$$的长度为$$$n=8$$$,包含$$$5$$$个不同的值,小于或等于$$$m=6$$$。连续值之间的差异为$$$0,2,3,4,7,8,10$$$,严格递增的序列。
$$$[1, 1, 2, 4, 8, 16, 32, 1]$$$ 将是另一个有效答案。