In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Permutacja -elementowa jest ciągiem
-elementowym
składającym
się z różnych liczb ze zbioru
. Przykładowo,
ciąg
jest permutacją
-elementową.
W permutacjach liczb będą interesować nas najdłuższe rosnące podciągi.
W przykładowej permutacji mają one długość
i istnieją dokładnie dwa takie podciągi, a mianowicie
oraz
.
Superliczbą nazwiemy każdą liczbę, która należy do dowolnego
z najdłuższych rosnących podciągów. W permutacji
superliczbami są
, zaś liczba
superliczbą nie jest.
Twoim zadaniem jest dla zadanej permutacji znaleźć wszystkie superliczby.
Napisz program, który:
Wejście składa się z dwóch wierszy. W pierwszym wierszu znajduję
się jedna liczba ,
.
W drugim wierszu znajduję się
liczb
tworzących permutację
-elementową, pooddzielanych pojedynczymi
odstępami.
Wyjście powinno się składać z dwóch wierszy. W pierwszym wierszu
powinna znaleźć się jedna liczba - liczba superliczb
w wejściowej permutacji. W drugim
powinny znaleźć się superliczby pooddzielane pojedynczymi
odstępami, wymienione w kolejności rosnącej.
Dla danych wejściowych:
5 2 1 4 5 3
poprawną odpowiedzią jest:
4 1 2 4 5
Autor zadania: Jakub Pawlewicz.