Условие:
A. Перестановка с условиями
ограничение по времени на тест1 s.
ограничение по памяти на тест256 MB
Найдите перестановку длины n
, в которой a
элементов больше обоих своих соседей и b
элементов меньше обоих своих соседей. Элементы, имеющие одного соседа, не принимаются в расчёт.
Перестановка — это последовательность длины n
целых чисел от 1
до n
, в которой все числа встречаются ровно по одному разу. Например, (1)
, (4,3,5,1,2)
, (3,2,1)
— перестановки, а (1,1)
, (4,3,1)
, (2,3,4)
— нет.
Входные данные
В первой строке содержится три целых числа n
, a
и b (3≤n≤105;0≤a,b≤106)
— длина перестановки, число элементов больше обоих своих соседей и число элементов меньше обоих своих соседей.
Выходные данные
В качестве ответа выведите «YES» (без кавычек), если существует перестановка, и «NO» в противном случае. Если перестановка существует, то выведите любую из подходящих перестановок во второй строке.
Слова «YES» и «NO» можно выводить в любом регистре, например, «YES», «Yes», «yEs», и так далее.
Входные данные
5 2 2
Выходные данные
No
Входные данные
7 1 0
Выходные данные
Yes
1 7 6 5 4 3 2
Входные данные
7 3 2
Выходные данные
Yes
1 3 2 5 4 7 6
Решение:
Для решения задачи о перестановке с условиями, давайте разберем, что нам нужно сделать шаг за шагом.
Шаг 1: Понимание условий
Мы должны создать перестановку длины
n, в которой:-
a элементов больше обоих своих соседей (пики)-
b элементов меньше обоих своих соседей (впадины)Элементы, которые имеют только одного соседа (первый и последний элементы), не учитываются.
Шаг 2: Определение ограничений
1. Общее количество пиков и впадин:
- Каждый пик требует двух соседей, и так же для впадины.
- Поэтому максимальное количество пиков и впадин в перестановке длины
n будет ограничено:- Максимум пиков =
(n - 1) // 2- Максимум впадин =
(n - 1) // 2- Это связано с тем, что для каждого пика или впадины необходимо, чтобы у него были соседи.
2. Проверка возможности:
- Если
a + b n - 2, то это невозможно, так как у нас не хватает мест для размещения всех пиков и впадин.Шаг 3: Проверка условий
Теперь мы можем проверить, возможно ли создать такую перестановку:
Если условия выполнены, мы можем построить перестановку. Мы можем использовать следующий подход: 1. Начнем с последовательности от 1 до n. 2. Перемешаем элементы так, чтобы создать нужное количество пиков и впадин. Примерный алгоритм для построения: - Начнем с последовательности . - Для создания пиков и впадин будем менять местами элементы. Теперь реализуем это в коде: Теперь проверим на примерах, которые были даны в задаче: 1. Для входа - вывод будет . 2. Для входа - вывод будет и перестановка, например, . 3. Для входа - вывод будет и перестановка, например, . Таким образом, мы можем решить задачу, проверив условия и создав соответствующую перестановку.