编程介的小学生 2017-03-25 11:13 采纳率: 20.5%
浏览 818
已采纳

Railroad Sort

Consider the railroad station that has n dead-ends designed in a way shown on the picture. Dead-ends are numbered from right to left, starting from 1.

Let 2n railroad cars get from the right. Each car is marked with some integer number ranging from 1 to 2n, different cars are marked with different numbers.

You can move the cars through the dead-ends using the following two operations. If the car x is the first car on the path to the right of the dead-end i, you may move this car to this dead-end. If the car y is the topmost car in the dead-end j you can move it to the path on the left of the dead-end. Note, that cars cannot be moved to the dead-end from the path to its left and cannot be moved to the path on the right of the dead-end they are in.

Your task is to rearrange the cars so that the numbers on the cars listed from left to right were in the ascending order and all the cars are to the left of all the dead-ends.

One can prove that the required rearranging is always possible.

Input

The input contains multiple test cases. Each test case occupies two lines. The first line of each case contains n - the number of dead-ends (1 <= n <= 13). The second line contains 2n integer numbers - the numbers on the cars, listed from left to right.

A case with n = 0 ends up the input file.

Output

For each case, output the sequence of operations in one line. Each operation is identified with the number of the car moved in this operation. The type of the operation and the dead-end used are clearly determined uniquely.

Sample Input

2
3 2 1 4
2
1 2 3 4
0

Sample Output

3 3 2 2 1 1 4 4 3 2 1 1 2 3 4 4
1 2 2 1 2 1 3 3 4 4 1 2 3 3 4 4

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-04-02 15:41
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型