  ̌      ̌   
P 50 (2022/2023) 224
Distanciranje, 1. del
N B̌́
Naloga, ki se je lotevamo tukaj, je poenostavlje-
na različica naloge Measures, ki se je pojavila na
srednjeevropski računalniški olimpijadi leta
2022. Ta je potekala med 24. in 30. julijem v Vara-
ždinu na Hrvaškem [1].
Na ravni dolgi cesti stoji n ljudi. Ker so razda-
lje med njimi relativno velike, lahko cesto predsta-
vimo s številsko premico, ljudi na njej pa s točkami.
Naj bodo x1, x2, . . . , xn koordinate točk, kjer ti ljudje
stojijo. Brez škode lahko predpostavimo, da velja
x1 ≤ x2 ≤ · · · ≤ xn. Velja tudi, da so x1, x2, . . . , xn
cela števila.
Zaradi smrtonosne pandemije je treba poskrbeti,
da razdalja med nobenima dvema osebama ne bo
manjša kot D, pri čemer je D neko predpisano celo
število, ki ga izbere ekspertna skupina. Vsi ljudje se
hkrati odpravijo na svoje nove položaje y1, y2, . . .,
yn, tako da bo veljalo |yi−yj| ≥ D za i ≠ j, tj., da bo
razdalja med vsakima dvema vsaj D. Pri tem želimo,
da bo razdalja, ki jo prehodi tisti človek, ki prehodi
najdaljšo pot, čim manjša. Razdalja, ki jo prehodi
i-ta oseba, je |xi − yi|. Drugače povedano, položaje
y1, y2, . . . , yn je treba izbrati tako, da bo vrednost
max
1≤i≤n
|xi −yi| (1)
čim manjša.
Oglejmo si preprost primer, kjer je n = 5, D = 3
ter
x1 = 1, x2 = 2, x3 = 4, x4 = 6 in x5 = 7.
Denimo, da prva oseba ostane na svojem mestu, tj.
y1 = x1 = 1. Pogoj, da bo razdalja med vsakima vsaj
D = 3, lahko dosežemo na primer z naslednjim iz-
borom končnih položajev:
y2 = 4, y3 = 7, y4 = 11 in y5 = 14.
Poglejmo, kolikšna je dolžina poti, ki jo morajo pre-
hoditi posamezne osebe:
|1− 1| = 0, |4− 2| = 2, |7− 4| = 3,
|11− 6| = 5 in |14− 7| = 7.
Najdaljšo pot je prehodil tisti, ki je bil v začetnem
položaju x5. Njegova pot je bila dolžine 7. To se-
veda ni najmanjša mogoča vrednost izraza (1). Mi-
nimum znaša namreč 3, ustrezne končne položaje
y1, y2, . . . , y5 pa za vajo poiščite sami. (V določenih
primerih lahko obstaja več različnih izborov vredno-
sti y1, . . . , yn, ki minimizirajo izraz (1).)
Program, ki reši nalogo, bomo napisali v program-
skem jeziku Python. Še preden pa se lotimo reše-
vanja, si naredimo funkcijo testni_primer(a, n),
ki bo naključno zgenerirala testni primer. Pri tem je
seveda n število oseb, argument a pa omeji možen
izbor števil x1, x2, . . . , xn, tako da bo veljalo |xi| ≤ a
za vse 1 ≤ i ≤ n. Ker imamo opravka z naključ-
nimi števili, bomo uporabili modul random, ki je del
standardne knjižnice jezika Python.
import random
def testni_primer(a, n):
return sorted([random.randint(-a, a)
for i in range(n)])
Ni se težko prepričati, da med optimalnimi reši-
tvami obstaja tudi takšna, kjer velja y1 ≤ y2 ≤ · · · ≤
yn. Denimo, da osebi, ki svojo pot začneta na xi in
xi+1, končata na yi in yi+1, kjer je yi > yi+1. To
pomeni, da se nekje na svoji poti srečata. Če bi se
dogovorili za izmenjavo svojih končnih položajev, se
pot nobeni od njiju zaradi tega ne bi podaljšala.
  ̌      ̌   
P 50 (2022/2023) 2 25
Označimo vrednost izraza (1) s T . Če ne vemo,
kako bi poiskali optimalni T∗ (tj. najmanjši možni
T , za katerega še obstajajo y1, y2, . . . , yn, da velja
|yi − yj| ≥ D za i ≠ j), si lahko zastavimo neko-
liko drugačno vprašanje: Ali obstaja razporeditev, ki
upošteva pravilo distanciranja, če predpišemo najve-
čjo dovoljeno razdaljo T , ki jo posamezna oseba sme
prehoditi?
Na to vprašanje pa ni tako težko odgovoriti. Se-
veda je lahko pri optimalni rešitvi veliko ljudi, pri
katerih je prehojena razdalja manjša od T . (Lahko
imamo tudi kakšno nepremično osebo, ki ostane na
svojem mestu.) Seveda pa iskana rešitev ne bo nič
slabša, če poleg tistega nesrečneža, ki »mora« pre-
hoditi razdaljo T , obstajajo še drugi ljudje, ki tudi
prehodijo pot največje dovoljene dolžine.
Začnimo pri osebi, ki stoji skrajno levo, tj. na po-
ložaju x1. Za y1 mora veljati x1 − T ≤ y1 ≤ x1 + T .
Nič ne bo narobe, če izberemo y1 = x1 − T , saj se
na tak način razdalja med y1 in y2 lahko samo po-
veča. Tistim, ki stojijo desno od prve osebe, slednja
pusti samo še več manevrskega prostora, če se spre-
hodi na položaj x1 − T in se tako še bolj oddalji od
preostanka skupine.
Podobno, za y2 mora veljati x2−T ≤ y2 ≤ x2+T .
Zaradi distanciranja pa mora hkrati veljati še y1 +
D ≤ y2. Ker želimo tistim, ki so desno od druge
osebe, pustiti kar se da veliko manevrskega prostora,
se bo druga oseba sprehodila čim dlje proti levi.
Hkrati pa moramo paziti, da se ne približa preveč
prvi osebi. Zato postavimo y2 = max{x2 − T ,y1 +
D}, da zadostimo obema pogojema. Če pa je druga
oseba že preblizu prve, se bo sprehodila na desno in
sicer ravno dovolj, da bosta na medsebojni razdalji
D. Pri tem se nam lahko zgodi, da je y1+D > x2+T .
To pa pomeni, da se druga oseba nikakor ne more
dovolj oddaljiti od prve osebe. Takoj lahko zaklju-
čimo, da rešitev pri izbrani vrednosti T ne obstaja.
Za vse nadaljnje osebe lahko razmišljamo na po-
doben način. Ker velja y1 ≤ y2 ≤ · · · ≤ yi, je
dovolj, če pri izbiri yi+1 upoštevamo le yi (ne pa
tudi končnega položaja vseh predhodnih oseb). Če
je yi +D > xi+1 + T , rešitev ne obstaja, sicer pa po-
stavimo yi+1 = max{xi+1 − T ,yi +D}.
Glede na zgornji razmislek lahko napišemo funk-
cijo preveri(x, D, T), ki kot prvi argument dobi
seznam x s položaji vseh oseb, kot drugi in tretji
argument pa vrednosti D in T iz naloge. Funkcija
preveri, ali sploh obstaja rešitev, kjer je prehojena
razdalja pri posamezni osebi kvečjemu T . Če reši-
tev ne obstaja, funkcija vrne None, sicer pa seznam
končnih položajev.
def preveri(x, D, T):
y = [None for i in range(len(x))]
y[0] = x[0] - T
for i in range(1, len(x)):
if y[i - 1] + D > x[i] + T:
return None
y[i] = max(x[i] - T, y[i - 1] + D)
return y
Zdaj lahko preverimo, ali obstaja rešitev za naš
prvi zgled, kjer je denimo T = 2 ali pa T = 5.
>>> zgled_1 = [1, 2, 4, 6, 7]
>>> preveri(zgled_1, 3, 2)
None
>>> preveri(zgled_1, 3, 5)
[-4, -1, 2, 5, 8]
Naj bo T∗ najmanjši možen T , za katerega obstaja
rešitev. Kako pa poiščemo T∗? Ni se težko prepri-
čati, da če rešitev ni mogoča za nek T , potem tudi
ni mogoča za nobeno manjšo vrednost, saj je dovo-
ljen premik posamezne osebe manjši, tako da imajo
na voljo še manj manevrskega prostora. Če rešitev
obstaja za neki T , potem lahko to isto rešitev upo-
rabimo za vse večje vrednosti parametra T . To pa
pomeni, da lahko T∗ poiščemo z binarnim iskanjem.
Če vemo, da je Ta ≤ T∗ ≤ Tb, za neka Ta in Tb, lahko
preverimo, ali obstaja rešitev za (Ta + Tb)/2. Če ob-
staja, potem je (Ta+Tb)/2 ≤ T∗ ≤ Tb; sicer pa vemo,
da je Ta ≤ T∗ ≤ (Ta + Tb)/2. Postopek ponavljamo
toliko časa, dokler je razlika med Ta in Tb dovolj ve-
lika.
Potrebujemo še primerni začetni vrednosti za Ta
in Tb. Za T∗ velja 0 ≤ T∗ ≤ D(n− 1). V najboljšem
primeru ljudje na cesti že na samem začetku stojijo
dovolj daleč, zato se nikomur ni treba premikati (od
tod 0 ≤ T∗). V najslabšem primeru so vsi na istem
mestu, torej x1 = x2 = · · · = xn. V tem primeru se
lahko razporedijo takole: y1 = x1, y2 = x2+D, y3 =
x3 + 2D, . . . , yn = xn + (n− 1)D. Največjo razdaljo
prehodi najbolj desna oseba, in sicer (n − 1)D (od
tod T∗ ≤ D(n− 1)). Sami se prepričajte, da je to res
najbolj neugoden scenarij.
  ̌      ̌   
P 50 (2022/2023) 226
Zdaj lahko napišemo funkcijo distanciranje
(x, D), ki kot argumenta dobi seznam x s položaji
vseh oseb in vrednost D. Funkcija vrne iskano vred-
nost T∗.
def distanciranje(x, D):
T_a = 0
T_b = D * (len(x) - 1)
while T_b - T_a > 1e-12:
T_c = (T_a + T_b) / 2
if preveri(x, D, T_c):
T_b = T_c
else:
T_a = T_c
return T_b
Zdaj pa funkcijo preizkusimo še na našem zače-
tnem zgledu:
>>> zgled_1 = [1, 2, 4, 6, 7]
>>> distanciranje(zgled_1, 3)
3.0
Za vajo lahko funkcijo prilagodite tako, da bo po-
leg T∗ vrnila še ustrezen seznam vrednosti y1, y2,
. . ., yn. Preizkusite funkcijo še na kakšnem drugem
primeru; te si lahko enostavno naredite s pomočjo
funkcije testni_primer. V uvodnem odstavku smo
zahtevali, da so vrednost x1, . . . , xn in D cela šte-
vila. Naša rešitev te predpostavke nikjer ne uporabi
in še vedno pravilno deluje, tudi če zahtevo po ce-
loštevilskosti opustimo. Testni seznami, ki jih nare-
dimo s pomočjo funkcije testni_primer, pa vsebu-
jejo samo celo števila. Kaj pri tem opazite? Je rešitev
T∗ vedno celo število? Ali to ni nujno res?
Povejmo še nekaj besed o časovni zahtevnosti re-
šitve. Funkcija preveri ima zanko for, ki naredi
O(n) iteracij, vse operacije pa so elementarne, to-
rej je časovna zahtevnost te funkcije O(n). Funk-
cija distanciranje kliče funkcijo preveri v svoji
zanki while. Koliko klicev naredimo? Začetni inter-
val pri binarnem iskanju je [Ta, Tb] = [0,D(n − 1)].
Tega razpolavljamo toliko časa, dokler ne pridemo
do Tb−Ta < 10−12. Torej naredimo O(log2(nD)) ite-
racij. Časovna zahtevnost funkcije distanciranje
je zatorej O(n log2(nD)).
V drugem delu prispevka bomo rešitev še izbolj-
šali. Nato si bomo ogledali še nekoliko zahtevnejšo
različico naloge, pri kateri lahko na cesto dodamo še
dodatnih M oseb, po vsakem dodajanju pa moramo
izpisati T∗. Vso izvorno kodo iz pričujočega članka
lahko najdete na GitHub repozitoriju [2].
Literatura
[1] Central European Olympiad in Informatics
(CEOI 2022), Varaždin, Hrvaška, 24.–30. julij
2022, Naloge z rešitvami, dostopno na https:
//ceoi.hsin.hr/competition/, ogled 11. 10.
2022.
[2] N. Bašić, Distanciranje (GitHub), dosto-
pno na https://github.com/nbasic/
presek-distanciranje, ogled 11. 10. 2022.
×××
Križne vsote
Naloga reševalca je, da izpolni bele kvadratke s
števkami od 1 do 9 tako, da bo vsota števk v za-
porednih belih kvadratkih po vrsticah in po stolpcih
enaka številu, ki je zapisano v sivem kvadratku na
začetku vrstice (stolpca) nad (pod) diagonalo. Pri tem
morajo biti vse števke v posamezni vrstici (stolpcu)
različne.
14 11
16
14 8
6
6 20
12
4
10
16
22
7
×××