@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]
]
  • Вопрос задан
  • 474 просмотра
Решения вопроса 3
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Возможность возвращения: sum(diff_X) % 2 == 0 && sum(diff_Y) % 2 == 0
Для комбинации перед единицами расставить соответственно sum(diff_X) / 2 и sum(diff_Y) / 2 плюсов и такое же количество минусов. В каком именно порядке - неважно.
Ответ написан
sergiks
@sergiks Куратор тега JavaScript
♬♬
Отдельно смотреть наборы чисел по осям.
В одной оси задача расставить знаки так, чтобы сумма получилась нулевая.
В примере по x: [1, 0, 1]
Далее в общем виде – NP-полная задача об упаковке.
В частном, если там только единицы и нули, проще: четное число единиц – есть решение (половине дать минусы).
Ответ написан
На самом деле вся задача заключается в том, что нужно найти, возможно ли из набор значений разбить на два набора, суммы элементов в которых будут равны. Решаете эту задачу отдельно для смещений по X и отдельно для смещений по Y. Если оба раза есть такие разбиения, то возвращаете ответ, в котором минусы будут расставлены у значений из какого-то одного разбиения.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы