{"problem":{"name":"J. Рудольф и Marine Front Unlimited ZX","description":{"content":"Игра «Marine Front Unlimited ZX» становится очень популярной в Сети — все друзья Рудольфа только и делают, что говорят о ней! Рудольф тоже решил попробовать модную игру, но, поиграв в неё несколько ми","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10132J"},"statements":[{"statement_type":"Markdown","content":"Игра «Marine Front Unlimited ZX» становится очень популярной в Сети — все друзья Рудольфа только и делают, что говорят о ней! Рудольф тоже решил попробовать модную игру, но, поиграв в неё несколько минут, начал что-то подозревать. Поиграв ещё пару часов, он полностью убедился в том, что невероятная новинка — не более чем очередной клон игры «Морской бой».\n\nЕсли вы вдруг не знаете, как играть в «Морской бой», то мы вам расскажем. Эта игра предназначена для двух игроков. Прежде всего каждый из них берёт клетчатый лист и очерчивает на нём два одинаковых поля, содержащих n столбцов и m строк, — одно для своих кораблей, а другое для кораблей противника. Столбцы каждого из полей помечаются слева направо первыми n буквами латинского алфавита, а строки — сверху вниз первыми m натуральными числами. Таким образом, каждая клетка имеет уникальные координаты: например, левый верхний угол обозначается как _a1_. Затем каждый из игроков втайне от другого рисует на своём поле набор кораблей — фигур, составленных из клеток, имеющих общую сторону. Форма, количество и правила размещения кораблей зависят от конкретных вариантов игры.\n\nНа этом подготовка завершается, и игроки начинают по очереди обстреливать поле противника. Один игрок называет другому координаты клетки, по которой он стреляет. Если в этой клетке нет кораблей, второй игрок отвечает «Мимо» и получает право хода. В противном случае второй игрок говорит «Попал» (или «Потопил», если противник уже расстрелял все остальные клетки корабля), а первый может стрелять ещё раз. Цель игры — первым потопить все корабли соперника.\n\nВ «Marine Front Unlimited ZX» в роли противника выступает компьютер. Рудольф заметил, что интеллект у него так себе — он всегда обстреливает клетки игрока в одном и том же порядке! Тем не менее, у игры есть и положительные стороны — например, достижения. Для получения одного из них требуется поставить на своём поле единственный четырёхпалубник (прямоугольник 1 × 4 или 4 × 1) таким образом, чтобы компьютер потопил его как можно позже. Однако и компьютер при этом меняет свою стратегию: он заведомо не стреляет по клеткам, в которых четырёхпалубник не может оказаться, а впервые попав по нему, всегда добивает его тремя следующими выстрелами.\n\nХоть Рудольф и не в восторге от новой игры, но получить достижение он всё-таки хочет. Помогите ему правильно поставить корабль.\n\nПервая строка содержит целые числа n и m (4 ≤ n, m ≤ 26) — количество столбцов и строк игрового поля соответственно.\n\nСледующие m × n строк описывают порядок, в котором компьютерный противник обстреливает клетки. Каждая из этих строк содержит координаты одной из клеток поля. Гарантируется, что все координаты уникальны.\n\nВыведите одно целое число — максимальное количество выстрелов, после которых размещённый некоторым образом на поле четырёхпалубник будет потоплен.\n\nВ первом примере целесообразно разместить четырёхпалубник в клетках _b4_, _c4_, _d4_, _e4_. Компьютер не будет стрелять по клеткам _с2_, _d2_, _e2_, _c3_, _d3_, _e3_, так как после обстрела предыдущих клеток ясно, что корабль в них оказаться не может.\n\n## Входные Данные\n\nПервая строка содержит целые числа n и m (4 ≤ n, m ≤ 26) — количество столбцов и строк игрового поля соответственно.Следующие m × n строк описывают порядок, в котором компьютерный противник обстреливает клетки. Каждая из этих строк содержит координаты одной из клеток поля. Гарантируется, что все координаты уникальны.\n\n## Выходные Данные\n\nВыведите одно целое число — максимальное количество выстрелов, после которых размещённый некоторым образом на поле четырёхпалубник будет потоплен.\n\n## Примеры\n\nВходные данные5 4a1b1c1d1e1a2b2c2d2e2a3b3c3d3e3a4b4c4d4e4Выходные данные14Входные данные4 4c4d3d4c3a1a2a3a4b4b3b2b1c1d1c2d2Выходные данные8\n\n## Примечание\n\nВ первом примере целесообразно разместить четырёхпалубник в клетках _b4_, _c4_, _d4_, _e4_. Компьютер не будет стрелять по клеткам _с2_, _d2_, _e2_, _c3_, _d3_, _e3_, так как после обстрела предыдущих клеток ясно, что корабль в них оказаться не может.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ with $ 4 \\leq n, m \\leq 26 $ be the number of columns and rows of the grid.  \nLet $ L = (c_1, c_2, \\dots, c_{n \\cdot m}) $ be the fixed sequence of cell coordinates (in Latin-alphabet + number format) representing the computer's shooting order.  \nLet $ S $ be the set of all possible placements of a $ 1 \\times 4 $ or $ 4 \\times 1 $ ship on the $ n \\times m $ grid, where each placement occupies four orthogonally adjacent cells.  \n\n**Constraints**  \n1. Each ship placement is axis-aligned and fits entirely within the grid.  \n2. The computer shoots cells in the exact order $ L $, skipping any cell that cannot contain the ship (based on prior misses and the constraint that the ship is contiguous and of length 4).  \n3. Upon first hit, the computer immediately fires the next three shots at the remaining three cells of the ship (in the direction of the ship, in order).  \n\n**Objective**  \nFind the maximum possible index $ k \\in \\{1, \\dots, n \\cdot m\\} $ such that there exists a ship placement $ s \\in S $ for which the computer's $ k $-th shot is the *last* shot that hits the ship (i.e., the fourth and final hit).  \n\nThat is, maximize $ k $ such that:  \n- The first three hits on $ s $ occur at positions $ i_1 < i_2 < i_3 < k $ in $ L $,  \n- The fourth hit occurs at position $ k $,  \n- All prior shots (before $ i_1 $) are either misses or not yet logically forced to be on $ s $,  \n- The computer’s strategy ensures no shot is fired at a cell that is provably empty before $ k $.  \n\nOutput: $ \\max \\{ k \\mid \\exists s \\in S \\text{ such that the fourth hit on } s \\text{ occurs at position } k \\text{ in } L \\} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10132J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}