Решение задачи Особая перестановка с Codeforces

С пояснением   Просмотров: 154

Перестановкой длины n называется такой массив p=[p1,p2,…,pn], который содержит каждое число от 1 до n (включительно) и притом ровно по одному разу. Например, p=[3,1,4,2,5] — перестановка длины 5.

Для заданного числа n (n≥2) найдите такую перестановку p, в которой разница (то есть модуль разности) любых двух соседних элементов находится в диапазоне от 2 до 4, включительно. Формально, для перестановки p должно выполняться 2≤|pi−pi+1|≤4 для всех i (1≤i
Выведите любую такую перестановку для заданного значения n или определите, что ее не существует.

Код 

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n; cin >> n;
	if (n <= 3) {
		cout << -1 << "\n";
		return;
	}
	for (int i = n - (n % 2 == 0); i >= 1; i -= 2)
		cout << i << ' ';
	cout << "4 2 ";
	for (int i = 6; i <= n; i += 2)
		cout << i << ' ';
	cout << "\n";
}

int main() {
	int t; cin >> t;
	while (t--) solve();
}

         

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


Пояснение к задаче

Если n<4, то ответа не существует. Вы можете проверить все случаи руками, чтобы убедиться в этом. Иначе ответ всегда существует и существует очень простой способ его построить: сначала давайте добавим в ответ все нечетные числа в убывающем порядке, затем добавим 4, 2 и все остальные четные числа в возрастающем порядке. Для того, чтобы проверить, что это всегда работает, вы можете локально запустить в некотором роде чекер (вы можете проверить все 1000 тестов очень быстро, меньше, чем за секунду, и это иногда бывает очень полезно).



Комментарии

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


© 2020 HSECODES [email protected] Карта сайта