@prosto_paren
react intern developer

Где у меня ошибка?

При решении этой задачи платформа выдает ошибку Превышено ограничение по памяти хотя проверил через локальный сервер и утечки памяти не было.
Ограничения:
Ограничение по времени: 1 сек
Ограничение по памяти: 256 Мб
Задача:
Текстовый редактор поддерживает следующие команды:
<число> H – сдвинуть курсор на указанное число позиций влево.
<число> L – сдвинуть курсор на указанное число позиций вправо.
<число> I <буква> – вставить указанную букву указанное число раз перед позицией курсора и после этого переместить курсор на одну позицию влево так, чтобы он указывал на самую правую вставленную букву.

Например, после команд 3 I a, 1 I b получится текст aaba, и курсор будет указывать на букву b. После команд 3 I a, 2 H, 1 I b, 3 L получится текст baaa, и курсор будет указывать на последнюю букву.
Команды H и L никогда не выводят курсор за пределы текста. Например, после команд 3 I a, 10 L курсор остановится на последней букве. А после команд 3 I a, 10 H курсор остановится на первой букве.
Напишите программу, которая по данному списку команд и по данному списку позиций выводит буквы, находящиеся на соответствующих позициях в результирующем тексте.
Формат входных данных
Первая строка содержит два натуральных числа N и M (N, M ≤ 1000). Далее следуют N строк, каждая из которых содержит одну команду. После этого следуют M строк, каждая из которых содержит одно натуральное число – позицию в результирующем тексте. Позиции нумеруются начиная с единицы и не превышают длины текста. Гарантируется, что все числа в командах будут в интервале [1…1000000000] и что длина текста не превысит 1000000000.
Формат выходных данных
Выведите M строк. Каждая строка должна содержать одну букву.
spoiler
5f508a246a796534615141.png

как я решил:
// массив arr - это входные данные заключенный в массив

let [n,m] = arr[0].split(' ')
let result;
let cursorPosition = 0;
let flag;

const putSubstrInStr=(str, substr, idx)=> {
  let temp = str.split("");
  temp.splice(idx, 0, substr);
  return temp.join("");
}

for(let i=1;i<arr.length;i++){
    if(n>0){
      n--
       let strings = arr[i].trim().split(" ");
  switch (strings[1]) {
    case "I":
      let word = "";
      let count = strings[0];
      while (true) {
        word += strings[2];
        count--;
        if (count === 0) break;
      }
      if (!result) {  
        result = word;
        cursorPosition = parseInt(strings[0]);
      } else {
        result = putSubstrInStr(
          result,
          word,
          cursorPosition-1
        );
          cursorPosition =
         cursorPosition + parseInt(strings[0])-1
      }
      break;
    case "H":
       cursorPosition = cursorPosition - strings[0] <= 0
        ? cursorPosition = 1
        : cursorPosition - parseInt(strings[0]);
      break;
    case "L":
        cursorPosition = cursorPosition + parseInt(strings[0]) 
        >= result.length
        ? cursorPosition = result.length
        : cursorPosition + parseInt(strings[0]);
      break;
    default:
      break;
  }
    }
    else if(n==0 &&m>0){
       m--
      print(result[arr[i].trim()-1])
    }
}
  • Вопрос задан
  • 294 просмотра
Решения вопроса 1
Robur
@Robur
Знаю больше чем это необходимо
массив arr - это входные данные заключенный в массив


длина текста не превысит 1000000000


Ограничение по памяти: 256 Мб


В качестве дополнительного задания найдите взаимосвязь между этими тремя предложениями ;)
не говоря уже о том что вы потом с этим массивом делаете.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Проблема в том, что числа повторений в задаче ОЧЕНЬ большие.
Правильное решение должно не строить строку, а хранить ее в виде пар (символ, количество), как в RLE.
Самое быстрое решение - хранить список таких пар (или 2 списка). Но проще, и должно проходить по времени другое решение: Можно просто хранить массив этих пар (или 2 массива, один для символов, другой - для количества повторения).

Позиция курсора тут будет храниться двумя числами - в какой группе в массиве он сейчас и где он внутри группы. При перемещении сначала увеличьте или уменьшите позицию внутри группы. Если стало -1 или слишком большим, то переходите к следующей или предыдущей группе. Если таких нет, откатывайтесь на границу.

При вставке надо разбить текущую группу на 2 (если вы не на границе между группами) и добавить новую группу. Это вставка в центр массива двух элементов. Не знаю, как это на js реализуется, но точно можно. На худой конец, вставляете пустые элементы в конец массива и перемещаете нужные элементы на 1-2 позиции циклом с конца к началу. Но скорее всего, есть какая-то встроенная конструкция.

Есть оптимизация - если вставляемый символ такой же, как текущая группа (или предыдущая, если вы на границе), то просто прибавляйте новое количество к повторениям в группе.

В конце нужно для каждой позиции пройтись по массиву групп, пока не отсчитаете нужное количество символов. Если слишком медленно, то можно M чисел отсортировать и потом одним проходом по массиву групп с указателем в массиве запросов найти все ответы (если текущая позиция-запрос левее текущей группы, переходим к следующей позиции, если текущая позиция в текущей группе - мы нашли ответ).
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы