W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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ń.