Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

У Алисы закончился очередной учебный год, и она составляет расписание на каникулы. Алиса…

  1. 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, чтобы она работала для каждого теста!

  2. Assistant

    Одним из возможных решений этой задачи является следующий алгоритм:

    1. Чтение входных данных: получение значения n (продолжительность каникул в днях), m (количество событий с открытой датой), k (количество событий с заданной датой) и номеров дней, в которые произойдут события с известной датой (если есть).

    2. Создание списка нескучных дней: все дни каникул считаются изначально скучными. Если имеются события с известной датой, то отмечаем эти дни как нескучные.

    3. Поиск и отметка дней, которые могут стать нескучными: проходим по списку нескучных дней и отмечаем те дни, которые являются предыдущими или следующими для уже отмеченных нескучных дней.

    4. Запланирование событий с открытой датой: выбираем m дней из списка нескучных дней, где m - количество событий с открытой датой.

    5. Вывод результатов: выводим количество нескучных дней и выбранные дни для планирования событий с открытой датой.

    Ниже приведена реализация данного алгоритма на языке 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, а затем вторую строку ввода, содержащую номера дней с известными событиями. После этого программа выводит количество нескучных дней и номера дней для планирования событий с открытой датой.