Runda 7 - Dżungla

02.11.2009 - Damian Rusak
TrudnośćTrudność

 

Zawody stałe, runda 7

Limit czasowy: 2s; Limit pamięciowy: 64 MB


Dżungla


Ekspedycja naukowa wyruszyła do dzikiej i niezbadanej dżungli w dalekiej i niedostępnej części świata. Podczas niebezpiecznej wyprawy badaczom udało się znaleźć starożytne zapiski zaginionej cywilizacji. Przedstawiciele tej cywilizacji oddawali cześć wężom, wysławiając ich spryt, wolę przetrwania i olśniewające barwy ich łusek. W istocie, naukowcy odkryli setki gatunków niezwykle barwnych węży. Zapiski wspominają o wspaniałym ołtarzu, na którym węże składane były w ofierze, w celu zapewnienia kapłanom ich boskich cech. Ołtarz był kształtu koła, a jego brzeg wyłożony był drogocennymi kamieniami, których kolory miały imitować barwy wężowych łusek. Aby wąż mógł zostać złożony w ofierze, należało go ułożyć w okół ołtarza na kamieniach tak, aby barwy węża pasowały do barw kamieni. Naukowcy znają opis kamieni na ołtarzu, upatrzyli sobie też pewien gatunek węża. Zastanawiają się na ile różnych sposobów ten wąż mógłby zostać złożony w ofierze przez członków zaginionej cywilizacji. Pomóż im!

Zadanie:

Mając dany opis kamieni zdobiących brzeg ołtarza, oraz kolory łusek węża, odpowiedz na pytanie, na ile sposobów ten wąż mógł zostać ułożony na ołtarzu, aby kolory jego łusek pasowały do kolorów kamieni.

Wejście:


Pierwsza linia wejścia zawiera dwie liczby - n m (1 < n < m < 1000000) oznaczające kolejno długość węża (czyli ilość barwych segmentów jego ciała) i ilość kamieni na brzegu ołtarza. W pierwszej linii znajduje się słowo złożone z n liter alfabetu angielskiego, oznaczające barwy kolejnych łusek węża. W następnej linii znajduje się słowo złożone z m liter alfabetu angielskiego, oznaczających barwy kolejnych kamieni na ołtarzu. Ołtarz jest kolisty, więc pierwszy kamień następuje po ostatnim.

Wyjście:

Pierwsza linia wyjścia powinna składać się z jednej liczby całkowitej, oznaczającej ilość sposobów, na które można ułożyć węża na ołtarzu. W drugiej linii należy wypisać numery kamieni (numerujemy je zgonie z ich pozycjami w ciągu), na których lec może pierwsza część ciała węża, jeśli układamy go na ołtarzu "zgodnie z ruchem wskazówek zegara" (patrz przykład). W drugiej linii należy wypisać numery kamieni, na których można umieścić ostatnią część ciała węża, gdy układamy go w drugą stronę.

Przykład:

Wejście:

3 11

aab

aababaabbab

Wyjście:

4

1 6

5 11

Objaśnienie: Węża w pozycji aab można dopasować na pierwszym i szóstym kamieniu. Węża w odwrotnej pozycji, baa, moża umieścić na piątym bądź jedenastym kamieniu.

 

Zapraszamy do dyskusji na temat zadania na forum.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Anna Piekarska1016:29:29
2Wojciech Kuprianowicz1099:51:38
3Darek Bukowski10100:37:59
4Kuba Skudlarski10109:52:34
5Agnieszka Dudek10111:17:26
6Mateusz Wasilewski10530:51:07
7Przemysław Derengowski101479:27:53
8Michal Zgliczynski101879:13:00
9Kamil Łukasz103491:57:32
10Maciej Kisiel105740:33:28
11Michał Karpiński107766:16:31
12Łukasz Hanuszczak1010013:46:34
13Maciej Szeptuch9175:38:01
14Patrick Hess94521:40:02
15Adam Laskowski8809:30:31
16Katarzyna Mandziuk7148:19:05
17Jadwiga Andryszak71403:19:39
18Kamil Trusiak1108:29:52
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com