Listassa on lukujen 1,2,\dots,n permutaatio, missä n on parillinen. Tehtäväsi on selvittää, voiko listan järjestää seuraavan operaation avulla: valitaan kokonaisluku i väliltä 1 \dots n/2 ja vaihdetaan keskenään listan i ensimmäistä ja i viimeistä lukua järjestys säilyttäen.

Esimerkiksi kun n=4, listan [3,1,4,2] voi järjestää seuraavasti:

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

Tässä tapauksessa ensimmäisessä operaatiossa i=2 ja toisessa operaatiossa i=1. Sen sijaan listaa [3,1,2,4] ei ole mahdollista järjestää mitenkään operaation avulla.

Voit olettaa, että n on välillä 2 \dots 10^5. Tavoitteena on, että algoritmin aikavaativuus on O(n) tai O(n \log n).

Python

Toteuta tiedostoon movesort.py funktio check, joka tarkastaa, voiko listan järjestää.

def check(t):
    # TODO

if __name__ == "__main__":
    print(check([3,1,4,2])) # True
    print(check([3,1,2,4])) # False
    print(check([1,2])) # True
    print(check([4,5,6,1,2,3])) # True
    print(check([4,5,6,3,2,1])) # False

Java

Toteuta tiedostoon MoveSort.java metodi check, joka tarkastaa, voiko listan järjestää.

public class MoveSort {
    public boolean check(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        MoveSort m = new MoveSort();
        System.out.println(m.check(new int[] {3,1,4,2})); // true
        System.out.println(m.check(new int[] {3,1,2,4})); // false
        System.out.println(m.check(new int[] {1,2})); // true
        System.out.println(m.check(new int[] {4,5,6,1,2,3})); // true
        System.out.println(m.check(new int[] {4,5,6,3,2,1})); // false
    }
}