Задания олимпиады морской бой
Аня с Борей играют в «морской бой» по следующим правилам: на окружности выбираются 29 различных точек, пронумерованных по часовой стрелке натуральными числами от 1 до 29. Аня рисует корабль – произвольный треугольник с вершинами в этих точках. Будем называть «выстрелом» выбор двух различных натуральных чисел k и m от 1 до 29. Если отрезок с концами в точках с номерами k и m имеет с треугольником Ани хотя бы одну общую точку, то корабль считается «раненым». Боря производит «залп» – несколько выстрелов одновременно. Аня нарисовала корабль и показала его Боре. И тут они заметили, что любой «залп» из K различных выстрелов обязательно ранит корабль Ани. Укажите какое-нибудь расположение корабля Ани, при котором значение К будет минимальным.
Вершины треугольника Ани делят окружность на три дуги (рис.). Пусть и — количество точек на этих дугах (рис.), не считая вершины самого треугольника. Чтобы «выстрел» с концами в точках k и m не задел корабль, надо чтобы обе эти точки лежали на одной из дуг. Выбрать две различные точки на дуге, содержащей x точек, можно, очевидно, способами. То же и для остальных дуг. Значит, число N «безопасных» выстрелов равно сумме Тогда следующий выстрел уже обязательно «ранит» корабль, поэтому
Итак, требуется найти такие целые неотрицательные числа удовлетворяющие условию при которых значение N минимально. Запишем выражение для N в развернутом виде:
Раскрыв скобки и приведя подобные, получим
При каждом фиксированном y от 0 до 26 будем искать такое значение x, удовлетворяющее неравенству
при котором значение N минимально. Если y фиксирован, то правая часть принимает минимальное значение при
Это минимальное значение равно Оно, в свою очередь, минимально при ≈ 8,6. Тогда Среди точек с целыми координатами (8,8), (8,9), (9,8), (9,9) – ближайших целочисленных соседей точки минимума – выбираем ту, которой соответствует наименьшее значение N. Это точки (8,9), (9,8), (9,9). Для них N = 100.
Ответ: Корабль следует расположить так, чтобы на трех дугах, на которые вершины корабля разбивают окружность, располагалось по 8, 9 и 9 точек (не считая вершины самого корабля).
Источник
Разбор олимпиадной задачи — Морской бой — 2
«Морской бой» — игра для двух участников, в которой игроки по очереди называют координаты на неизвестной им карте соперника. Если у соперника по этим координатам имеется корабль, то корабль или его часть «топится», а попавший получает право сделать еще один ход. Цель игрока — первым поразить все корабли противника. «Морской бой» очень популярен среди учеников одной физико-математической школы. Ребята очень любят в него играть на переменах. Вот и сейчас ученики Иннокентий и Емельян начали новую партию. Правила, по которым ребята расставляют корабли перед началом партии, несколько отличаются от классических. Во-первых, игра происходит на поле размером N×M, а не 10×10. Во-вторых, число кораблей, их размер и форма выбираются ребятами перед партией — так играть намного интереснее. Емельян уже расставил все свои корабли, кроме одного однопалубного. Такой корабль занимает ровно одну клетку. Задана расстановка кораблей Емельяна. Найдите число способов поставить оставшийся однопалубный корабль. При этом учитывайте, что по правилам его можно ставить только в ту клетку, все соседние с которой не заняты. В этой задаче соседними считаются клетки, имеющие общую сторону. Входные данные Первая строка входного файла INPUT.TXT содержит два числа: N и M (1 ≤ N, M ≤ 100) . Последующие N строк описывают игровое поле — каждая из них содержит M символов. Символом «.» (точка) обозначена свободная клетка, символом «*» (звездочка) — занятая кораблем. Выходные данные В выходной файл OUTPUT.TXT выведите ответ на задачу. Примеры
№ INPUT.TXT OUTPUT.TXT 1 4 4
****
**..
*…
*…4 2 4 3
***
…
…
***0
Разбор решения задачи
Это прекрасная практика к темам «Массивы» (потому что игровое поле задается двумерным массивом), «Циклы» и «Функции» (так как код станет гораздо лучше если выделить вспомогательные функции, но нужно не забыть про передачу параметров по ссылке). Картинка к первому примеру задачи — красным обозначены занятые клетки, розовым — битые (в них тоже ставить нельзя), зеленым свободные:
Все выглядит просто — берем клетку с координатами [i, j] , проверяем что она свободна, а также — свободны соседние 4 клетки. На самом деле — нужно не забыть проверить корректность индексов соседних клеток, т.к. [i-1, j] может оказаться некорректным если i = 0 . Аналогично можно выйти за пределы поля справа, слева и снизу. Мы можем написать функции, проверяющие корректность индексов, пустоту клетки и соседних клеток:
#include #include #include using namespace std; bool is_correct_position(const vector> &gameboard, int i, int j) < return i >= 0 && j >= 0 && i < gameboard.size() && j < gameboard[0].size(); >bool is_free(const vector> &gameboard, int i, int j) < if (is_correct_position(gameboard, i, j) == false) return true; return gameboard[i][j] == '.'; >bool can_build(const vector> &gameboard, int i, int j) < return is_free(gameboard, i, j) && is_free(gameboard, i-1, j) && is_free(gameboard, i+1, j) && is_free(gameboard, i, j-1) && is_free(gameboard, i, j+1); >int main() < ifstream ifst("input.txt"); ofstream ofst("output.txt"); int n, m; ifst >> n >> m; vector> gameboard(n, vector(m)); for (auto& line : gameboard) < for (auto& cell : line) < ifst >> cell; > > int counter = 0; for (int i = 0; i < n; ++i) < for (int j = 0; j < m; ++j) < counter += can_build(gameboard, i, j); >> ofst
Это вполне нормальное решение, но не очень хорошо выглядит «если позиция [i, j] некорректная — то клетка [i, j] пустая». Часто в таких задачах (да и казуальных игрушках) в игровое поле добавляют границы. Например, пишите вы игру — Змейка и хотите чтобы она «разбивалась при достижении края поля. Проверки валидности границ выглядят в коде плохо. В нашем случае вокруг поля удобно добавить пустые клетки, не доступные для установки кораблей. Для этого при конструировании поля — задаим дополнительные 2 строки и 2 столбца, изначально все поле сделаем свободным, а затем — заполним внутренние клетки содержимым файла:
#include #include using namespace std; bool is_free(const vector> &gameboard, int i, int j) < return gameboard[i][j] == '.'; >bool can_build(const vector> &gameboard, int i, int j) < return is_free(gameboard, i, j) && is_free(gameboard, i-1, j) && is_free(gameboard, i+1, j) && is_free(gameboard, i, j-1) && is_free(gameboard, i, j+1); >int main() < ifstream ifst("input.txt"); ofstream ofst("output.txt"); int n, m; ifst >> n >> m; vector> gameboard(n+2, vector(m+2, ‘.’)); for (int i = 1; i < n+1; ++i) < for (int j = 1; j < m+1; ++j) < ifst >> gameboard[i][j]; > > int counter = 0; for (int i = 1; i < n+1; ++i) < for (int j = 1; j < m+1; ++j) < counter += can_build(gameboard, i, j); >> ofst
Источник