猴子选大王

题目描述:

N只猴子选大王，选举办法如下：从头到尾1、2、3报数，凡报3的退出，余下的从尾到头1、2、3报数，凡报3退出；余下的又从头到尾报数，还是报3的退出；依此类推，当剩下的两只猴子时，取这时报数报1的为王。若想当猴王，请问最初占据什么位置？

输入格式:

输入一个数，表示有n只猴子

输出格式:

输出一个数

样例输入:

10

样例输出:

8

提示:

n<=1000

下面程序使用双向链表实现，请完善该程序：

n = int( input() )
lst = _______________   #填空2
for i in range( 1,n-1 ):
    lst.append( _____________ ) #填空2
lst.append ( [ n-2, n, -1 ] )
head1 = 0
head2 = n-1
tot = 0
f = 1
while tot < n-2 :
    if f :
        q = p = head1
        m = 1
        while p != -1:
            m += 1
            q = p
            p = lst[p][2]
            if m == 3 and p != -1:
                ______________________   #填空3
                if lst[p][2] != -1: _______________ #填空4
                if p==head2: head2 = q
                p = lst[p][2]
                tot += 1
                m = 1
    else :
        q = p = head2
        m = 1
        while p != -1:
            m += 1
            q = p
            p = lst[p][0]
            if m == 3 and p != -1:
                _____________________   #填空5
                if lst[p][0] != -1: ___________________ #填空6
                if p==head1: head1 = q
                p = lst[p][0]
                tot += 1
                m = 1
    ___________________  #填空7
if f:
    print( lst[head1][1] )
else:
    print( lst[head2][1] )

时间限制: 1000ms
空间限制: 256MB

---

来源: 原创