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