III Olimpiada Informatyczna 1995/96
|
Zadanie: PER
|
Autor: Wojciech Guzicki
|
Zawody III stopnia |
Plik źródłowy: | PER.??? (np. pas, c, cpp) |
Plik wykonywalny: | PER.exe |
Plik wejściowy: | PER.in |
Plik wyjściowy: | PER.out |
Permutację p0, p1, ... , pn-1 liczb naturalnych 0, 1, ... , n-1 nazywamy permutacją antyarytmetyczną, jeśli nie występuje w niej żaden trzywyrazowy ciąg arytmetyczny, tzn. nie istnieją takie trzy indeksy i < j < k, że liczby pi, pj, pk (w tej kolejności) tworzą ciąg arytmetyczny. Na przykład, ciąg liczb 3, 1, 0, 4, 2 jest permutacją antyarytmetyczną liczb 0, 1, 2, 3, 4. Natomiast ciąg 0, 5, 4, 3, 1, 2 nie jest permutacją antyarytmetyczną, ponieważ jego wyrazy - pierwszy, piąty i szósty: 0, 1, 2 tworzą ciąg arytmetyczny (także wyrazy drugi, czwarty i piąty: 5, 3, 1 oraz drugi, trzeci i czwarty: 5, 4, 3 tworzą ciągi arytmetyczne).
Wejście
W pliku tekstowym PER.IN jest zapisana jedna liczba całkowita n spełniająca nierówność
3 <= n <= 1000000.
Wyjście
W n kolejnych wierszach pliku tekstowego PER.OUT należy zapisać n różnych liczb
całkowitych ze zbioru {0, 1, ... , n-1}, każdą w osobnym wierszu. Liczby w kolejnych wierszach
powinny tworzyć permutację antyarytmetyczną liczb 0, 1, ... , n-1.
Przykład
Jeśli w pliku PER.IN jest zapisana liczba 5, to poprawnym rozwiązaniem jest następujący plik
PER.OUT:
3
1
0
4
2
Twój program powinien szukać pliku PER.IN w katalogu bieżącym i tworzyć plik PER.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę PER.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku PER.EXE.