Aluksi listalla on kokonaisluvut [1,2,3,...,n] nousevassa järjestyksessä. Joka askeleella otat listan kaksi ensimmäistä alkiota ja siirrät ne listan loppuun käänteisessä järjestyksessä. Monenko askeleen jälkeen listan alkuperäinen järjestys on palautunut?

Esimerkiksi tapauksessa n=5 listan sisältö on aluksi [1,2,3,4,5] ja muuttuu sitten seuraavasti:

• [3,4,5,2,1]
• [5,2,1,4,3]
• [1,4,3,2,5]
• [3,2,5,4,1]
• [5,4,1,2,3]
• [1,2,3,4,5]

Tässä tapauksessa siis 6 askeleen jälkeen listan järjestys on palautunut.

Voit olettaa, että n on välillä 2 \dots 10^9. Huomaa, että n on suuri, joten ei ole mahdollista luoda niin suurta listaa ja simuloida prosessia, vaan sinun tulee keksiä tehokkaampi algoritmi.

Python

Toteuta tiedostoon fullround.py funktio count, joka antaa askelten määrän.

def count(n):
    # TODO

if __name__ == "__main__":
    print(count(2)) # 2
    print(count(5)) # 6
    print(count(31)) # 240
    print(count(1234567)) # 381038919372

Java

Toteuta tiedostoon FullRound.java metodi count, joka antaa askelten määrän.

public class FullRound {
    public long count(int n) {
        // TODO
    }

    public static void main(String[] args) {
        FullRound f = new FullRound();
        System.out.println(f.count(2)); // 2
        System.out.println(f.count(5)); // 6
        System.out.println(f.count(31)); // 240
        System.out.println(f.count(1234567)); // 381038919372
    }
}