INFORMATYKA DAM NAJ c++
Limit czasu: 1,00 s Limit pamięci: 512 MB
Permutacja liczb całkowitych1 , 2 , … , rznazywa się pięknym , jeśli nie ma sąsiednich elementów, których różnica wynosi1.
Danyn, skonstruuj piękną permutację, jeśli taka permutacja istnieje.
Wejście
Jedyny wiersz wejścia zawiera liczbę całkowitąn.
Dane wyjściowe
Wydrukuj piękną permutację liczb całkowitych1 , 2 , … , rz. Jeśli istnieje kilka rozwiązań, możesz wydrukować dowolne z nich. Jeśli nie ma rozwiązań, wydrukuj „NO SOLUTION”.
Ograniczenia
1 ≤ n ≤106
Przykład 1
Wejście:
5
Wyjście:
4 2 5 3 1
Przykład 2
Wejście:
3
Wyjście:
NO SOLUTION
Limit czasu: 1,00 s Limit pamięci: 512 MB
Permutacja liczb całkowitych1 , 2 , … , rznazywa się pięknym , jeśli nie ma sąsiednich elementów, których różnica wynosi1.
Danyn, skonstruuj piękną permutację, jeśli taka permutacja istnieje.
Wejście
Jedyny wiersz wejścia zawiera liczbę całkowitąn.
Dane wyjściowe
Wydrukuj piękną permutację liczb całkowitych1 , 2 , … , rz. Jeśli istnieje kilka rozwiązań, możesz wydrukować dowolne z nich. Jeśli nie ma rozwiązań, wydrukuj „NO SOLUTION”.
Ograniczenia
1 ≤ n ≤106
Przykład 1
Wejście:
5
Wyjście:
4 2 5 3 1
Przykład 2
Wejście:
3
Wyjście:
NO SOLUTION
Odpowiedź:
Propozycja rozwiązania w załączniku
Wyjaśnienie:
Uwaga:
dla n=1 nie ma sąsiadów - permutacja 1 jest piękna.
dla n=2 i n=3 nie istnieje permutacja piękna.
Dla pozostałych pomysł rozwiązania jest następujący:
najpierw wypisujemy kolejne elementy o wartościach parzystych a następnie kolejne elementy o wartościach nieparzystych. Dzięki temu sąsiednie elementy będą różnić się przynajmniej o 2.
Dlaczego najpierw parzyste a później nieparzyste a nie odwrotnie?
W przeciwnym wypadku dla n=4 otrzymalibyśmy:
1 3 2 4
Różnica między 3 a 2 jest równa 1 - nie spełnia wymagań.
Przy większych wartościach n - nie ma znaczenia, ale pozostawiam dla jednolitego rozwiązania.