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