Witam, czy ma ktoś pomysł na skrócenie pracy programu - Pastebin, ponieważ przy zgłaszaniu wyskakuje mi przekroczony limit czasu??Zadanie - http://pl.spoj.com/problems/AL_07_02/ Z góry dzięki.
0
1
Opis algorytmu:
- zamieniasz ciąg wiatrów na odpowiednie struktury: S = X/-1, N = X/1, E = Y/1, W = Y/-1
- przechodzisz przez tablicę struktur tak długo aż nie wyzerujesz odpowiednich delt lub nie skończy Ci się ciąg znaków
Złożoność gdzie n - ilość dni trwania konkursu.
Przykładowa implementacja (w innym języku, by nie było za prosto):
def race(start, finish, winds)
dx = finish.x - start.x
dy = finish.y - start.y
winds.each_with_index do |wind, index|
if dx != 0
dx += 1 if dx < 0 && wind == 'N'
dx -= 1 if dx > 0 && wind == 'S'
end
if dy != 0
dy += 1 if dy < 0 && wind == 'E'
dy -= 1 if dy > 0 && wind == 'W'
end
return index if dy == 0 && dx == 0
end
return nil
end
PS nie testowałem czy działa.