Školska razina 2018 / Primjena algoritama OŠ / Osnovna škola (8. razred) - 3. zadatak

Želimo posaditi drvored koji će imati stabla bukve (B), hrasta (H) i jele (J). Drvored je zamišljen tako da su sva stabla istog tipa uvijek uzastopna. Npr. drvoredi BBHHJJ, HJJBB i JJHHBB zadovoljavaju navedeno pravilo, dok drvored HJH ne zadovoljava pravilo, budući da hrastovi nisu susjedni.

Radnik Dudo je posadio drvored stavljajući zrno po zrno sjemena u zemlju. Nažalost, tek je po završetku posla saznao da je drvored morao poštovati navedeno pravilo. Sada mora presložiti sjeme.

Dudo raspolaže samo sjemenom koje je već u zemlji, a s njim može činiti dvije stvari:

1. izvaditi sjeme iz zemlje s nekog mjesta i spremiti ga u torbu;
2. posaditi sjeme iz torbe u zemlju na neko mjesto s kojeg je sjeme izvađeno.

Svaka od ove dvije aktivnosti traje točno jednu minutu.

Pomozite Dudi i odredite koliko mu je najmanje minuta potrebno da završi posao.

Ulazni Podaci

U prvom i jedinom retku nalazi se niz znakova od barem jednog znaka čija duljina neće prelaziti \(20\) - početno stanje drvoreda. Niz će se sastojati samo od velikih slova B, H i J.

Izlazni Podaci

U jednom retku treba ispisati traženu vrijednost iz teksta zadatka.

Bodovanje

U test podacima vrijednim \(63\) boda, Dudi će se uvijek vremenski najviše isplatiti reorganizirati sjeme tako da u završnom poretku prvo dolaze svi hrastovi, zatim sve bukve, a na kraju sve jele.

Primjeri test podataka

Ulaz

HJHHBBH

Izlaz

4

Objašnjenje

Optimalno bi bilo: izvadi sjeme jele s drugog mjesta; izvadi sjeme hrasta sa sedmog mjesta; posadi sjeme jele na sedmo mjesto; posadi sjeme hrasta na drugo mjesto.

Ulaz

HHBJ

Izlaz

0

Ulaz

JBJBHJBHJH

Izlaz

10