Srednješolsko tekmovanje ACM iz računalništva in informatike

Odvoz odpadkov

Podroben opis naloge

Neko podjetje za odvoz odpadkov ima več strank (ki so naročile odvoz odpadkov), več smetišč (kamor je mogoče odvažati odpadke) in več voznikov (vsak od teh ima svoj tovornjak za odvoz odpadkov). Znane so lokacije strank, smetišč in voznikov ter razdalje in čas vožnje med njimi.

Tvoja naloga je sestaviti razpored odvozov s čim manjšo skupno ceno. V ceno razporeda štejejo: skupna prevožena razdalja vseh voznikov; pribitek na morebitne neodpeljane odpadke; poleg tega pa ima vsak voznik in vsaka stranka svoj delovni čas in v ceno razporeda se šteje pribitek za morebitne vožnje zunaj tega delovnega časa.

Odpadki so shranjeni v sodih, ki so vsi enake velikosti. Za vsako stranko je znano, koliko sodov z odpadki ima. Za vsakega voznika je znana kapaciteta njegovega tovornjaka (koliko sodov lahko prepelje). Na vsakem smetišču je neomejeno veliko prostora, tako da se lahko načeloma odpadke poljubne stranke odpelje na poljubno smetišče (ali kombinacijo več smetišč). Nekateri odpadki lahko ostanejo tudi neodpeljani, vendar to poveča ceno tvojega razporeda (ki jo moraš minimizirati).

Pri tej nalogi se vse dogaja znotraj enega dneva, časi pa se merijo v minutah od polnoči (časi so zato cela števila od 0 do 1440).

Za vsakega voznika je znano, na kateri lokaciji se nahaja ob začetku dneva; tja se mora na koncu tudi vrniti, vmes pa lahko poljubno obiskuje stranke in smetišča (oz. sploh katere koli lokacije). Ko obišče stranko, lahko tam naloži 0 ali več sodov; ko obišče smetišče, lahko tam odloži 0 ali več sodov (največ toliko, kolikor jih ima trenutno naloženih). Voznik začne svoj dan s praznim tovornjakom (torej z 0 sodi), pri pobiranju sodov ne sme nikoli preseči kapacitete tovornjaka, na koncu (po vseh vožnjah) pa mora imeti spet prazen tovornjak. Nalaganje in odlaganje sodov se zgodi v trenutku (to pomeni, da če ob času t pride na neko lokacijo, jo lahko ob istem času t že tudi zapusti, ob tem pa pobere ali odloži nekaj sodov). Med vožnjami posameznega voznika so lahko časovne vrzeli (voznik stoji pri miru in čaka do časa naslednje vožnje). Dovoljeno je tudi, da več voznikov istočasno pobira sode pri isti stranki ali jih odlaga na istem smetišču.

Vsak voznik ima svoj delovni čas, namreč od 480 do 960 (torej od osmih zjutraj do štirih popoldne). Vozi lahko tudi zunaj delovnega časa, vendar to poveča ceno tvojega razporeda voženj: v ceno se prišteje določen znesek za vsako minuto od začetka prve vožnje tega voznika do začetka njegovega delovnega časa ter za vsako minuto od konca njegovega delovnega časa do konca njegove zadnje vožnje.

Podobno ima tudi vsaka stranka svoj delovni čas, in sicer ravno tako od 480 do 960. Odpadke se lahko pri njej pobira tudi zunaj delovnega časa, vendar se v ceno tvojega razporeda prišteje določen znesek za vsako minuto od trenutka prvega pobiranja pri tej stranki do začetka njenega delovnega časa ter za vsako minuto od konca njenega delovnega časa do zadnjega pobiranja pri tej stranki.

Ocenjevalni program

Lahko si preneseš izvorno kodo programa, s katerim bomo ocenjevali prejete rešitve: Rtk24Odvoz.cpp.

Na voljo je tudi prevedena različica ocenjevalnega programa (za Windows).

Oblika vhodne datoteke

V prvi vrstici vhodne datoteke je niz z imenom naloge (Odvoz). V drugi vrstici je številka testnega primera, na katerega se nanaša ta vhodna datoteka. V tretji vrstici so štiri cela števila: L (število lokacij), S (število strank), V (število voznikov) in C_km (cena prevoženega kilometra).

Sledi L vrstic, ki vsebujejo vsaka po L celih števil; j-to število v i-ti od teh L vrstic je t(i, j), to je čas vožnje (v minutah) od lokacije i do lokacije j.

Sledi L vrstic, ki vsebujejo vsaka po L celih števil; j-to število v i-ti od teh L vrstic je d(i, j), to je razdalja (v kilometrih) od lokacije i do lokacije j.

Časi in razdalje niso nujno simetrične; lahko torej velja t(i, j) ≠ t(j, i) in/ali d(i, j) ≠ d(j, i). Pač pa za vsak i velja t(i, i) = 0 in d(i, i) = 0. Vsi ostali časi in razdalje (torej med dvema različnima lokacijama) so večji od 0.

Sledi vrstica, v kateri je L števil; i-to od teh števil ima vrednost 1, če je na lokaciji i smetišče, sicer pa ima vrednost 0.

Sledi S vrstic, ki opisujejo stranke; i-ta od teh vrstic opisuje stranko i in vsebuje naslednja štiri cela števila:

LS_i (lokacija te stranke; število od 1 do L);
N_i (število sodov pri tej stranki);
CS_i (cena za vsak neodpeljan sod te stranke);
MS_i (cena za vsako minuto od prvega pobiranja pri tej stranki do začetka delovnega časa ter od konca delovnega časa do zadnjega pobiranja).

Lokacije strank so različne (iz i ≠ j sledi LS_i ≠ LS_j). Poleg tega na lokaciji nobene stranke ni smetišča.

Sledi V vrstic, ki opisujejo voznike; i-ta od teh vrstic opisuje voznika i in vsebuje naslednja tri cela števila:

LV_i (lokacija tega voznika; število od 1 do L);
K_i (kapaciteta — koliko sodov lahko hkrati pelje ta voznik);
MV_i (cena za vsako minuto od začetka prve vožnje tega voznika do začetka njegovega delovnega časa ter od konca delovnega časa do konca zadnje vožnje).

Primer vhoda: naslednji primer kaže, kakšna bi lahko bila vhodna datoteka za majhen testni primer št. 0 s petimi lokacijami: na lokacijah 1 in 2 sta stranki, na 3 je smetišče, na 4 in 5 pa sta voznika.

Odvoz
0
5 2 2 100
0 10 15 20 12
11 0 19 25 15
16 20 0 13 10
18 27 15 0 17
15 13 11 18 0
0 3 2 1 5
6 0 7 1 2
5 6 0 1 3
3 4 5 0 3
2 1 3 5 0
0 0 1 0 0
1 20 1000 10
2 15 1500 20
4 12 30
5 10 40

Tu je na primer cena prevoženega kilometra 100 enot; cena vsakega neodpeljanega soda je pri prvi stranki 1000 enot, pri drugi 1500 enot; cena za vsako minuto dela zunaj delovnega časa je pri pri prvem vozniku 30 enot, pri drugem 40 enot; in podobno.

Oblika izhodne datoteke

Oddaš lahko poljubno število izhodnih datotek s svojimi rešitvami. Pri tem vsaka izhodna datoteka vsebuje rešitve za enega ali več testnih primerov. Če za isti testni primer oddaš več rešitev, bomo pri ocenjevanju upoštevali najboljšo med njimi.

Oblika posamezne izhodne datoteke je naslednja:

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 (Odvoz). Sledijo naj tvoje rešitve za enega ali več testnih primerov.

Vsaka rešitev se začne s prazno vrstico. Sledi naj vrstica, ki vsebuje številko testnega primera (od 1 do T), na katerega se ta rešitev nanaša. V drugi vrstici naj bo celo število (recimo k), ki pove, iz koliko voženj je sestavljen tvoj razpored. Sledi naj k vrstic, ki opisujejo vožnje; i-ta od teh vrstic naj opisuje i-to vožnjo in naj vsebuje šest celih števil:

VV_i (številka voznika; od 1 do V);
LZ_i (lokacija začetka vožnje; od 1 do L);
LK_i (lokacija konca vožnje; od 1 do L);
TV_i (čas začetka vožnje; od 0 do 1440);
DZ_i (sprememba v številu sodov na začetku vožnje, lahko tudi 0);
DK_i (sprememba v številu sodov na koncu vožnje, lahko tudi 0).

Taka vrstica pove, da voznik VV_i ob času TV_i pobere ali odloži DZ_i sodov (če je DZ_i > 0, jih toliko pobere, če pa je DZ_i < 0, jih −DZ_i odloži) na lokaciji LZ_i in se nato odpelje do lokacije LK_i, kjer pobere ali odloži DK_i sodov (če je DK_i > 0, jih toliko pobere, če pa je DK_i < 0, jih −DK_i odloži). Na končno lokacijo LK_i bo prišel ob času TV_i + t(LZ_i, LK_i); če je ta čas večji od 1440, šteje to za napako (ker se morajo vse vožnje zgoditi znotraj enega dneva) in bo tvoja rešitev zavrnjena. Lokacija začetka in konca vožnje morata biti različni.

Vožnje lahko navedeš v poljubnem vrstnem redu — ni treba, da so urejene po vozniku, po času ali kakorkoli drugače. Vožnje posameznega voznika se med seboj seveda ne smejo prekrivati (po času); in če jih uredimo po času, se mora vsaka od njih začeti na isti lokaciji, kjer se je prejšnja končala. Poleg tega se mora najzgodnejša vožnja voznika i začeti na lokaciji LV_i, najkasnejša vožnja tega voznika pa se mora na tej lokaciji končati.

Voznik lahko pobira sode le pri strankah in jih odlaga le na smetiščih. Poleg tega seveda skupno število pobranih sodov pri stranki i ne sme preseči N_i; število sodov, ki jih prevaža voznik i, pa v nobenem trenutku ne sme preseči K_i.

Če voznik na lokaciji neke stranke, recimo i-te, čaka nekaj časa (torej če se njegova naslednja vožnja ne začne takoj ob času, ko se prejšnja neha), recimo od časa t₁ do t₂, in če opis voženj določa, da naj bi ob prihodu na to lokacijo in/ali ob odhodu z nje pobral pri tej stranki kak sod, bo ocenjevalni probram štel, da je bilo to pobiranje izvedeno med delovnim časom stranke, če ima interval [t₁, t₂] neprazen presek z intervalom [480, 960]. Z drugimi besedami, če voznik na primer pride k stranki pred začetkom njenega delovnega časa, vendar jo zapusti šele ob ali po začetku, si mislimo, da je pobral sode na začetku njenega delovnega časa in ne že ob svojem prihodu; podobno velja tudi ob koncu delovnega časa.

Primer izhoda: če bi bila naša uporabniška koda enaka 123456 in bi obstajal testni primer št. 0, kakršen je prikazan zgoraj, bi lahko oddali spodnjo izhodno datoteko.

123456
Odvoz

0
9
1 4 1 480 0 12
1 1 3 498 0 -12
1 3 4 513 0 0
2 5 1 470 0 8
2 1 2 485 0 2
2 2 3 495 0 -10
2 3 2 514 0 10
2 2 3 534 0 -10
2 3 5 553 0 0

To je veljavna rešitev. Prvi voznik pelje od svoje začetne lokacije do prve stranke, pobere nekaj sodov, jih odloži na smetišču in se vrne na začetno lokacijo. Drugi voznik se pelje od svoje začetne lokacije do prve stranke, naloži nekaj sodov, nadaljuje do druge stranke, kjer naloži še dva soda, odloži vse sode na smetišču, nato pa se vrne k drugi stranki po še nekaj sodov, odloži še njih na smetišču in se nato odpelje nazaj na svojo začetno lokacijo.

Ocenjevanje

Rešitve (pri posameznem testnem primeru) se razvrsti po ceni (manjša je boljša). Cena rešitve (razporeda voženj) je vsota naslednjih seštevancev:

(skupno število prevoženih kilometrov po vseh vožnjah) · C_km;
za vsako stranko i (od 1 do S):
- (število neodpeljanih sodov te stranke) ·CS_i;
- če je bil najzgodnejši sod te stranke odpeljan ob času t₁, najkasnejši pa ob času t₂, se ceni rešitve prišteje MS_i · (max(0, 480 − t₁) + max(0, t₂ − 960));
za vsakega voznika i (od 1 do V):
- če se je najzgodnejša vožnja tega voznika začela ob času t₁, najkasnejša pa se je končala ob času t₂, se ceni rešitve prišteje MV_i · (max(0, 480 − t₁) + max(0, t₂ − 960)).

Rešitev, ki ne ustreza zgoraj opisanim pravilom za obliko in vsebino izhodne datoteke, je neveljavna in se ne bo upoštevala.

Primer: oglejmo si izračun cene za primer izhoda, ki smo ga navedli zgoraj. Voznika odpeljeta vseh 20 sodov prve stranke in 12 sodov druge; tako ostanejo 3 neodpeljani sodi pri drugi stranki (kar k ceni rešitve prispeva 3 · 1500 = 4500 enot denarja). Prvi voznik je prevozil 3 + 2 + 1 = 6 kilometrov, drugi pa 2 + 3 + 7 + 6 + 7 + 3 = 28 kilometrov, kar k ceni rešitve prispeva (6 + 28) · 100 = 3400 enot. Poleg tega je drugi voznik začel delati 10 minut pred začetkom svojega delovnega časa, kar k ceni rešitve prispeva 10 · 40 = 400 enot. Skupaj je tako cena te rešitve 4500 + 3400 + 400 = 8300 enot.

Vhodni podatki

Vse vhodne datoteke skupaj: odvoz-inputs.zip.

odvoz01.in (50 lokacij, 10 strank, 10 voznikov)
odvoz02.in (100 lokacij, 10 strank, 50 voznikov)
odvoz03.in (100 lokacij, 50 strank, 10 voznikov, kratki časi vožnje)
odvoz04.in (200 lokacij, 50 strank, 50 voznikov)
odvoz05.in (80 lokacij, 30 strank, 30 voznikov, ni pribitka za vožnje zunaj delovnega časa: MS_i = MV_i = 0)
odvoz06.in (100 lokacij, 30 strank, 30 voznikov, kratki časi vožnje, visok pribitek za neodpeljane sode CS_i)

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 srednješolci/ke in študentje/ke.

Obrazec za oddajo rešitev

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

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

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