Как решить задачу о возвращении в исходную точку?

Question

[Dmitr66]

Здравствуйте! Помогите решить задачу. Даже не знаю, с чего зайти. Если есть какие-то мысли - буду очень благодарен.
Не прошу решение, прошу какие-нибудь подсказки/намеки

Метеозонд отправляет данные с его смещениями по X и Y за последние N минут ( N ≥ 1 ). За минуту зонд может сместиться на +/-1 по каждой координате или остаться на месте.
Аппаратура зонда сломалась и отправляет все значения координат без знаков (’+’ или ’-’). Проверьте существование комбинации знаков, для которых зонд вернулся на свое начальное положение.
На вход данные передаются как массив из N смещений. Каждое смещение имеет формат:

[diff_X, diff_Y]
Ваша функция должна вернуть модифицированный массив смещений со знаками, для которых зонд вернулся в начальное положение, или null, если такой комбинации не существует.

Формат ввода
[
[1, 0],
[0, 1],
[1, 1]
]
Формат вывода
[
[-1, 0],
[0, -1],
[1, 1]
]

Comments

[Robur]

сильно зависит от ограничений на N

[RAX7]

Для того чтобы вернуться в исходную позицию сумма смещений по X и Y должна быть равно 0. Если количество единиц четное, то половина из них со знаком +, половина -. Если нечетное, то зонд не вернется в исходную позицию.

Answer 1

[Rsa97]

Возможность возвращения: sum(diff_X) % 2 == 0 && sum(diff_Y) % 2 == 0
Для комбинации перед единицами расставить соответственно sum(diff_X) / 2 и sum(diff_Y) / 2 плюсов и такое же количество минусов. В каком именно порядке - неважно.

Comments

[yui yui]

подскажите, пожалуйста, почему это код неправильный ?
if (X % 2 == 0 && Y % 2 == 0) {
for(let i = 0; i < diffs.length/2; i++) {
if (diffs[i][0] != 0) diffs[i][0] = -diffs[i][0]
if (diffs[i][1] != 0) diffs[i][1] = -diffs[i][1]
}

[Rsa97]

yui yui, Потому что нулевые значения у вас тоже в общее количество цикла попадают.

[yui yui]

Rsa97, Напишите, пожалуйста, как код будет выглядит ?

[Rsa97]

yui yui, Например, так:

let sign = 0;
for (let i = 0; sign < X/2; i++) {
  if (diffs[i][0] == 1) {
    diffs[i][0] = -1;
    sign++;
  }
}
sign = 0;
for (let i = 0; sign < Y/2; i++) {
  if (diffs[i][1] == 1) {
    diffs[i][1] = -1;
    sign++;
  }
}

[Chpokman312]

yui yui, чему равны переменные X и Y?

Answer 2

[Сергей Соколов]

Отдельно смотреть наборы чисел по осям.
В одной оси задача расставить знаки так, чтобы сумма получилась нулевая.
В примере по x: [1, 0, 1]
Далее в общем виде – NP-полная задача об упаковке.
В частном, если там только единицы и нули, проще: четное число единиц – есть решение (половине дать минусы).

Answer 3

[Иван Клименко]

На самом деле вся задача заключается в том, что нужно найти, возможно ли из набор значений разбить на два набора, суммы элементов в которых будут равны. Решаете эту задачу отдельно для смещений по X и отдельно для смещений по Y. Если оба раза есть такие разбиения, то возвращаете ответ, в котором минусы будут расставлены у значений из какого-то одного разбиения.