Školsko natjecanje 2020. godine za 1. i 2. razred Srednje Škole - 2. 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 dani geohash h(c) pronalazi koordinate odgovarajuće ćelije c.

ULAZNI PODACI

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

U sljedećem je retku cjelobrojni geohash h (0 ≤ h < 2^2n).

IZLAZNI PODACI

U prvi redak ispišite tražene koordinate x i y donjeg-lijevog vrha tražene ćelije, odvojene razmakom.

PRIMJERI TEST PODATAKA

ulaz

1
0

izlaz

0 0

ulaz

2
7

izlaz

1 3

ulaz

3
36

izlaz

4 2