Rejs - skrócenie czasu programu

Odpowiedz Nowy wątek
2015-01-31 18:53
Kiwiior
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.

Pozostało 580 znaków

2015-01-31 19:05
Kiwiior
0

Kod - http://4programmers.net/Pastebin/3804

Pozostało 580 znaków

2015-01-31 21:06
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.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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