Задание 26 ЕГЭ по информатике · FC12A4
Два свободных места между занятымиВысокаяКЭС 3.10
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
Входные данные
В первой строке входного файла находится число N — количество занятых мест (натуральное число, не превышающее 10\,000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100\,000: номер ряда и номер занятого места.
Выходные данные
Два целых неотрицательных числа: номер ряда и наименьший номер места в выбранной паре.
Пример входного файла: 7; далее пары: (40, 3), (40, 6), (60, 33), (50, 125), (50, 128), (50, 64), (50, 67). Для приведённого примера подходящие пары имеют вид (40, 4), (50, 126), (50, 65), поэтому ответ: 50 65.
1_FC12A4.zipВходные данные
В первой строке входного файла находится число N — количество занятых мест (натуральное число, не превышающее 10\,000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100\,000: номер ряда и номер занятого места.
Выходные данные
Два целых неотрицательных числа: номер ряда и наименьший номер места в выбранной паре.
Пример входного файла: 7; далее пары: (40, 3), (40, 6), (60, 33), (50, 125), (50, 128), (50, 64), (50, 67). Для приведённого примера подходящие пары имеют вид (40, 4), (50, 126), (50, 65), поэтому ответ: 50 65.
Показать ответ
79936 78782
Подсказки (3)
- Как по двум занятым местам определить, что между ними находятся ровно два свободных соседних места?
- Для занятых мест с номерами x и x+3 подходящая пара свободных мест начинается с x+1. Сгруппируйте места по рядам и проверьте наличие обеих границ пары.
- Для каждого ряда переберите занятые места x и проверяйте условия
x. Удобнее проверять шаблон: места x и x+3 заняты, а места x+1 и x+2 свободны. Среди подходящих рядов выберите максимальный номер, а в нём — минимальное начало пары.
otin?
Решение
1. Удобно хранить для каждого ряда множество занятых мест, чтобы проверять принадлежность за постоянное время.
occupied[row]={занятые места в ряду}
2. Две соседние свободные места с занятыми местами слева и справа имеют вид x+1 и x+2, при этом места x и x+3 заняты, а x+1 и x+2 не заняты.
3. Для каждого ряда перебираем занятые места как возможное левое ограничение, находим минимальный номер подходящей пары и сравниваем ряд с текущим лучшим рядом.
4. Если номер ряда больше текущего максимального, заменяем ответ. Если ряд тот же, сохраняем меньший номер места.
occupied[row]={занятые места в ряду}
2. Две соседние свободные места с занятыми местами слева и справа имеют вид x+1 и x+2, при этом места x и x+3 заняты, а x+1 и x+2 не заняты.
x \in occupied,\quad x+1
otin occupied,\quad x+2
otin occupied,\quad x+3 \in occupied3. Для каждого ряда перебираем занятые места как возможное левое ограничение, находим минимальный номер подходящей пары и сравниваем ряд с текущим лучшим рядом.
4. Если номер ряда больше текущего максимального, заменяем ответ. Если ряд тот же, сохраняем меньший номер места.
Частые ошибки
- Выбирать ряд с наименьшим, а не с наибольшим номером.
- Проверять только расстояние между занятыми местами и не убеждаться, что оба внутренних места свободны.
- Выбирать произвольную пару в найденном ряду вместо пары с наименьшим номером места.
- Считать подходящей пару из одного свободного места или пару, для которой занято только одно внешнее место.
Источник: Открытый банк ФИПИ
Похожие задания
26При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на…Два свободных места между занятыми · AD6F7026Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке.…Два свободных места между занятыми · BD5ECE26Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке.…Два свободных места между занятыми · BE60AB26Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке.…Два свободных места между занятыми · C3D45026Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 02861826В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Одну коробку можно…Коробки и коржи: вложение с заданной разностью · 05BFA6
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.