Aluksi listan sisältö on [1,2,3,...,n]. Joka askeleella otat listan kaksi ensimmäistä alkiota ja siirrät ne listan loppuun käänteisessä järjestyksessä. Mikä on listan ensimmäinen alkio k askeleen jälkeen?

Esimerkiksi kun n=4 ja k=3, lista muuttuu näin:

[1,2,3,4] \rightarrow [3,4,2,1] \rightarrow [2,1,4,3] \rightarrow [4,3,1,2]

Tässä tapauksessa listan ensimmäinen alkio on siis 4.

Voit olettaa, että n on välillä 2 \dots 10^5 ja k on enintään 10^5. Tavoitteena on, että algoritmin aikavaativuus on O(n+k).

Python

Toteuta tiedostoon fliptwo.py funktio solve, joka palauttaa ensimmäisen alkion k askeleen jälkeen.

def solve(n,k):
    # TODO

if __name__ == "__main__":
    print(solve(4,3)) # 4
    print(solve(12,5)) # 11
    print(solve(99,555)) # 11
    print(solve(12345,54321)) # 9875

Java

Toteuta tiedostoon FlipTwo.java metodi solve, joka palauttaa ensimmäisen alkion k askeleen jälkeen.

public class FlipTwo {
    public int solve(int n, int k) {
        // TODO
    }
    
    public static void main(String[] args) {
        FlipTwo f = new FlipTwo();
        System.out.println(f.solve(4,3)); // 4
        System.out.println(f.solve(12,5)); // 11
        System.out.println(f.solve(99,555)); // 11
        System.out.println(f.solve(12345,54321)); // 9875
    }
}