При онлайн-⁠покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить билет на такое место в ряду, чтобы перед ним как можно больше идущих подряд кресел с таким же номером было свободно. Если места, удовлетворяющие этому условию, есть в нескольких рядах, то нужно выбрать ряд, расположенный как можно ближе к сцене. В ответе запишите два целых числа: искомый номер ряда и количество свободных кресел перед выбранным местом. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одно такое место в зале есть. Входные данные. В первой строке входного файла находятся три числа: N   количество занятых мест в зале (целое положительное число, не превышающее 10 000), М   количество рядов (целое положительное число, не превышающее 100 000) и K   количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих N строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения M, а второе   K). Выходные данные. Два целых положительных числа: искомый номер ряда и количество свободных кресел перед выбранным местом. 2626.txt

Привет! Давай разберём твою задачу по ЕГЭ и сравним с правильным подходом. 1) Что ты прислал - Ты написал: "Ученик не дал ответ на задание". Это не ответ на задачу — нам нужно получить конкретные два целых числа: номер ряда и количество свободных кресел перед выбранным местом. Поэтому такой ответ нельзя считать правильным. 2) Как решить задачу (кратко и по существу) Идея: рассматриваем каждый номер места (столбец по залу). Для каждого столбца s мы смотрим, в каких рядах там заняты места с этим номером. Далее по каждому столбцу находим максимальное число подряд свободных кресел перед выбранным местом, и выбираем самый раний по сцене ряд в случае равенства. Пошагово: - Построить словарь: для каждого номера места s хранить список рядов, в которых место (row, s) занято. - Добавить границы: для каждого s возьмём отсортированный список занятых строк rows = [r1, r2, ..., rk], и рассчитаем интервалы свободных рядов между занятыми: - Пусть previous = 0 (начало зала) и i пробегает по отсортированному списку занятых rows. - Для каждого occupied = ri: - длина свободного промежутка между previous и ri: gap = ri - previous - 1. - если gap > 0, то можно выбрать место в конце этого промежутка: rowCandidate = ri - 1, countCandidate = gap - 1. - обновляем глобальный максимум: если countCandidate больше текущего, запоминаем rowCandidate и countCandidate. Если равенство по countCandidate и rowCandidate меньше текущего лучшего ряда — обновляем лучший ряд. - ставим previous = ri и переходим к следующему occupied. - После цикла обработаем окончательный промежуток до конца зала: gap = M - previous; если gap > 0, то rowCandidate = M, countCandidate = gap - 1; обновляем максимум аналогично. - В итоге получаем глобально лучший ряд bestRow и количество свободных кресел bestCount. - Выводим: bestRow и bestCount. Некоторые пояснения: - Эталонный ответ для данных задачи может быть 665 61 (пример из твоего сообщения). - Смысл: максимум свободных кресел перед выбранным местом достигается на конце какого-либо свободного отрезка в столбце (номер места s фиксирован), и этот конец находится в строке ri-1, где ri — ближайшая занятая строка выше этого конца. Для последнего открытого блока до конца зала строка будет M. 3) Почему твой ответ неверен - Твой ответ не содержит чисел, поэтому он не решает задачу и не может быть корректным. - Чтобы проверить правильность, нужно применить именно описанный выше подход и получить конкретное число row и count. В твоём примере правильный результат — 665 61, т.е. лучший ряд 665 и 61 свободное кресло перед выбранным местом. 4) Подсказка, чтобы двинуться вперёд - Сфокусируйся на столбцах (номерах мест). Для каждого номера места собери список занятых рядов. Затем через этот список найдИ интервалы свободных рядов между соседними занятыми рядами и у границ (0 и M+1). В каждом таком интервале можно выбрать место в конце интервала; количество свободных кресел перед ним равно длине интервала минус 1. Следи за тем, чтобы выбирать максимальное значение count, и в случае равенства — минимальный номер ряда. Если хочешь, могу привести маленький примеры на hand-пояснение или помочь написать короткий код на твоём языке обучения (псевдокод тоже подойдёт). Просто скажи, на каком языке ты хочешь увидеть решение. Пожалуйста, оцените мой ответ лайком или дизлайком.