| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_15_02 - Kompresja 3 |
Wymyśliliśmy bardzo "ciekawą i nowatorską" metodę kompresji tekstu, a jako że jesteśmy bardzo zapracowani jej implementację pozostawiamy Tobie. Oto zasady:
- Tekst jest poddawany podwójnej kompresji, najpierw kompresowane są litery w obrębie wyrazów, a następnie kompresowane są wyrazy.
- Kompresja liter działa następująco: jeżeli dana litera występuje w bezpośrednim sąsiedztwie więcej niż jeden raz zastępujemy je jednokrotnym wystąpieniem tej litery, po której następuje znak * oraz liczba wystąpień. Kompresji liter dokonujemy tylko wtedy gdy ich długość po skompresowaniu jest mniejsza niż długość liter bez kompresji.
- Kompresja wyrazów działa następująco: jeżeli dany wyraz (ze skompresowanymi literami bądź nie) występuje w bezpośrednim sąsiedztwie więcej niż jeden raz zastępujemy go pojedynczym jego wystąpieniem po którym następuje znak / oraz liczba jego wystąpień. Podobnie jak ma to miejsce w przypadku liter kompresję przeprowadzamy tylko wtedy gdy wyraz w postaci skompresowanej jest krótszy niż dana liczba jego wystąpień porozdzielana spacjami.
Oczywiście potrzebujemy również programu, który będzie w stanie odwrócić cały proces dlatego pierwszą linię każdego testu stanowi wyraz KOMPRESJA albo DEKOMPRESJA i określa on sposób w jaki program powinien traktować tekst na wejściu. Wejście może składać się z wielu linii skompresowanego lub nieskompresowanego tekstu, wyjście natomiast powinno znajdować się wyłącznie w jednej linii. Wyrazy powinny być oddzielone pojedynczymi spacjami.
Wejście
W pierwszej linii wejścia znajduje się jeden wyraz KOMPRESJA albo DEKOMPRESJA określający operację jaką należy wykonać. W kolejnych liniach znajduje się tekst na którym trzeba wykonać daną operację. Tekst składa się z nie więcej niż 1000 wyrazów. Każdy wyraz zawiera wyłącznie małe litery alfabetu angielskiego zaś jego długość nie przekracza 2000 znaków.
Wyjście
Na wyjściu należy wypisać przetworzony tekst w jednej linii. Wyrazy należy oddzielić pojedynczą spacją.
Przykład 1
Wejście
KOMPRESJA kkkkompressja kkkkompressja kkkkompressja tekstu tekstu
Wyjście
k*4ompressja/3 tekstu/2
Przykład 2
Wejście
DEKOMPRESJA d*4ekompres*4ja/2 te*5kstu/2
Wyjście
ddddekompressssja ddddekompressssja teeeeekstu teeeeekstu
| Dodane przez: | Maciej Boniecki |
| Data dodania: | 2014-03-29 |
| Limit czasu wykonania programu: | 0.300s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM64 GOSU |
| Pochodzenie: | ALGOLIGA |
ukryj komentarze
|
|||||
|
2014-03-30 00:59:40 Tomasz Gandor
Sporo testów. Można się emocjonalnie wykończyć patrząc na stronę statusu, jak numerek długo leci ("uruchamianie sędziego"). Uff. |
|||||
|
2014-03-29 20:17:46 Karol Waszczuk
Czy do długości nieskompresowanych takich samych wyrazów pod rząd wliczane są spacje je udzielające? |
|||||
|
2014-03-29 17:32:54 Maciej Boniecki
Może, dodatkowe białe znaki są ignorowane. |
|||||
|
2014-03-29 17:31:40 Karol Waszczuk
Czy na końcu wyjścia może znaleźć się spacja? |
|||||
|
2014-03-29 15:45:19 Maciej Boniecki
Jednocześnie pragnę zapewnić, że zadanie da się rozwiązać na C++ string. Rozwiązanie wzorcowe dla wszystkich testów na SPOJu z użyciem string i stringstream działa w łącznym czasie 0.1s. |
|||||
|
2014-03-29 15:27:57 Maciej Boniecki
Niestety z przykrością muszę stwierdzić, że w teście wydajnościowym wygenerowanym automatycznie zabrakło części spacji rozdzielających wyrazy przez co cały test jest błędny. Pozostałe testy są poprawne. Przepraszam za kłopot i niepotrzebne trudzenie się z błędnym testem. Rozpoczynamy ponowną ocenę. |
|||||
|
2014-03-29 14:53:12 Maciej Boniecki
Nie, tylko małe litery alfabetu angielskiego. |
|||||
|
2014-03-29 14:39:21 Filip Tokarski
A czy w tekście przed kompresją mogą występować znaki "*", oraz "/"? |
|||||
|
2014-03-29 14:34:23 Maciej Boniecki
Tak, jedyna różnica to taka, że nie musi znajdować się w 1 linii. |
|||||
|
2014-03-29 14:27:29 Tomek
Czy w przypadku, gdy test zaczyna się "DEKOMPRESJA", tekst musi być zkompresowany według zasad dla testu : "KOMPRESJA". |
|||||
RSS