Školska razina 2021 / Osnovna škola (8. razred) - 3. zadatak

U Snježogradu postoji samo jedna ulica u kojoj se nalazi N kuća s oznakama od 1 do N. Udaljenost između dviju kuća jednaka je apsolutnoj razlici njihovih kućnih brojeva. Na kućnom broju 1 smještena je agencija “Ab ovo” koja se bavi dostavom. U agenciji su zaposlena 2 studenta, Mirko i Slavko. Zaprimili su K narudžbi oblika (ai , bi ) koje nam govore da stanovnik koji živi na kućnom broju ai želi poslati paket stanovniku u kući s kućnim brojem bi .

Početna i završna adresa dostave će se, naravno, u svim narudžbama razlikovati. Mirko i Slavko žele organizirati dostavu na način da zbroj duljina njihovih prijeđenih puteva bude minimalan.

Mirko i Slavko će međusobno podijeliti narudžbe te odrediti kojim će redom svaki od njih obavljati svoj skup narudžbi. Obojica se na početku nalaze na kućnom broju jedan. Da bi dostavljač izvršio sve dostave koje planira, prvo mora doći do početne adrese narudžbe koju je odlučio prvu obaviti i dostaviti paket na njezino odredište pa se nakon toga pomaknuti na početnu adresu narudžbe koju će drugu obaviti, dostaviti paket na njezino odredište, itd.

Nakon odrađene zadnje isplanirane dostave, oba se dostavljača trebaju vratiti u agenciju. Primijetite da je moguće da u optimalnom rasporedu sve dostave obavlja samo jedan dostavljač.

Također, moguće je da izvrstan student Slavko taj dan ne dođe na posao jer mora učiti za ispit pa će sve dostave morati obaviti Mirko.

Ulazni podaci

U prvom je retku prirodan broj B (1 ≤ B ≤ 2). Ako Slavko taj dan nije došao na posao B će biti jednak 1, a inače će B biti jednak 2.

U drugom retku nalaze se prirodni brojevi N (3 ≤ N ≤ 100) i K (1 ≤ K ≤ 7), brojevi iz teksta zadatka.

U svakom od sljedećih K redaka su po dva različita prirodna broja ai i bi (2 ≤ ai i bi ≤ N), koji predstavljaju narudžbe koje je agencija zaprimila.

Izlazni podaci

Ako Slavko nije došao na posao ispišite minimalnu duljinu puta koju Mirko mora prijeći da bi dostavio sve pakete i vratio se u agenciju.

Ako je pak Slavko došao ispišite minimalnu ukupnu duljinu putova koju on i Mirko moraju prijeći da bi dostavili sve pakete i vratili se u agenciju

Primjeri test podataka

Ulaz

1
8 3
3 6
6 3
8 4

Izlaz

18

Objašnjenje

Slavko je morao učiti za ispit pa sve dostave obavlja Mirko. Optimalno mu je prvo obaviti prvu, pa treću, pa drugu narudžbu iz ulaza.

Na početku se nalazi na adresi s kućnim brojem 1. Da bi obavio prvu narudžbu mora doći na adresu 3, tamo uzeti paket i odnijeti ga do adrese 6, pa se pomaknuti do 8, uzeti paket i odnijeti do adrese 4. Nakon toga, da bi obavio drugu narudžbu iz ulaza odlazi do kuće 6 te nosi paket do kuće s oznakom 3.

Na kraju se mora vratiti u agenciju koja je na adresi 1. Za to mu treba ukupno 2+3+2+4+2+3+2=18 koraka.

Ulaz

2
10 5
2 9
10 6
7 10
2 3
9 5

Izlaz

28

Ulaz

2
10 4
2 3
10 2
9 2
6 8

Izlaz

32

Objašnjenje

Ovo je jedan od primjera gdje je zbroj udaljenosti koje su Mirko i Slavko prešli najmanji ako jedan od njih stoji na mjestu, a drugi obavi sve dostave. Tako na primjer Mirko može stajati na mjestu dok Slavko obavlja redom prvu, pa drugu, pa četvrtu i na kraju treću narudžbu iz ulaza.