ACM RTK - 1. skupina

Davek na ograjo

Slovenski državni urad za odkrivanje novih davkov je ugotovil, da ima vsak Slovenec svoje posestvo omejeno z ograjo in da za to še ni predpisanega nobenega davka. Zato so hitro naročili svojim matematikom, naj pripravijo informativni izračun.

Matematiki so seveda takoj brez škode za splošnost predpostavili, da je Slovenija pravokotna mreža w × h kvadratkov, kjer vsak kvadratek predstavlja en kvadraten kilometer, in da je vsa zemlja razdeljena med n lastnikov, pri čemer ima vsak kvadratek samo enega lastnika. Nato so oštevilčili vse lastnike zemlje s števili od 0 do n - 1, vsak kvadratni kilometer zemlje pa so označili s številko lastnika. Torej, kot na skici: polja, označena z 0, pripadajo lastniku 0; polja, označena z 1, pripadajo lastniku 1 in tako naprej.

Vsa posestva so popolnoma ograjena: ograje stojijo na vseh državnih mejah in povsod tam, kjer kvadratek enega lastnika meji na kvadratek drugega lastnika. Na zgornji sliki so ograje narisane z debelimi črtami.

Davek se zaračuna sorazmerno z dolžino ograje, ki obdaja posestva posameznega lastnika. Ker vsi lastniki trdijo, da ograja spada k njihovemu zemljišču in ne sosednjemu, se jo vsem lastnikom tudi zaračuna - večina ograj se tako šteje dvakrat. Napiši program, ki za vsakega lastnika izračuna in izpiše skupno dolžino ograj, od katerih bo moral plačati davek. Predpostavi, da že obstajajo naslednje funkcije, ki vračajo podatke o mreži:

• Visina() vrne h, torej višino mreže (celo število, vsaj 1 in največ 250);
• Sirina() vrne w, torej širino mreže (celo število, vsaj 1 in največ 250);
• StLastnikov() vrne n, torej število različnih lastnikov (največ w * h);
• Lastnik(x, y) vrne številko lastnika za celico (x, y); to je celo število od 0 do n-1. Pri tem je x številka stolpca (od 0 do w-1), y pa številka vrstice (od 0 do h-1).

Za primer z gornje slike bi moral tvoj program ugotoviti, da je za lastnika 0 skupna dolžina ograj enaka 8, za lastnika 1 je skupna dolžina 10, za lastnika 2 je skupna dolžina 12, za lastnika 3 je skupna dolžina 8, za lastnika 4 je skupna dolžina 20, za lastnika 5 je skupna dolžina 8, za lastnika 6 pa je skupna dolžina ograj enaka 18.