1 Тема від bogdandacik

  • bogdandacik
  • Користувач
  • Поза форумом
  • Дата реєстрації: 23.11.2018
  • Повідомлень: 27
    • Репутація: 1

Тема: Змійка

Допоможіть оптимізувати. Ось умова задачі:
   Петрик із слоненятком грають  компютерну гру "Змійка". Гра проходить на нескінченній площині і полягає в наступному:спочатку задано координати x, y голови змійки. Гра триває N ходів: на кожному ході обирають напрямок у якому буде рухатись голова змійки далі. Хвіст і тіло змійки залишаються нерухомими, тобто після кожного коректного ходу голова змійки зростає на 1. Гра закінчується успішно якщо буде виконано всі N ходів і голова змійки жодного разу не зіткнеться з тілом змійки.
  Для вибраних Петриком початкових координат x, y і послідовності ходів, обраних Слоненятком вам слід відповісти чи успішно закінчиться гра. У випадку якщо гра закінчиться неуспішно, виведіть номер ходу коли голова змійки зіткнеться з тілом.
  Вхідні дані:
   У першому рядку задано початкові координати x, y змійки. У другому рядку задано стрічк S, що визначає послідовність ходів. Стрічка S складається тільки із символів 'L', 'R', 'U', 'D'. Якщо голова змійки знаходиться в точці з координатами (x, y), то у випадку команди 'L' вона перейде у точку
(x-1, y),  'R'  в точку (x+1, y), 'U' в точку (x, y+1), 'D' в точку (x, y-1) .
  Вихідні дані:
   Виведіть 'Success' (без лапок) якщо гра закінчиться успішно. Інакше в першому рядку виведіть 'Fail' , в другому рядку виведіть номер ходу після якого відбудеться перше зіткнення голови змійки з тілом. Ходи нумеруються починаючи з одиниці.
   Обмеження:
1<=x,y<=100000
1<=S<=1000000
    Приклади:
Вхідні дані:                                      Вихідні дані:
1 2                                                  Fail
RRRUULLDRRD                                    10

    Код який я написав проходить 16 тестів. Розумію, що він примітивний дайте якусь нову ідею розвязку.

var
  a: mas; s: string; x, y, len, k: longint; peretin: boolean;

begin
  readln(x, y);
  read(s);
  x:=5000; y:=5000;
  a[x, y] := 1;
  len := length(s);
  k := 1;
  peretin := false;
  while (k <= len) and (peretin = false) do 
  begin
    if s[k] = 'L' then x := x - 1;
    if s[k] = 'R' then x := x + 1;
    if s[k] = 'U' then y := y + 1;
    if s[k] = 'D' then y := y - 1;
    if a[x, y] = 0 then begin a[x, y] := 1; k := k + 1 end else peretin := true; 
  end; 
  if peretin = true then begin writeln('Fail'); write(k) end else write('Success');
end.

2 Відповідь від koala Востаннє редагувалося koala (11.04.2019 12:24:43)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Змійка

1. Ваш код не компілюється.
2.  

 readln(x, y);
  x:=5000; y:=5000;

Що ви тут хочете зробити?
3.

bogdandacik написав:

Код який я написав проходить 16 тестів.

Це всі тести чи ні? Якщо ні - скільки усього? З яким повідомленням не проходить?
4.

bogdandacik написав:

Допоможіть оптимізувати

"Оптимізувати" означає, що код працює, як вам треба, але не вписується в певні обмеження (час, об'єм пам'яті). Уточніть, що саме вам треба.

5. З вашим підходом потрібне поле 1000000 x 1000000 (добре, половина такого поля) - бо можливо задати стрічку "LL...L" чи "UU...U" (по 1000000 символів); тобто знадобиться терабайт пам'яті. Навіть якщо використовувати по 1 біту на комірку, то все одно це 128ГБ. Але ж шлях не буде довшим за мільйон елементів. Тобто вам треба зберегти мільйон пар (x,y) і якщо буде повтор - припинити. Зберігати унікальний набір елементів найкраще в set-і. Мільйон по, скажімо, 16 байт (по 4 байти на x та y та 8 на внутрішні структури) - це 16МБ.

koala вебсайт

3 Відповідь від bogdandacik

  • bogdandacik
  • Користувач
  • Поза форумом
  • Дата реєстрації: 23.11.2018
  • Повідомлень: 27
    • Репутація: 1

Re: Змійка

Всього тестів 25. Проходить 16. Про неохідність застосовувати великий обєм памяті думав. Ви пропонуєте заносити координати кожної точки в множину і на кожному етапі перевіряти чи такої вже не було?

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Змійка

Саме так.

koala вебсайт

5 Відповідь від bogdandacik

  • bogdandacik
  • Користувач
  • Поза форумом
  • Дата реєстрації: 23.11.2018
  • Повідомлень: 27
    • Репутація: 1

Re: Змійка

Пане Koala, але у множину можна занести до 255 значень, а як мені туди заности міліони значень? Як заносити координати точок?

6 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Змійка

А, точно, вже забув. Дурнувате обмеження.
Тоді доведеться власний аналог писати. Найпростіше, що можу запропонувати - зберігати множину у відсортованому масиві, пошук за O(log(N)), додавання - за O(N). Якщо не буде надто швидко - дерево чи хеш. Зберігати можна як int64 за формулою на кшталт (2^32)*x+y.

koala вебсайт

7 Відповідь від bogdandacik

  • bogdandacik
  • Користувач
  • Поза форумом
  • Дата реєстрації: 23.11.2018
  • Повідомлень: 27
    • Репутація: 1

Re: Змійка

Як я розумію потрібно створити два масиви координат X і координат Y, а потім шукати перше співпадання. Як здійснювати пошук?

8 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Змійка

Я ж кажу - краще один масив за формулою на кшталт x*1000000+y (можна трохи швидше, якщо степінь 2 використовувати).

koala вебсайт

9 Відповідь від bogdandacik

  • bogdandacik
  • Користувач
  • Поза форумом
  • Дата реєстрації: 23.11.2018
  • Повідомлень: 27
    • Репутація: 1

Re: Змійка

Зрозуміло дякую, а як швидко знайти перші два однакові числа у сформованому масиві?

10 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Змійка

Бінарним пошуком чи геш-таблицями, раджу перше.

koala вебсайт

11 Відповідь від bogdandacik

  • bogdandacik
  • Користувач
  • Поза форумом
  • Дата реєстрації: 23.11.2018
  • Повідомлень: 27
    • Репутація: 1

Re: Змійка

Дякую за допомогогу пане Koala. Пішли всі тести. Ось код.

type
  mas = array[1..1000000] of int64;

var
  A, index, per: mas; x, y, i, j, k, nomer, min1, min2, kord: int64; s: string;

procedure SortA(left, right: int64);
var
  i, j, x, w, l: int64;
begin
  I := left;
  J := right;
  x := A[(left + right) div 2];
  repeat
    while A[i] > x do i := i + 1;
    while x > A[j] do j := j - 1;
    if i <= j then begin
      W := A[i];
      A[i] := A[j];
      A[j] := W;
      W := index[i];
      index[i] := index[j];
      index[j] := W;
      I := i + 1;
      J := j - 1;
    end;
  until i > j;
  if left < j then SortA(left, j);
  if i < right then SortA(i, right);
end;

begin
  readln(x, y);
  read(s);
  kord := x * 1000000 + y;
  A[1] := kord;
  k := 1;
  while (k <= length(s)) do 
  begin
    if s[k] = 'L' then x := x - 1;
    if s[k] = 'R' then x := x + 1;
    if s[k] = 'U' then y := y + 1;
    if s[k] = 'D' then y := y - 1;
    k := k + 1;
    kord := x * 1000000 + y;
    A[k] := kord;
  end;
  for i := 1 to k do
    index[i] := i;
  sortA(1, k);
  j := 0; 
  i := 0; 
  while j < k do 
  begin
    min1 := 0;
    min2 := 0;
    j := j + 1;
    if (A[j] = A[j + 1]) and (index[j] > index[j + 1]) then begin
      min2 := index[j];
      min1 := index[j + 1];
      j := j + 1;
    end;
    if (A[j] = A[j + 1]) and (index[j] < index[j + 1]) then begin
      min2 := index[j + 1];
      min1 := index[j];
      j := j + 1;
    end;
    while (A[j] = A[j + 1]) do 
    begin
      if (index[j + 1] < min2) and (index[j + 1] > min1) then min2 := index[j + 1];
      if (index[j + 1] < min1) then begin min2 := min1; min1 := index[j + 1] end;
      j := j + 1;
    end;
    if min2 > 0 then begin i := i + 1; per[i] := min2 - 1 end;
  end;
  
  if i > 0 then begin
    nomer := per[1];
    for j := 2 to i do 
      if per[j] < nomer then nomer := per[j];
  end;
  if nomer > 0 then begin writeln('Fail'); write(nomer) end else write('Success');
end.