Вам даны три последовательности: \(a_1, a_2, \ldots, a_n\); \(b_1, b_2, \ldots, b_n\); \(c_1, c_2, \ldots, c_n\).
Для всех \(i\) выполняется \(a_i \neq b_i\), \(a_i \neq c_i\), \(b_i \neq c_i\).
Найдите последовательность \(p_1, p_2, \ldots, p_n\), которая удовлетворяет следующим условиям:
- \(p_i \in \{a_i, b_i, c_i\}\);
- \(p_i \neq p_{(i \mod n) + 1}\).
Другими словами, для всех позиций вы должны выбрать одно из трех возможных значений так, что никакие две соседние позиции не имеют одинаковое значение (мы рассматриваем позиции \(i,i+1\) как соседние для всех \(i<n\), и также позиции \(1\) и \(n\) являются соседними).
Можно доказать, что в данных ограничениях решение всегда существует. Вам не нужно ничего минимизировать/максимизировать, вам нужно просто найти любую подходящую последовательность.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел \(p_1, p_2, \ldots, p_n\) (\(p_i \in \{a_i, b_i, c_i\}\), \(p_i \neq p_{i \mod n + 1}\)).
Если есть несколько возможных решений, выведите любое.
Примечание
В первом наборе входных данных \(p = [1, 2, 3]\).
Это правильный ответ, потому что:
- \(p_1 = 1 = a_1\), \(p_2 = 2 = b_2\), \(p_3 = 3 = c_3\);
- \(p_1 \neq p_2 \), \(p_2 \neq p_3 \), \(p_3 \neq p_1\).
Все возможные правильные ответы на этот набор входных данных: \([1, 2, 3]\), \([1, 3, 2]\), \([2, 1, 3]\), \([2, 3, 1]\), \([3, 1, 2]\), \([3, 2, 1]\).
Во втором наборе входных данных \(p = [1, 2, 1, 2]\).
В этой последовательности \(p_1 = a_1\), \(p_2 = a_2\), \(p_3 = a_3\), \(p_4 = a_4\). Также можно заметить, что никакие два соседние элемента этой последовательности не равны.
В третьем наборе входных данных \(p = [1, 3, 4, 3, 2, 4, 2]\).
В этой последовательности \(p_1 = a_1\), \(p_2 = a_2\), \(p_3 = b_3\), \(p_4 = b_4\), \(p_5 = b_5\), \(p_6 = c_6\), \(p_7 = c_7\). Также можно заметить, что никакие два соседние элемента этой последовательности не равны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 1 1
2 2 2
3 3 3
4
1 2 1 2
2 1 2 1
3 4 3 4
7
1 3 3 1 1 1 1
2 4 4 3 2 2 4
4 2 2 2 4 4 2
3
1 2 1
2 3 3
3 1 2
10
1 1 1 2 2 2 3 3 3 1
2 2 2 3 3 3 1 1 1 2
3 3 3 1 1 1 2 2 2 3
|
1 2 3
1 2 1 2
1 3 4 3 2 4 2
1 3 2
1 2 3 1 2 3 1 2 3 2
|