Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP6_2D - Kompresja 2 |
Każdego roku po zakończeniu rundy zdalnej przenosimy zadania do naszego uczelnianego archiwum. Nigdy nie było z tym żadnego problemu, aż do tegorocznej edycji. Okazało się, że na serwerze, na którym znajduje się nasze archiwum nie ma już miejsca! Oczywiście pewnym rozwiązaniem jest kupno nowego dysku, ale my nigdy nie idziemy na łatwiznę i dlatego postanowiliśmy pozostawić rozwiązanie tego problemu Tobie. Wymyśliliśmy bardzo ciekawą i nowatorską ;-) metodę kompresji tekstu. Oto jej zasady:
- Każdy wczytany wyraz wypisujemy w oddzielnej linii.
- Jeżeli w bezpośrednim sąsiedztwie występują dwa albo większa liczba takich samych wyrazów to sprawdzamy czy opłacalne jest ich skompresowanie do postaci <wyraz>/<liczba_wystąpień>.
- Kompresja następuje wtedy i tylko wtedy, gdy wyraz w postaci skompresowanej zajmuje mniej znaków (wliczając w to znak przejścia do nowej linii) niż wypisanie <liczby_wystąpień> tego wyrazu w osobnych liniach (również wliczając w to znaki przejścia do nowej linii) np: zapis skompresowany test/2<LF> (7 znaków) jest bardziej opłacalny od zapisu test<LF>test<LF> (10) znaków, gdzie <LF> to znak przejścia do nowej linii.
Zaimplementuj ją!
Wejście
Na wejściu znajduje się tekst, który należy skompresować. 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 1000 liter.
Wyjście
Na wyjściu należy wypisać tekst w postaci skompresowanej. Każdy wyraz wypisujemy w osobnej linii. W przypadku, gdy skompresowaliśmy kilka wystąpień wyrazu w jedno, powinien on zostać wypisany w postaci <wyraz>/<liczba_wystąpień>.
Przykład
Wejście
hej polska gol la la la la la la la la la la la la la la la la la la hej polska gol la la la la la la la la la la la la la la la la la la
Wyjście
hej polska gol la/18 hej polska gol la/18
Dodane przez: | Maciej Boniecki |
Data dodania: | 2014-03-14 |
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 SCM qobi |