Rejs - skrócenie czasu programu

0

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.

1

Opis algorytmu:

  • \Delta_x = x_m - x_s
  • \Delta_y = y_m - y_s
  • 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ść O(n) 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.

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