In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
W ramach nowej kampanii reklamowej, duża firma z Gdyni zamierza zaprezentować w mieście swoje logo. Firma przeznaczy na nie cały budżet kampanii, musi ono zatem być naprawdę imponujące. Jeden z menedżerów wpadł na pomysł użycia jako części logo całych budynków.
Logo składa się z pionowych pasków różnej wysokości, numerowanych od lewej
do prawej liczbami
.
Logo można opisać permutacją
liczb
.
Opis taki oznacza, że pasek o numerze
jest najniższy wśród pasków logo,
pasek o numerze
drugi w kolejności... wreszcie pasek
jest
najwyższy. Dokładne wysokości pasków z punktu widzenia opisu nie są istotne.
Wzdłuż głównej ulicy Gdyni stoi budynków. Ku Twojemu zdziwieniu, ich
wysokości są parami różne. Twoje zadanie polega na znalezieniu miejsc, w których
logo pasuje do układu budynków.
Pomóż firmie znaleźć wszystkie spójne fragmenty ciągu budynków, które pasują do
logo, tzn. -szy budynek tego fragmentu jest najniższy,
-gi drugi
najniższy, itd.
Na przykład podciąg budynków o wysokościach
,
,
pasuje do logo
opisanego permutacją
, jako że trzeci budynek (o wysokości
) jest
najniższy, pierwszy z lewej (
) - drugi co do wysokości, zaś drugi (
)
najwyższy.
Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite oraz
(
). Drugi wiersz zawiera
liczb
będących permutacją zbioru
. Oznacza to, że
oraz
dla
.
Trzeci wiersz zawiera
liczb całkowitych
(
dla
) - wysokości budynków. Liczby
są parami
różne. W każdym wierszu liczby rozdzielone są pojedynczymi odstępami.
W testach wartych łącznie przynajmniej punktów zachodzi
oraz
.
W testach wartych przynajmniej punktów,
oraz
.
Pierwszy wiersz standardowego wyjścia powinien zawierać liczbę pasujących
fragmentów. Drugi wiersz powinien zawierać
liczb - indeksów (licząc od
)
budynków, od których te fragmenty się zaczynają. Indeksy należy wypisać w
kolejności rosnącej, pooddzielane pojedynczymi odstępami. W wypadku gdy
,
drugi wiersz powinien pozostać pusty.
Dla danych wejściowych:
5 10 2 1 5 3 4 5 6 3 8 12 7 1 10 11 9
poprawną odpowiedzią jest:
2 2 6
Wyjaśnienie do przykładu: Ciągi oraz
pasują do logo
opisanego permutacją
. W szczególności w pierwszym z nich najniższy
jest budynek numer
(o wysokości
), drugim najniższym jest budynek numer
(o wysokości
), trzecim - budynek numer
(o wysokości
) i tak
dalej.
Autorzy zadania: Tomasz Kulczyński, Tomasz Waleń.