Školsko natjecanje 2020. godine za 3. i 4. razred Srednje Škole - 3. zadatak

Geohash je metoda koja zemljopisne koordinate pretvara u cijeli broj u svrhu učinkovitog pohranjivanja i upita u bazama podataka. U ovom zadatku promatramo zemljovid kao 2^n × 2^n kvadrat u standardnom koordinatnom sustavu gdje x koordinata raste udesno, a y koordinata raste prema gore. Ćelija je jedinični kvadrat poravnat s koordinatnim osima kojemu je donji-lijevi vrh točka s cjelobrojnim koordinatama (x, y) takva da je 0 ≤ x, y < 2^n.

Ukupno je 2^2n ćelija na zemljovidu 2^n × 2^n. Za neku ćeliju c, njezin geohash h(c) je 2n-bitni nenegativni cijeli broj konstruiran bit-po-bit počevši od najznačajnijeg bita, na način da je početni okvir jednak cijelom zemljovidu te se sljedeći koraci ponove n puta:

1. Podijelimo okvir na dva jednaka područja – lijevu i desnu polovinu. Ako je ćelija c u lijevoj polovini, sljedeći je bit 0, inače je sljedeći bit 1. Novi okvir je područje koje sadrži ćeliju c.

2. Okvir dijelimo na dva jednaka područja – donju i gornju polovinu. Ako je ćelija c u donjoj polovini, sljedeći bit je 0, inače je sljedeći bit 1. Novi okvir je područje koje sadrži ćeliju c.

   

Na slici prikazani su geohashevi (pretvoreni iz binarnog u dekadski zapis) svih ćelija na 8 × 8 zemljovidu (za n = 3) pri čemu se ishodište (0, 0) koordinatnog sustava nalazi u donjem-lijevom vrhu.

Na primjer, ćelija s koordinatama donjeg-lijevog vrha u (4, 2) ima geohash 36 = 100100₂ jer tu ćeliju sužavanjem okvira redom nalazimo u desnom području (1), pa donjem području (0), pa lijevom (0), pa gornjem (1), pa lijevom (0), pa donjem (0).

Napišite program koji za dvije ćelije zemljovida, zadane njihovim geohashevima, pronalazi put između njih kojemu je zbroj geohasheva posjećenih ćelija minimalan. Put je niz ćelija od kojih su svake dvije uzastopne susjedne u jednom od četiriju smjerova (sjever, jug, istok, zapad.)

ULAZNI PODACI

U prvom je retku prirodan broj n (1 ≤ n ≤ 8) koji definira dimenziju zemljovida 2^n × 2^n.

U drugom je retku cjelobrojni geohash h1 (0 ≤ h1 < 2^2n) koji odgovara polazišnoj ćeliji.

U trećem je retku cjelobrojni geohash h2 (0 ≤ h2 < 2^2n) koji odgovara odredišnoj ćeliji.

IZLAZNI PODACI

U prvi redak ispišite traženi minimalan zbroj geohasheva svih ćelija na traženom putu (uključujući polazišnu i odredišnu).

PRIMJERI TEST PODATAKA

ulaz

2
0
15

izlaz

45

ulaz

3
36
22

izlaz

134