Задание 26 ЕГЭ информатика: № 26016. Типовые варианты

Петя участвует в расширенной версии игры «Морской бой». В данной версии игры, в отличие от классической, допускается увеличение количества и длины кораблей, а игровое поле может быть прямоугольным, размером M x K, где M – количество горизонтальных рядов клеток на игровом поле (целое положительное число, не превышающее 100 000), K – количество вертикальных рядов клеток на игровом поле (целое положительное число, не превышающее 100 000). Нумерация горизонтальных рядов поля идёт сверху вниз с 1, а вертикальных – слева направо также с 1. Некоторые клетки поля уже заняты кораблями (n-палубный корабль занимает, соответственно, n подряд идущих клеток).

Пете необходимо разместить 2-палубный корабль, расположив его на свободных клетках некоторого одного ряда так, чтобы корабль находился как можно дальше от верхнего края игрового поля и все клетки игрового поля, находящиеся непосредственно над ним, не были заняты другими кораблями. Допускается ставить корабли вплотную друг к другу.

Если в найденном для размещения корабля ряду мест, удовлетворяющих условию, несколько, то найдите место с наименьшими номерами вертикальных рядов. В ответе запишите два целых числа: номер горизонтального ряда и наименьший из двух номеров вертикальных рядов, где необходимо разместить корабль. Гарантируется, что хотя бы одно удовлетворяющее условию место для корабля есть.

Входные данные.

В первой строке входного файла находятся три числа: N – количество клеток игрового поля, в которых расположены однопалубные коробки или части многопалубных кораблей (N – целое положительное число, не превышающее 100 000), M – количество горизонтальных рядов игрового поля и K – количество вертикальных рядов игрового поля. В следующих N строках соответственно находятся пары натуральных чисел: номер горизонтального ряда и номер вертикального ряда игрового поля, в которых расположены корабли или их части (первое число не превышает значения M, а второе – K).

Выходные данные.

Два целых положительные числа: соответственно искомые номера горизонтального ряда и вертикального ряда.

Типовой пример организации данных во входном файле

6 6 7
1 1
5 5
5 6
4 4
2 2
3 3

При таких исходных данные ответом является пара чисел 4 и 5. Условию задачи удовлетворяет расположение корабля в вертикальных рядах 5 и 6 игрового поля в горизонтальном ряду 4.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

2616.txt 187,7 КБ

with open('2616.txt') as file:
    _, M, K = map(int, file.readline().split())
    data = [list(map(int, line.split())) for line in file]

ships = sorted(data, key=lambda x: (x[1], -x[0]))

field = [M + 1] * (K + 2)

for h, v in ships:
    field[v] = h

res = []
for i in range(1, K + 1):
    min_len = min(field[i], field[i + 1])
    if min_len > 1:
        res.append((min_len - 1, i))

res = sorted(res, key=lambda x: (-x[0], x[1]))

print(res[0])

Рекомендуемые статьи