DRŽAVNO NATJECANJE 2015. – Drugi dan natjecanja / Srednja škola, I. podskupina (1. i 2. razred) - 3. zadatak

Flota od N svemirskih brodova označenih prirodnim brojevima od 1 do N luta galaksijom u potrazi za novim otkrićima. Svaki brod K ima fiksan komunikacijski kanal Xk -- nenegativni cijeli broj manji od 2^30.

Vrijeme potrebno da jedan brod pošalje poruku drugome ovisi o njihovim komunikacijskim kanalima. Ako je kanal prvog broda X a drugog Y onda se vrijeme slanja poruke računa tako da se:

• X i Y prebace u binarni sustav.
• Izračuna se binarni broj Z kojemu je K-ta binarna znamenka s desna jednaka 1 ako i samo ako su K-te binarne znamenke s desna brojeva X i Y različite.
• Vrijednost broja Z je traženo vrijeme slanja poruke.

Drugim riječima, vrijeme slanja poruke od broda A do broda B je takozvani bitwise XOR komunikacijskih kanala X i Y te se može izračunati pomoću izraza X^Y u C-u, C++-u, i Python-u, odnosno X xor Y u Pascal-u.

Ako je na primjer X = 12 (binarno 1100) , a Y = 9 (binarno 1001) onda je vrijeme slanja poruke 5 (binarno 101).

Podzadatak A: Svaki svemirski brod želi odrediti njemu najbliži svemirski brod (tj. onaj do kojeg je vrijeme slanja poruke najmanje) kako bi ga mogao pozvati u slučaju opasnosti.

Napiši program koji će za svaki svemirski brod A odrediti jedan njemu najbliži brod. Ukoliko za neki A postoji više najbližih brodova potrebno je ispisati bilo koji od njih.

Podzadatak B: Svemirski brod broj 1 želi poslati poruku svim drugim brodovima u floti.

To se odvija kroz N korak, a u svakom koraku jedan brod koji već ima poruku šalje je nekom brodu koji je još nije dobio.

Ukupno vrijeme postupka je suma vremena slanja svih pojedinih poruka.

Vaš program treba odrediti najmanje moguće ukupno vrijeme potrebno da poruku dobiju svi brodovi u floti.

Ulazni podaci

U prvom redu nalazi se prirodni broj, N (2 ≤ N ≤ 100000) - broj svemirskih brodova.

U K-tom od sljedećih N redova nalazi se cijeli broj Xk ( ≤ Xk ≤ 2^30) - komunikacijski kanal svemirskog broda K.

Komunikacijski kanali bit će međusobno različiti.

Izlazni podaci

U prvi red potrebno je ispisati N prirodnih brojeva, gdje je K-ti redu broj oznaka najbližeg broda brodu K.

U drugi red potrebno je ispisati traženo najmanje moguće ukupno vrijeme.

Napomena: Preporučamo da koristite 64-bitni cjelobrojni tip podataka (int64 u Pascalu, long long u C/C++).

Primjeri test podataka

Ulaz

4
1
2
4
8

Izlaz

2 1 1 1
17

Ulaz

5
1
3
6
8
12

Izlaz

2 1 2 5 4
20

Ulaz

8
15
7
6
21
25
5
14
10

Izlaz

7 3 2 5 4 2 1 7
44