#2747. 「CTSC2011」排列

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

沫沫很喜欢找规律填数字,譬如 1,4,7,(\ \ ), \cdots ,相邻的数相差为 3 ,括号中的数应为 10 ;又如 3,6,12, (\ \ ), \cdots ,每个数是前一个数的两倍,括号中的数应为 24

由于常年玩这种游戏,沫沫厌倦了等差数列与等比数列。当看到数列 1, 2, \cdots ,n 时,她想尽量小的改变其顺序使得不存在公差为 A 或者公比为 B 的子列。

具体地,给定整数 n, A, B ,求一个 1 n 的排列 P = (P_1, P_2, \cdots , P_n) ,满足 \forall i, j \in \{1, 2, \cdots , n\} ,若 i \lt j P_i \lt P_j ,则 P_j\not = Pi + A P_j \not = P_i \times B 。排列 P 保留原有顺序的程度 S 定义为:

S=\sum_{1\le i\lt j\le n,P_i\lt P_j} (P_j-P_i)

请你在满足前述要求的前提下,使得 S 的值尽量大。

输入格式

第一行包含三个正整数 n, A, B ,意义如前所述。相邻的数之间用一个空格隔开。

输出格式

第一行包含 n 个整数,为你求得的排列 P ,相邻的数之间用空格隔开。

样例

样例输入

4 3 2

样例输出

4 2 1 3

样例说明

该排列对应的 S = 3 ,是 n = 4,A = 3, B = 2 时能取到的最大的 S

数据范围与提示

评分方式

每个测试点单独评分。

对于每一个测试点,如果你的输出不合法,如文件格式错误、输出的解不符合要求等,该测试点得 0 分。
否则设你输出的排列对应 S 值为 a ,我们提供的排列对应 S 值为 b ,你在该测试点的得分如下:

  • 如果 a\ge b ,得 10 分;
  • 否则得分为:

\max \{ \lfloor 10\times (\exp (\frac{a}{b})-2)\rfloor,1\}

数据规模

总共 10 个测试点,数据范围满足:

测试点编号 n A B
1 \le 30 \le n
2 \le 60 A\bmod B\not =0 \ge 4
3 \le 70 \ge 5
4 \le 80 \ge 6
5 \le 90 \ge 7
6 \le n =1
7,8 \le 5 \le n
9 =60 =21 =3
10 =90 =18 =2

在所有输入数据中, A B 均为不超过 n 的正整数。