Tekmovalni dnevi Instituta Jožef Stefan

Avtomobili

Podroben opis naloge

Na karirasti mreži velikosti w × h (w stolpcev, h vrstic) je definirano dirkališče. Vsako polje mreže je bodisi prevozno bodisi neprevozno. Nekatera izmed prevoznih polj tvorijo štartno črto, nekatera pa tvorijo kontrolna območja. Na mreži si mislimo tudi koordinatni sistem: stolpce oštevilčimo od leve proti desni s koordinatami od 0 do w − 1, vrstice pa od zgoraj navzdol s koordinatami od 0 do h − 1.

Primer:

Pot vozila po dirkališču predstavimo z zaporedjem koordinat obiskanih točk:

(x0, y0), (x1, y1), (x2, y2), …, (xk, yk).

Dolžino poti definiramo kot število korakov na njej; dolžina zgornje poti je torej k.

Cilj te naloge je poiskati čim krajšo pot, ki ustreza vsem naslednjim zahtevam:

Posebej poudarimo, da nas pri preverjanju, ali pot ustreza gornjim zahtevam, zanimajo le točke (xt, yt), na katerih se začenja ali končuje posamezni korak. Na primer: točki (xt−1, yt−1) in (xt, yt) morata biti prevozni, ni pa nujno, da cela daljica od (xt−1, yt−1) do (xt, yt) leži na prevoznem delu mreže (dovoljeno je torej „sekanje ovinkov“). Podobno, če niti (xt−1, yt−1) niti (xt, yt) ne ležita na nekem kontrolnem območju, potem se šteje, da v tem koraku tega kontrolnega območja nismo obiskali, četudi mogoče nek del daljice od (xt−1, yt−1) do (xt, yt) prečka kakšno od polj, ki pripadajo temu kontrolnemu območju.

Naslednja slika kaže primer poti, ki ustreza skoraj vsem zgoraj opisanim pogojem; z njo je narobe le to, da ne obišče četrtega kontrolnega območja.

Oblika vhodne datoteke

V prvi vrstici vhodne datoteke je niz z imenom naloge (Avtomobili), v drugi pa številka testnega primera, na katerega se nanaša ta vhodna datoteka. V naslednji vrstici sta števili w (širina mreže) in h (višina mreže), ločeni s presledkom. To sta celi števili, večji ali enaki 1 ter manjši ali enaki 1000. Sledi h vrstic, ki podajajo opis dirkališča. V vsaki vrstici je niz w znakov, ki za posamezna polja te vrstice povedo, ali so prevozna in ali pripadajo kakšnemu kontrolnemu območju.

Neprevozna polja so predstavljena s pikami (.). Vsa ostala polja so prevozna. Polja, ki pripadajo štartni črti, so označena s S; polja, ki pripadajo kontrolnim območjem, so označena z velikimi črkami angleške abecede: A za prvo kontrolno območje, B za drugo in tako naprej. Ostala prevozna polja so predstavljena z znakom o. Kontrolnih območij je največ 16.

Primer: če bi uporabili dirkališče iz zgornje slike kot šesti testni primer, bi bilo lahko predstavljeno z naslednjo vhodno datoteko:

Avtomobili
6
40 26
........................................
........................................
ooooooooooooooooAAAAAS.............ooooo
ooooooooooooooooAAAAAS.....ooooooooooooo
ooooooooooooooooAAAAASoooooooooooooooooo
ooo.................oooooooooooo.....ooo
ooo.................ooooooo..........ooo
ooo..................................ooo
ooo..................................ooo
ooo..................................ooo
ooo..................................ooo
ooo..................................DDD
ooo..................................ooo
ooo..................................ooo
ooo..................................ooo
ooo..................................ooo
ooo.............ooooooo..............ooo
ooo.............ooooooo..............ooo
ooo.............ooooooo..............ooo
ooo.............ooo.ooo..............ooo
ooo.............ooo.ooo..............ooo
ooo.............ooo.ooo..............ooo
oooooooBBBooooooooo.oooooooooooCCCoooooo
oooooooBBBooooooooo.oooooooooooCCCoooooo
oooooooBBBooooooooo.oooooooooooCCCoooooo
........................................

Oblika izhodne datoteke

V prvi vrstici naj bo koda, ki si jo dobil(a) ob registraciji in iz katere je razvidno, da si rešitev res poslal(a) ti, ne pa kdo drug. V drugi vrstici naj bo ime naloge (Avtomobili). V tretji vrstici naj bo številka testnega primera, na katerega se ta izhodna datoteka nanaša. V četrti vrstici naj bo število točk, ki jih tvoja pot obišče. Če je to recimo k + 1, naj potem sledi še k + 1 vrstic, ki po vrsti navajajo koordinate obiskanih točk: najprej x0 in y0, v naslednji vrstici x1 in y1 in tako naprej, vse do zadnje vrstice, v kateri naj bosta koordinati xk in yk.

Primer: če bi bila naša uporabniška koda enaka 123456 in bi bil šesti testni primer takšen, kot je prikazan zgoraj, bi lahko pri njem oddali spodnjo izhodno datoteko.

123456
Avtomobili
6
32
21 2
20 2
18 2
15 2
11 2
7 3
4 4
2 6
1 9
0 13
0 17
1 20
3 22
5 23
8 23
12 22
17 22
23 22
28 23
32 23
35 22
37 20
38 17
38 14
38 11
38 8
37 6
35 4
32 3
28 3
23 4
17 4

Ta izhodna datoteka opisuje naslednjo pot (ki ustreza vsem zahtevam naloge, dolga pa je 31 korakov in je pri tem dirkališču to tudi najkrajša možna pot):

Testni primeri

Pripravili smo več testnih primerov z različno velikimi dirkališči in različnim številom kontrolnih območij.

Registracija

Preden lahko oddajaš svoje rešitve, se prijavi prek spodnjega obrazca. Dodelili ti bomo enolično uporabniško kodo, ki jo boš potreboval(a) za pripravo svojih izhodnih datotek.

Opomba: pri tej nalogi lahko sodeluje kdorkoli, ne glede na starost, izobrazbo, itd. Objavili bomo rezultate vseh tekmovalcev, za morebitne praktične nagrade pa pridejo v poštev le tisti tekmovalci oz. tekmovalke, ki v letu 2006/07 obiskujejo kakšno srednjo šolo.

Ime in priimek: *
e-mail: *
Šola:
Letnik:
Mentor:
 

Obrazec za oddajo rešitev

(Oddaja rešitev je možna do vključno 30. marca 2007.)

Datoteka s tvojo rešitvijo:

[Nazaj na glavno stran. | Na vrh te strani. | Imate vprašanje ali komentar?]