最坏安排

火车头需要带动按ABCD的顺序依次排列的四节车厢。

不过在挂上火车头前这些车厢并不总是按正确的顺序排列好的，排列车厢的工具是一个大型旋转台。

火车驶上旋转台后可以选择在某处分离部分车厢，然后火车头先带着未被分离的车厢离开旋转台，其余车厢则留在旋转台上并旋转180度后再与原车体相连，随后火车再开上旋转台。重复这一过程，直到顺序正确为止。

例如以ADCB顺序排列的车厢，可以先在AD之间断开，然后DCB旋转180度变为BCD，再连接后就是正确顺序。

假设火车司机张三头脑简单，总是选择先将A放到正确的位置，再将B放到正确的位置，以此类推。那么使用这种策略时的最坏安排（即需要使用旋转台的次数最多的安排）将会是DACB和DBAC，对应的次数都是五次（而最有效方法只需要三次旋转）。按张三的策略重排DACB的步骤如下图所示：

可以验证，六节车厢时共有24种最坏安排，其中字典序第十位的是DFAECB。

求有十一节车厢时字典序第2011位的最坏安排。

本题难度:

解答

可以看出最坏安排需要$2N-3$次操作。

以A为例，若A不在首位，那么需要先在A处切割，旋转一次将其放到队列尾，再旋转一次将其放到队首。

前N-2个车厢都需要如此操作，共$2N-4$次，最后两节车厢只需旋转一次，因此总共$2N-3$次。

由于$11!$是千万级不算太大，因此直接枚举所有排列计算即可得结果$CAGBIHEFJDK$。

注：以下代码为Python 3，因Python 3的字符串处理效率更优，代码中还打印了进度信息。

import itertools

symbols="ABCDEFGHIJK"
target=2011

for c in itertools.permutations(symbols,len(symbols)):
    s=list(c)
    i=0
    while i < len(symbols)-1:
        if s[0]==symbols[i] or (len(s)>2 and s[-1]==symbols[i]):
            break
        else:
            k=s.index(symbols[i])
            s=s[:k]+s[:k-1:-1]
            s.pop()
            s.reverse()
            i+=1
    if i==len(symbols)-1:
        target-=1
        if target==0:
            print("".join(c))
            break
        elif target%100==0:
            print(target,"left to be found")