Задача №114811. Единственное решение
Владимир Геннадьевич готовит задание по высшей математике для студентов.
Задание планируется такое. Дано \(n\) целых чисел \(x_1, x_2, \ldots, x_n\) и натуральное число \(m\), \(1 \le m < 2^n\).
Требуется выбрать \(n\) целых чисел \(a_1, a_2, \ldots, a_n\), каждое из которых равно \(0\), \(-1\) или \(1\), при этом хотя бы одно из них должно быть отлично от \(0\), а сумма \(a_1x_1 + a_2x_2 + \ldots + a_nx_n\) должна делиться на \(m\) без остатка.
Владимир Геннадьевич придумал ответ на задание, которое он хочет дать студентам: он выбрал \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(-1 \leq a_i \leq 1\)), хотя бы одно из них не равно \(0\). Чтобы выполненные задания было легче проверить, он хочет придумать такие числа \(x_1, x_2, \ldots, x_n\) и натуральное число \(m\), чтобы выбранные им числа \(a_1, a_2, \ldots, a_n\) были единственным подходящим решением. К сожалению, это невозможно, так как числа \(-a_1, -a_2, \ldots, -a_n\) также подходят.
Тогда Владимир Геннадьевич ослабил свои требования: он хочет, чтобы других решений, кроме \(a_1, a_2, \ldots, a_n\) и \(-a_1, -a_2, \ldots, -a_n\) не существовало.
Помогите ему выбрать числа \(x_1, x_2, \ldots, x_n\) и \(m\) для задания.
В первой строке находится число \(n\) (\(1 \leq n \leq 30\)).
В следующей строке дано \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(-1 \leq a_i \leq 1\)). Гарантируется, что хотя бы одно из чисел \(a_i\) не равно \(0\).
В первой строке выведите натуральное число \(m\) (\(1 \leq m < 2^n\)).
В следующей строке выведите \(n\) целых чисел \(x_1, x_2, \ldots, x_n\) (\(-2^{30} < x_i < 2^{30}\)).
Если подходящих вариантов несколько, выведите любой из них.
Гарантируется, что решение всегда существует.
В примере студенты должны выбрать числа \(a_1\) и \(a_2\), чтобы число \(a_1 + 4a_2\) делилось на \(3\). Подходят два решения:
- \(a_1 = 1\), \(a_1 = -1\) (\(a_1 + 4a_2 = 1 - 4 = -3\), делится на \(3\)) и
- \(a_1 = -1\), \(a_2 = 1\) (\(a_1 + 4a_2 = -1 + 4 = 3\), делится на \(3\)).
2 1 -1
3 1 -2