Тридевятом царстве на острове Буяне продолжительность основного тура олимпиады по информатике «Алгоритм победы» составляет t t минут. В рамках этого тура школьникам предстоит…

Question

Задача Задача №3158975

А

Аноним

30 апреля 2025 12:24 · публичный вопрос

А

Аноним 30 апреля 2025 12:24

Тридевятом царстве на острове Буяне продолжительность основного тура олимпиады по информатике «Алгоритм победы» составляет t t минут. В рамках этого тура школьникам предстоит…

Запрос пользователя

Тридевятом царстве на острове Буяне продолжительность основного тура олимпиады по информатике «Алгоритм победы» составляет t t минут. В рамках этого тура школьникам предстоит решить n n задач различной сложности, пронумерованных от 1 1 до n n. Пончик, представитель команды Цветочного города, отличается высокой тренированностью и знает, что для решения i i-й задачи ему потребуется a i a i минут. У него есть свои принципы, которые он неукоснительно соблюдает: он выбирает произвольную задачу с номером i i и решает их последовательно, начиная с этой задачи. Это означает, что сначала Пончик сдаст задачу с номером i i, затем задачу с номером i + 1 i+1, потом i + 2 i+2 и так далее. Он продолжает решать задачи до тех пор, пока не закончится время t t или пока не дойдет до задачи с номером n n. Важно отметить, что каждую задачу контеста умный Пончик решает на 100 очков, то есть полностью. Ваша задача – определить максимальное количество задач, которое умный Пончик сможет решить на олимпиаде «Алгоритм победы». Формат ввода В первой строке вводятся два целых числа: n n ( 1 ≤ n ≤ 1 0 5 1≤n≤10 5 ) – количество задач в контесте и t t ( 1 ≤ t ≤ 1 0 9 1≤t≤10 9 ) – продолжительность основного тура в минутах. Во второй строке следуют n n целых чисел a i a i ( 1 ≤ a i ≤ 1 0 4 1≤a i ≤10 4 ) – количество минут, которое требуется умному Пончику на решение i i-й задачи контеста. Формат вывода Выведите одно целое число – максимальное количество задач, которое умный Пончик сможет решить на олимпиаде «Алгоритм победы 2025». Система оценивания Первая группа тестов: n ≤ 100 n≤100 – не более 20 баллов. Вторая группа: без ограничений – 80 баллов. Пример 1 Ввод Вывод 4 5 3 1 2 1 3 Пример 2 Ввод Вывод 3 3 2 2 3 1 Пример 3 Ввод Вывод 7 29 6 9 6 3 7 8 6 В преддверии олимпиады «Алгоритм победы» в Цветочном городе Знайкой был проведен турнир по спортивному программированию для малышей и малышек. В отборочном туре каждый участник мог набрать максимум 1000 1000 очков. Заключительный этап олимпиады пройдет на острове Буян в Тридевятом царстве. В нем примут участие коротышки, набравшие не менее X X очков в отборочном туре. Ваша задача – составить список участников финала в лексикографическом порядке. Обратите внимание, что в Цветочном городе нет двух коротышек с одинаковыми именами. Более того, имя коротышки всегда начинается с заглавной буквы, и больше заглавных букв в имени нет. Формат ввода В первой строке задано число n n ( 1 ≤ n ≤ 1 0 4 1≤n≤10 4 ) – количество участников отборочного тура. В следующих n n строках через пробел указаны имя коротышки и количество набранных им очков. Имя представляет собой слово, состоящее из латинских букв, длиной не более 10 символов, а очки — целое число, не превышающее 1000 1000. В последней строке указан проходной балл в финал олимпиады X X ( 10 ≤ X ≤ 1000 10≤X≤1000). Формат вывода Выведите список участников финала олимпиады на острове Буяне, следуя условиям задачи. Укажите количество участников и перечислите их имена в лексикографическом порядке и набранные каждым участником баллы. Если никто из участников отборочного тура не прошел в финал, выведите − 1 −1. Система оценивания Первая группа тестов n ≤ 100 n≤100 – 40 баллов. Вторая группа тестов n ≤ 1000 n≤1000 – 32 балла. Третья группа – нет ограничений – 28 баллов. Пример Ввод Вывод 6 Donut 510 Grumpy 250 Dunno 600 Button 920 Znayka 1000 Vintik 480 500 4 Button 920 Donut 510 Dunno 600 Znayka 1000

Ответ нейросети

30 апреля 2025 12:24

Давайте разберём обе задачи подробно и шаг за шагом.

Задача 1: Максимальное количество решённых задач на олимпиаде

Условие:

Есть n задач.
Время на выполнение всей олимпиады — t минут.
Для каждой задачи i известно время a_i.
Можно выбрать любую задачу i и решать её последовательно, начиная с неё, до конца задач и пока не закончится время t.
Нужно определить максимальное количество задач, которые можно решить, начиная с любой задачи.

Подход к решению:

Понимание задачи:
- Можно выбрать любую задачу i.
- Решать задачи с i по n.
- Общее время для решения задач с i до k — сумма a_i + a_{i+1} + ... + a_k.
- Нужно найти такой i, для которого сумма a_i + ... + a_j максимально возможна, не превышая t, и при этом j максимально возможен.

План решения:

Протяженный случай и эффективность:
- Время n может быть до 10^5.
- Значит, простой перебор всех вариантов с вложенными циклами не подойдет из-за ограничения времени.
- Можно использовать Два указателя (two-pointer) для эффективного подсчёта суммы на подотрезках.
Два указателя:
- Изначально оба указателя (left и right) указывают на начало массива.
- Расширяем right, добавляя a[right], пока сумма не превысит t.
- Как только сумма превысит t, сдвигаем left, убирая из суммы a[left].
- В каждый момент времени запоминаем длину текущего интервала, если он допустим.
- В конце перебираем все возможные интерваллы, чтобы найти максимум.

Код решения:

n, t = map(int, input().split())
a = list(map(int, input().split()))

left = 0
current_sum = 0
max_tasks = 0

for right in range(n):
    current_sum += a[right]
    while current_sum > t:
        current_sum -= a[left]
        left += 1
    max_tasks = max(max_tasks, right - left + 1)

print(max_tasks)

Объяснение кода:

Инициализация left = 0, current_sum = 0.
Проходим по right от 0 до n-1.
Добавляем a[right] к текущей сумме.
Пока сумма превышает t, сдвигаем left и убираем a[left] из суммы.
Обновляем максимум задач, которые можно решить начиная с left и ending с right.

Задача 2: Выбор финалистов по баллам

Условие:

Есть список участников с именами и баллами.
Необходимо вывести всех участников, набравших не менее X баллов.
Отсортировать их по имени в лексикографическом порядке.
Если никто не прошёл, вывести -1.

План решения:

Вводим число участников n.
Считываем список участников (имя, балл).
Вводим проходной балл X.
Отбираем участников, у которых балл >= X.
Если таких участников нет, выводим -1.
Иначе сортируем их по имени и выводим.

Код решения:

n = int(input())
participants = []

for _ in range(n):
    line = input().split()
    name = line[0]
    score = int(line[1])
    participants.append((name, score))

X = int(input())

# Отбираем участников, набравших не менее X
finalists = [p for p in participants if p[1] >= X]

if not finalists:
    print(-1)
else:
    # Сортируем по имени
    finalists.sort(key=lambda x: x[0])
    print(len(finalists))
    for name, score in finalists:
        print(name, score)

Итог:

Первая задача — использование двух указателей.
Вторая задача — фильтрация и сортировка.

Если требуется, я могу помочь с более подробным разбором или объяснением любого из пунктов!