Pomysł na rozwiązanie zadania (dosyć trudne)

0

Witam tak mnie naszło.. ma ktos jakis pomysl jak by to rozwiazac?
http://logia.oeiizk.waw.pl/nowa/page.php?sr=logia11/2etap
chodzi mi o Zadanie 3 (PIONEK). To zadanie z konkursu 2 lata temu. Ktos ma jakis pomysl jak to sprawdzac?
Wymyslilem ze nalezy od kazdej cyfry isc w tyl i przod az sie wypadnie z indeksu i w miedzyczasie liczyc odleglosc i jak jest krotsza od zapisanej w jakiejs zmiennej lokalnej to ja nadpisac.. Ale moze macie lepszy?

0

Do tablicy wpisujesz T[i]=x[i]+y[i], gdzie x[i],y[i] współrzędne i-tej cyferki :c.
Sortujesz tablice T[i].
W jednym przebiegu znajdujesz wynik=min(T[i+1]-T[i]);
Koszt: O(log(n)) - z sortowania.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0