Задание 26 ЕГЭ по информатике · BE60AB
Два свободных места между занятымиВысокаяКЭС 3.10
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, такие что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
В первой строке входного файла находится число N — количество занятых мест, не превышающее 10 000. Каждая из следующих N строк содержит два натуральных числа: номер ряда и номер занятого места. Номера ряда и места не превышают 100 000.
В выходном файле должны быть записаны два целых неотрицательных числа: номер ряда и наименьший номер места в выбранной паре.
1_BE60AB.zipВ первой строке входного файла находится число N — количество занятых мест, не превышающее 10 000. Каждая из следующих N строк содержит два натуральных числа: номер ряда и номер занятого места. Номера ряда и места не превышают 100 000.
В выходном файле должны быть записаны два целых неотрицательных числа: номер ряда и наименьший номер места в выбранной паре.
Показать ответ
69920 90893
Подсказки (3)
- Как по номерам занятых мест в одном ряду обнаружить две соседние свободные позиции, ограниченные занятыми местами?
- После сортировки занятых мест в ряду ищите соседние занятые места с разностью 3: если заняты места x и x+3, то места x+1 и x+2 образуют подходящую пару.
- Для каждой найденной пары сохраните номер ряда и x+1. Выберите максимальный номер ряда, а среди пар в этом ряду — минимальное значение x+1.
Решение
1. Сгруппировать номера занятых мест по номерам рядов.
2. В каждом ряду отсортировать номера занятых мест по возрастанию.
3. Просмотреть соседние элементы отсортированного списка. Если два соседних занятых места имеют разность 3, то два места между ними свободны и образуют подходящую пару.
ai+1−ai=3⇒(ai+1, ai+2)
4. Среди всех найденных пар выбрать пару с максимальным номером ряда. Если в этом ряду найдено несколько пар, выбрать пару с минимальным первым номером места.
2. В каждом ряду отсортировать номера занятых мест по возрастанию.
3. Просмотреть соседние элементы отсортированного списка. Если два соседних занятых места имеют разность 3, то два места между ними свободны и образуют подходящую пару.
ai+1−ai=3⇒(ai+1, ai+2)
4. Среди всех найденных пар выбрать пару с максимальным номером ряда. Если в этом ряду найдено несколько пар, выбрать пару с минимальным первым номером места.
Частые ошибки
- Проверяют только наличие двух свободных мест, но не проверяют занятые места непосредственно слева и справа.
- Выбирают ряд с наименьшим, а не с наибольшим номером.
- При нескольких подходящих парах в одном ряду выбирают не пару с минимальным первым номером места.
- Не сортируют номера мест перед поиском соседних занятых мест.
Источник: Открытый банк ФИПИ
Похожие задания
26Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке.…Два свободных места между занятыми · 97FA8B26При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить билет на…Два свободных места между занятыми · 9A0AE426При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на…Два свободных места между занятыми · AD6F7026Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке.…Два свободных места между занятыми · BD5ECE26Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке.…Два свободных места между занятыми · C3D45026Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке.…Два свободных места между занятыми · FC12A4
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.