Permutacje

18.11.2009 - Marcin Oczeretko
Trudność

    Gorąco zachęcam do zmierzenia się z dwoma prostymi problemami programistycznymi. Wszystkie potrzebne do ich rozwiązania informacje znajdują się w artykule, choć możliwe, że zadania te będą mimo to wymagały chwili zastanowienia. Poprawność swoich programów możecie zbadać, wysyłając je na sprawdzaczkę.
   

Cykle

   Dla danej permutacji P określonej na zbiorze $ \{1,\ldots,n\} $ wyznacz długość najdłuższego cyklu występującego w jej rozkładzie na cykle.


   Podpowiedź: Rozkład na cykle bardzo łatwo wyznaczyć, gdy zauważymy, że $ P^2(k) = P(a_k) $ i $ P^3(k) = P^2(a_k) $.
   
    Wejście:
    Wejście składa się z dwóch wierszy. W pierwszym podawana jest liczba $ n $ ($ 1\le n \le 10^6 $) z treści zadania.
    W kolejnym wierszu pojawi się $ n $ liczb $ a_1, a_2, \ldots, a_n $ , ($ 1\le a_i \le n $), które definiują permutację $ P $ w następujący sposób: $ P(i) = a_i $.
   
    Wyjście:
    Należy wypisać jedną liczbę równą długości najdłuższego cyklu w $ P $.
   
    Przykład:
   
    Wejście:
    7
    1 3 4 5 6 7 2
   
    Wyjście:
    6

    Bo $ P = (1)(2 3 4 5 6 7) $
   

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Po kolei

   Wiemy już, że wszystkich permutacji zbioru $ \{1, \ldots, n\} $ jest $ n! $. Dla danego $ n $ wypisz zatem wszystkie te permutacje w kolejności leksykograficznej (tzn. jeśli $ a_1, a_2, \ldots, a_n $ i $ b_1, \ldots, b_n $ opisują permutacje $ A $ i $ B $, to $ A $ powinnieneś wypisać przed $ B $, jeśli istnieje takie $ i $, że: $ a_1 = b_1, a_2=b_2, \ldots, a_{i-1}=b_{i-1}, a_i < b_i $).
   
    Wejście:
    Pierwszy i jedyny wiersz zawiera jedną liczbę $ n $ ($ 1\le n\le 8 $).
   
    Wyjście:
    Należy wypisać w kolejnych wierszach wszystkie permutacje zbioru n-elementowego
   
    Przykład:
   
    Wejście:
    3
   
    Wyjście:
    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

4.333335
Twoja ocena: Brak Ocena: 4.3 (9 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com