P3516 [POI2011]PRZ-Shift

    • 22通过
    • 90提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 POI 2011 Special Judge 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Byteasar bought his son Bytie a set of blocks numbered from $1$ to $n$ and arranged them in a row in a certain order.

    Bytie's goal is to rearrange the blocks so that they are ordered naturally, from the smallest number to the largest.

    However, the only moves Bytie is allowed to make are:

    putting the last block at the very beginning (move a), and putting the third block at the very beginning (move b).

    Help Bytie by writing a program that tells whether a given arrangement of blocks can be properly reordered, and tells the right sequence of moves if it is.

    有一个1..n的排列,有两种操作:

    (a) 将最后一个数移到最前面

    (b) 把第三个数移到最前面

    我们将连续进行k次同一个操作称为“一块操作”,表示为ka或kb。

    找到一个操作序列使得进行这些操作后,排列变为1,2,3,…,n。

    无解的话输出“NIE”

    输入输出格式

    输入格式:

    In the first line of the standard input there is a single integer $n$, $1\le n\le 2\ 000$.

    In the second line there are $n$ integers from the range $1$ to $n$, separated by single spaces.

    No number appears twice, and thus they represent the initial arrangement of the blocks.

    输出格式:

    If there is no sequence of moves leading to an arrangement with increasing blocks' numbers, your program should print out "NIE DA SIE" (there is no way in Polish), without the quotation marks.

    Otherwise there should be a single integer $m$ ($m\le n^2$), denoting the number of operations, in the first line.

    An operation is a $k$-fold execution of either a or b move.

    If $m>0$, then there should be a sequence of $m$ integers with either a or b appended in the second line.

    Thus $k$a (for $0<k<n$) denotes the $k$-fold execution of the move a.

    Analogously, $k$b (for $0<k<n$) denotes the $k$-fold execution of the move b.

    Furthermore, the characters appended to the numbers in the second line have to alternate.

    Should there be more than one solution, your program is free to pick one arbitrarily.

    输入输出样例

    输入样例#1: 复制
    4
    1 3 2 4
    输出样例#1: 复制
    4
    3a 2b 2a 2b

    说明

    有一个1..n的排列,有两种操作:

    (a) 将最后一个数移到最前面

    (b) 把第三个数移到最前面

    我们将连续进行k次同一个操作称为“一块操作”,表示为ka或kb。

    找到一个操作序列使得进行这些操作后,排列变为1,2,3,…,n。

    感谢cn:苏卿念 提供spj

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。