У Алисы закончился очередной учебный год, и она составляет расписание на каникулы. Алиса…
- User
У Алисы закончился очередной учебный год, и она составляет расписание на каникулы. Алиса планирует, что в ее каникулы состоится некоторое число событий, таких как посещение концертов, празднование дней рождений и так далее. Алиса называет i-тый день каникул нескучным, если для него выполняется хотя бы одно из двух условий: в i-тый день состоится хотя бы одно событие; хотя бы одно событие состоится в день с номером i−1 и в день с номером i+1.
Рассмотрим пример. Пусть в каникулах 10 дней и некоторые события произойдут в дни с номерами 2,3,5,9,10. Тогда нескучными будут все эти дни, а также день с номером 4, поскольку некоторые события произойдут в два соседних с ним дня.
При составлении расписания Алиса учитывает, что для некоторых событий заранее известна дата, а для других она сама может подобрать подходящий день. Алиса хочет расставить события с открытой датой так, чтобы каникулы получились наиболее нескучными, то есть, чтобы количество нескучных дней в каникулах было максимальным.
Напишите программу, которая подберет дни для событий с открытой датой так, чтобы каникулы получились наиболее нескучными.
Формат входных данных На вход в первой строке через пробел подается три целых числа n, m и k — продолжительность каникул в днях, количество событий с открытой датой и количество событий с заданной датой соответственно;
1≤n≤100000; 1≤m≤100000; 0≤k≤100000.
Во второй строке через пробел записаны k натуральных чисел d1 ,d2, ⋯ ,dk — номера дней, в которые произойдут события с известной датой; 1≤di≤n. Числа могут повторяться и следовать в произвольном порядке. Если k будет равно нулю, то вторая строка будет пустой.
Формат выходных данных В первой строке выведите одно натуральное число s— количество нескучных дней в каникулах. Во второй строке через пробел выведите m натуральных чисел t1 ,⋯, tm — номера дней в которые Алиса должна запланировать события с открытой датой. Если допустимых ответов будет несколько, то можно вывести любой. Числа могут повторяться и следовать в произвольном порядке.
Методика проверки Программа проверяется на 30 тестах. Прохождение каждого теста оценивается в 1 балл. Тесты из условия задачи при проверке не используются. В трех первых тестах k=0. В следующих трех тестах k=1. В первых 15 тестах n, m и k не превосходят 100.
Sample Input 1: 11 5 6 1 3 5 7 9 11
Sample Output 1: 11 1 1 1 1 1
Sample Input 2: 11 2 0
Sample Output 2: 3 2 4
Sample Input 3: 15 2 5 1 2 8 12 14
Sample Output 3: 11 4 6
Пояснение к примерам В первом примере все дни каникул являются нескучными из-за событий с известной датой, поэтому пять событий с открытой датой можно расставить произвольно.
В ответе к второму примеру нескучными будут дни с номерами 2,3,4. Улучшить ответ нельзя.
В ответе к третьему примеру нескучными будут 11 дней с номерами 1,2,3,4,5,6,7,8,12,13,14. Улучшить этот ответ нельзя, хотя набор дней может быть другим, например, 4, 10 или 6, 10.
Напиши программу на python, чтобы она работала для каждого теста!
- Assistant
Одним из возможных решений этой задачи является следующий алгоритм:
-
Чтение входных данных: получение значения n (продолжительность каникул в днях), m (количество событий с открытой датой), k (количество событий с заданной датой) и номеров дней, в которые произойдут события с известной датой (если есть).
-
Создание списка нескучных дней: все дни каникул считаются изначально скучными. Если имеются события с известной датой, то отмечаем эти дни как нескучные.
-
Поиск и отметка дней, которые могут стать нескучными: проходим по списку нескучных дней и отмечаем те дни, которые являются предыдущими или следующими для уже отмеченных нескучных дней.
-
Запланирование событий с открытой датой: выбираем m дней из списка нескучных дней, где m - количество событий с открытой датой.
-
Вывод результатов: выводим количество нескучных дней и выбранные дни для планирования событий с открытой датой.
Ниже приведена реализация данного алгоритма на языке Python:
n, m, k = map(int, input().split()) event_days = list(map(int, input().split())) boring_days = [False] * n # отметка дней с известными событиями как нескучных for day in event_days: boring_days[day-1] = True # отметка дней, которые могут стать нескучными for i in range(1, n-1): if boring_days[i-1] or boring_days[i+1]: boring_days[i] = True # выбор m дней для планирования событий с открытой датой planned_event_days = [] count = 0 for i in range(n): if not boring_days[i]: planned_event_days.append(i+1) count += 1 if count == m: break # вывод результатов print(count) print(*planned_event_days)Программа принимает на вход значения n, m и k, а затем вторую строку ввода, содержащую номера дней с известными событиями. После этого программа выводит количество нескучных дней и номера дней для планирования событий с открытой датой.
-