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:

(x₀, y₀), (x₁, y₁), (x₂, y₂), …, (x_k, y_k).

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:

• Vsako od polj (x_t, y_t) je prevozno (za t = 0, 1, 2, …, k).

• Polje (x₀, y₀) leži na štartni črti.

• Definirajmo hitrost v času t takole:

  v_x(t) = x_t − x_t−1,      v_y(t) = y_t − y_t−1.

  (Pri t = 0 si mislimo v_x(t) = v_y(t) = 0.)

  Potem zahtevamo, da sta

  |v_x(t) − v_x(t−1)| in |v_y(t) − v_y(t−1)| iz množice { −1, 0, 1 }

  in to za vse t = 1, 2, . . . , k. Z drugimi besedami, hitrost se od enega koraka do naslednjega ne sme spremeniti za več kot za 1 v vsaki smeri.

• Pot mora obiskati vsa kontrolna območja v pravem vrstnem redu in se nato končati bodisi na štartni črti bodisi v prvem kontrolnem območju.

  Z drugimi besedami: ko enkrat obiščemo neko kontrolno območje i, od takrat naprej ne smemo več obiskati kontrolnih območij od 1 do i − 1. Ko zadnjič zapustimo zadnje kontrolno območje, se lahko od tam premaknemo le še na štartno črto ali pa na prvo kontrolno območje, nato pa se moramo ustaviti.

Posebej poudarimo, da nas pri preverjanju, ali pot ustreza gornjim zahtevam, zanimajo le točke (x_t, y_t), na katerih se začenja ali končuje posamezni korak. Na primer: točki (x_t−1, y_t−1) in (x_t, y_t) morata biti prevozni, ni pa nujno, da cela daljica od (x_t−1, y_t−1) do (x_t, y_t) leži na prevoznem delu mreže (dovoljeno je torej „sekanje ovinkov“). Podobno, če niti (x_t−1, y_t−1) niti (x_t, y_t) 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 (x_t−1, y_t−1) do (x_t, y_t) 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 x₀ in y₀, v naslednji vrstici x₁ in y₁ in tako naprej, vse do zadnje vrstice, v kateri naj bosta koordinati x_k in y_k.

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.

• avtomobili01.in (100 × 100; 3 kontrolna območja)
• avtomobili02.in (100 × 100; 3 kontrolna območja)
• avtomobili03.in (100 × 100; 12 kontrolnih območij)
• avtomobili04.in (200 × 200; 3 kontrolna območja)
• avtomobili05.in (200 × 200; 4 kontrolna območja)
• avtomobili06.in (200 × 200; 4 kontrolna območja)
• avtomobili07.in (100 × 100; 16 kontrolnih območij)
• avtomobili08.in (300 × 300; 16 kontrolnih območij)
• avtomobili09.in (300 × 300; 4 kontrolna območja)
• avtomobili10.in (1000 × 1000; 16 kontrolnih območij)
• Vsi testni primeri, zaZIPani v en arhiv
• Slike vseh dirkališč (za lažjo predstavo).

• Za sladokusce: še nekaj malo težjih dirkališč, ki pa se ne štejejo v skupni seštevek.

  • avtomobili11.in (200 × 200; 3 kontrolna območja)
  • avtomobili12.in (100 × 100; 3 kontrolna območja)
  • avtomobili13.in (200 × 200; 11 kontrolnih območij)
  • avtomobili14.in (63 × 63; 4 kontrolna območja)
  • avtomobili15.in (63 × 63; 5 kontrolnih območij)
  • avtomobili16.in (217 × 217; 3 kontrolna območja)
  • avtomobili17.in (93 × 93; 3 kontrolna območja)
  • avtomobili18.in (100 × 100; 6 kontrolnih območij)
  • avtomobili19.in (100 × 100; 3 kontrolna območja)
  • avtomobili20.in (300 × 300; 3 kontrolna območja)
  • avtomobili21.in (300 × 300; 11 kontrolnih območij)
  • avtomobili22.in (99 × 99; 4 kontrolna območja)
  • avtomobili23.in (199 × 199; 4 kontrolna območja)
  • avtomobili24.in (399 × 399; 4 kontrolna območja)
  • avtomobili25.in (999 × 999; 4 kontrolna območja)
  • avtomobili26.in (891 × 891; 16 kontrolnih območij)
  • avtomobili27.in (995 × 995; 16 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.

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?]