Piirileikki

Piirissä on $n$ leikkijää, jotka on numeroitu $1,2,\dots,n$. Vuoro kiertää piirissä ja joka toinen leikkijä lähtee pois, kunnes piiri on tyhjä. Tehtäväsi on selvittää järjestys, jossa leikkijät poistuvat.

Esimerkiksi kun $n=7$, alkutilanne näyttää tältä:

Leikki alkaa leikkijästä $1$ ja vuoro kiertää myötäpäivään. Ensin piiristä poistuu leikkijä $2$ ja siitä eteenpäin joka toinen leikkijä. Tässä tapauksessa leikkijät poistuvat järjestyksessä $[2,4,6,1,5,3,7]$.

Toteuta tiedostoon circlegame.py funktio find_order, jolle annetaan parametrina leikkijöiden määrä $n$. Funktion tulee palauttaa listana poistumisjärjestys.

Funktiosi tulee toimia tehokkaasti myös suurilla $n$:n arvoilla. Leikkijöiden poistaminen listan keskeltä olisi liian hidasta. Parempi tapa on esimerkiksi lisätä kierroksen aikana jäljelle jäävät leikkijät uuteen listaan.

Seuraavassa koodipohjassa viimeisessä testissä $n=10^5$ ja näytetään viisi viimeistä poistujaa. Funktiosi tulee toimia tehokkaasti tässäkin tapauksessa.

def find_order(n):
    # TODO

if __name__ == "__main__":
    print(find_order(1)) # [1]
    print(find_order(2)) # [2, 1]
    print(find_order(3)) # [2, 1, 3]
    print(find_order(7)) # [2, 4, 6, 1, 5, 3, 7]

    order = find_order(10**5)
    print(order[-5:]) # [52545, 85313, 36161, 3393, 68929]