Forum@DeGiorgi :: Pogledajte temu - Još jedan zadatak s natjecanja

through

[^/[Print]\]

Forum@DeGiorgi -> Osnove algoritama

#1: Još jedan zadatak s natjecanja Autor/ica: krcko,

Postano: 7:32 čet, 25. 1. 2018
—
Prošli tjedan održano je još jedno školsko natjecanje iz informatike. Ovo je po mojem sudu najzanimljiviji zadatak za 8. razred OŠ.

Citat:

Zadatak: Drvored (90 bodova)

Ž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šenom poslu 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.

PRIMJERI TEST PODATAKA

ulaz
HJHHBBH
izlaz
4
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

Ponovit ćemo natjecanje od lani za studente koji su upisali OA 2017./18. Tko prvi napiše rješenje ovdje na forumu, dobiva peticu za zalaganje i celebrity status na usmenom Very Happy

Priznaju se rješenja u Pythonu ili nekom drugom programskom jeziku, ili samo opis algoritma. Hint je da proučite Hammingovu metriku.

#2: Autor/ica: shranj,

Postano: 0:42 ned, 4. 2. 2018
—

Kod:

drvored=raw_input("Drvored: ")
duljina=len(drvored)
pomdrvored=[0]*duljina

b=0
h=0
j=0

splitano=[drvored[i:i+1] for i in xrange(duljina)]

for i in range (duljina):
if splitano[i]=='B':
b=b+1
elif splitano[i]=='H':
h=h+1
elif splitano[i]=='J':
j=j+1

min=duljina*2

#slucaj BHJ

i=0
br=0
for k in range (b):
pomdrvored[i]='B'
i=i+1
for k in range (h):
pomdrvored[i]='H'
i=i+1
for k in range (j):
pomdrvored[i]='J'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

#slucaj BJH

i=0
br=0
for k in range (b):
pomdrvored[i]='B'
i=i+1
for k in range (j):
pomdrvored[i]='J'
i=i+1
for k in range (h):
pomdrvored[i]='H'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

#slucaj HBJ

i=0
br=0
for k in range (h):
pomdrvored[i]='H'
i=i+1
for k in range (b):
pomdrvored[i]='B'
i=i+1
for k in range (j):
pomdrvored[i]='J'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

#slucaj HJB

i=0
br=0
for k in range (h):
pomdrvored[i]='H'
i=i+1
for k in range (j):
pomdrvored[i]='J'
i=i+1
for k in range (b):
pomdrvored[i]='B'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

#slucaj JBH

i=0
br=0
for k in range (j):
pomdrvored[i]='J'
i=i+1
for k in range (b):
pomdrvored[i]='B'
i=i+1
for k in range (h):
pomdrvored[i]='H'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

#slucaj JHB

i=0
br=0
for k in range (j):
pomdrvored[i]='J'
i=i+1
for k in range (h):
pomdrvored[i]='H'
i=i+1
for k in range (b):
pomdrvored[i]='B'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

print min*2

Program bi trebao raditi i za sve ostale primjere. Javite ako uočite pogrešku.

#3: Autor/ica: krcko,

Postano: 22:53 sri, 7. 2. 2018
—
Čestiam, rješenje je točno! Bilo bi elegantnije da ste dijelove koji se ponavljaju definirali kao funkcije, ali to službeno nismo radili na nastavi.

Dakle, ideja je prebrojati koliko puta se ponavljaju slova B, J, H i definirati šest nizova: BJH, BHJ, JBH, JHB, HBJ, HJB (slova se ponavljaju onoliko puta kao i u ulaznom nizu). Zatim se računa Hammingova udaljenost ulaznog niza od tih šest nizova i minimum se množi s 2. Hammingova udaljenost je jednostavno broj koordinata na kojima se nizovi razlikuju.

Forum@DeGiorgi -> Osnove algoritama

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.