4 - Cen*ura
Vremensko ograničenje | Memorijsko ograničenje |
---|---|
1000ms | 256MB |
Sloboda govora je divna stvar, ali neke ideje su prosto previše loše da bi se širile! Zato je oformljena Kontrolna Organizacija Štetnih Ideja (KOŠI), koja treba da pomogne ljudima da se "ne zanesu" previše u tekstovima koje pišu. Međutim, oni nisu baš najsigurniji kako to da rade još uvek, pa su odlučili da ako nešto urade, urade jednu stvar kako treba!
KOŠI je odredio najgoru reč koju mogu da smisle: zabranjenu reč *
(ASCII vrednost
Međutim, nije poenta uređivanja promeniti suštinu teksta, stoga moraju da promene što manje slova u tekstu
Opis ulaza
U prvom redu standardnog ulaza se nalazi tekst
Opis izlaza
U prvom redu standardnog izlaza napisati jedan prirodan broj koji predstavlja najmanji broj slova koje treba da zamenimo sa *
da bi ostvarili cilj. U drugom redu standardnog izlaza ispisati uređenu verziju teksta
Primer
Ulaz
Izlaz
Objašnjenja primera
Kada slovo p
cenzurišemo, ono se više ni ne pojavljuje u tekstu, pa
Ograničenja
Test primeri su podeljeni u 5 disjunktnih grupa:
- U test primerima vrednim
poena: zabranjena reč jea
- U test primerima vrednim
poena: sva slova zabranjene reči sua
- U test primerima vrednim
poena: zabranjena reč jeab
- U test primerima vrednim
poena: , a zabranjena reč jeabc
- U test primerima vrednim
poena: Bez dodatnih ograničenja
Bodovanje
Moguće je dobiti i parcijalne poene po test primeru: ako nađete pravilan najmanji broj cenzurisanih slova, ali ne i pravilnu cenzuru teksta, dobijate 80% bodova na tom primeru.
Autor | Tekst i test primeri | Analiza rеšenja | Testiranje |
---|---|---|---|
Pavle Martinović | Pavle Martinović | Pavle Martinović | Aleksa Plavšić |
Zabranjena reč je 'a'
U ovom podzadatku je očito dovoljno samo cenzurisati sva pojavljivanja slova 'a', što možemo da uradimo tako što linearno prođemo kroz
Sva slova zabranjene reči su 'a'
Isto je rešenje kao u prethodnom podzadatku, samo preskočimo prvih
Da li je jedna reč podsekvenca druge?
Da bismo umeli da pristupimo ovom problemu potrebno je analizirati algoritam kako proveravamo da li je jedna reč podsekvenca druge.
Ovo se vrši pohlepnim algoritmom. Naime, neka proveravamo da li je reč
Puno rešenje
Sada kada smo proučili taj algoritam, možemo da rešimo ceo zadatak.
Rešenje ćemo vršiti dinamičkim programiranjem, najsličnije DP rešenju za najdužu zajedničku podsekvencu dve niske. Naime neka je