Polish version    English version  
  Historia OI -> III OI 1995/1996 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
III Olimpiada Informatyczna 1995/96

Zadanie: PER
Autor: Wojciech Guzicki
Permutacje antyarytmetyczne

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).

Zadanie

Ułóż program, który:
  • wczytuje z pliku tekstowego PER.IN jedną liczbę naturalną n,
  • znajduje i zapisuje w pliku tekstowym PER.OUT jedną dowolną permutację antyarytmetyczną liczb 0, 1, ... , n-1.

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.




Wersja do druku