Решение задачи "Соседние замены" с Codeforces

Без пояснения   Просмотров: 13


В подарок на день рождения Мишка получил массив целых чисел a длины n (какая неожиданность!).

Мишке не нравится этот подарок и он хочет как-нибудь его изменить. Он изобрел алгоритм и назвал его «Алгоритм Мишки для Соседних Замен». Этот алгоритм может быть представлен в виде последовательности ходов:

Заменить все вхождения 1 в массиве a на 2;
Заменить все вхождения 2 в массиве a на 1;
Заменить все вхождения 3 в массиве a на 4;
Заменить все вхождения 4 в массиве a на 3;
Заменить все вхождения 5 в массиве a на 6;
Заменить все вхождения 6 в массиве a на 5;

Заменить все вхождения 109−1 в массиве a на 109;
Заменить все вхождения 109 в массиве a на 109−1.
Заметим, что многоточие в середине алгоритма означает, что Мишка применяет эти замены к каждой паре соседних чисел (2i−1,2i) для всех i∈{1,2,…,5⋅108}, как это описано выше.

Например, для массива a=[1,2,4,5,10] следующая последовательность массивов описывает алгоритм:

[1,2,4,5,10] → (заменить все вхождения 1 на 2) → [2,2,4,5,10] → (заменить все вхождения 2 на 1) → [1,1,4,5,10] → (заменить все вхождения 3 на 4) → [1,1,4,5,10] → (заменить все вхождения 4 на 3) → [1,1,3,5,10] → (заменить все вхождения 5 на 6) → [1,1,3,6,10] → (заменить все вхождения 6 на 5) → [1,1,3,5,10] → … → [1,1,3,5,10] → (заменить все вхождения 10 на 9) → [1,1,3,5,9]. Дальнейшие шаги алгоритма не изменят массив.

Мишка очень ленивый и он не хочет сам применять эти изменения. Но ему очень интересно узнать, как будет выглядеть результат их применения. Помогите Мишке найти его.

Код

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, a;
	cin >> n;
	while(n--){
		cin>>a;
		if(a % 2 == 0)
            a--;
		cout << a << " ";
	}
	return 0;
}

         

Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться