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]