P5780 [CTSC2011] Permutation

Momo really likes finding patterns and filling in numbers. For example, $1,4,7,( ),\cdots$: the difference between adjacent numbers is $3$, so the number in the parentheses should be $10$. Another example is $3,6,12,( ),\cdots$: each number is twice the previous one, so the number in the parentheses should be $24$. After playing this kind of game for many years, Momo got tired of arithmetic sequences and geometric sequences. When she sees the sequence $1,2,\cdots,n$, she wants to change its order as little as possible so that there is no subsequence with common difference $A$ or common ratio $B$. More specifically, given integers $n,A,B$, find a permutation $P=(P_1,P_2,\cdots,P_n)$ of $1$ to $n$ such that $\forall i,j \in \{1,2,\cdots,n\}$, if $i

The first line contains three positive integers $n,A,B$, with meanings as described above. Adjacent numbers are separated by one space.

The first line contains $n$ integers, the permutation $P$ you found. Adjacent numbers are separated by spaces.

**Sample Explanation** For this permutation, $S = 3$, which is the maximum possible $S$ when $n=4,A=3,B=2$. ------ **Scoring** Each test point is scored independently. For each test point, if your output is invalid, such as wrong file format, or the output solution does not satisfy the requirements, then you get $0$ points for that test point. Otherwise, let the $S$ value of your permutation be $a$, and the $S$ value of the permutation we provide be $b$. Your score for that test point is: - If $a \le b$, you get $10$ points. - Otherwise, the score is: $\max \{ [10 \times ( \exp (\frac{a}{b}-2)],1 \}$ ------ **Constraints** There are $10$ test points in total. The constraints are: | Test Point ID | $n$ | $A$ | $B$ | | :-----------: | :------: | :---------------: | :-----: | | $1$ | $\le 30$ | $\le n$ | $\le n$ | | $2$ | $\le 60$ | $A\bmod B\not =0$ | $\ge 4$ | | $3$ | $\le 70$ | $A\bmod B\not =0$ | $\ge 5$ | | $4$ | $\le 80$ | $A\bmod B\not =0$ | $\ge 6$ | | $5$ | $\le 90$ | $A\bmod B\not =0$ | $\ge 7$ | | $6$ | $\le 90$ | $\le n$ | $=1$ | | $7,8$ | $\le 90$ | $\le 5$ | $\le n$ | | $9$ | $=60$ | $=21$ | $=3$ | | $10$ | $=90$ | $=18$ | $=2$ | In all input data, both $A$ and $B$ are positive integers not exceeding $n$. Translated by ChatGPT 5