Привет Codeforces! Всех с наступающим! За полгода я придумал множество интересных задачи на тему "Клеточная сетка". Почитайте их, и ваше новогоднее настроение повысится до легендарного гроссмейстера :)

Спасибо medved за перевод задач на английский!

1. Петя и Вася играют в игру на бесконечной клеточной сетке. Вася начинает вторым. Он находится в узле сетки и за один ход двигается в соседний правый узел, или левый, или нижний, или верхний. Петя же в свой ход блокирует один узел сетки. После блокировки Вася не может ходить в этот узел. Может ли Петя сделать так, что Вася не сможет сделать ход?
2. Внутри квадрата 100 × 100 строят клетчатую фигуру по следующим правилам. На первом шаге закрашивают любую клетку. На каждом следующем шаге закрашивают любую клетку, имеющую одну общую сторону с уже закрашенными, и не имеющую с ними других общих вершин и сторон. Какое максимальное число клеток может получиться?
3. Под одной из клеток бесконечного клетчатого поля сидит крот. За n-й ход мы можем проверить любые $$$n^2$$$ клеток. После этого, если мы не нашли крота, он перемещается под любую соседнюю по стороне клетку. Существует ли алгоритм действий, позволяющий рано или поздно поймать бедное животное?
4. Дана клетчатая сетка. Также имеется дерево — изначально это одна вершина в узле сетки. На шаге n мы из любых висячих вершин проводим а) всего n новых рёбер б) всего 4n новых рёбер (по своему желанию), чтобы снова получилось дерево. Мы можем провести ребро в соседнюю вершину вправо, влево, вниз или вверх (то есть 4 варианта). Можно ли сделать процесс бесконечным? Если да, то приведите алгоритм, если нет, то какое максимальное число шагов мы можем сделать?
5. То же самое, что и в задаче 4, только теперь за один шаг мы одновременно из каждой висячей вершины проводим по два ребра (по своему желанию), чтобы снова получилось дерево. Вопрос тот же, можно ли сделать процесc бесконечным? Если да, то приведите алгоритм, если нет, то какое максимальное число шагов мы можем сделать?
6. а) То же, что в задаче 5, только теперь мы можем проводить рёбра в соседние 8 вершин. б) То же, что в предыдущем пункте, но теперь после всех ходов граф должен стать симметричным относительно горизонтальной и вертикальной прямых, проходящих через начальную вершину.
7. Граф строится по тем же правилам что и в задаче 5. Дано число k. Рассмотрим все возможные варианты деревьев. Построим цикл длины k (ребра в цикле могут быть между соседними вершинами по диагонали или стороне клетки, вершины цикла — это узлы сетки), такой что использовано максимальное число ребер из текущего рассматриваемого дерева. Среди всех таких чисел берём максимальное число, пусть равное n. Чему равно число n?

Hi Codeforces! Congratulate everyone with the New Year! For half a year, I was coming up with a lot of interesting problems on the topic "Coordinate Grid Problems". Read them and your New Year's mood will rise to the legendary grandmaster :)

Thank medved for translating the problems into English!

1. Petya and Vasya are playing a game with an infinite coordinate grid. At the beginning, Vasya is at the origin and during each of his turns moves to any adjacent vertex (left, right, up, down). Petya can block a point during his turn, which prevents Vasya from visiting this point again. Considering that Petya starts, can he block Vasya so that Vasya eventually doesn’t have any moves?
2. Consider a process inside a 100 × 100 table. First, you can color any cell black. At each next turn, the cells that have exactly one border adjacent to a colored cell are also colored black. At the end of this process, what is the maximum possible number of black cells?
3. Under one of the cells in an infinite grid sits a mole. To find the mole, we take turns: at the n-th turn, we can check n2 cells, and after that the mole moves to any adjacent cell of his choice. Does there exist an algorithm to find the poor animal?
4. In a coordinate grid, there is a tree, which initially has one vertex at the origin. At the n-th step, we draw a) n new edges b) 4n new edges so that the resulting graph remains a tree. We have 4 options of drawing an edge: left, right, up and down. Can we continue this indefinitely? If so, find an algorithm, otherwise, what is the maximum number of steps that we can do?
5. The same as problem 4, but this time we have to draw two new edges from each vertex of the tree that is a leaf. The question is the same: can we continue this indefinitely? If so, find an algorithm, otherwise, what is the maximum number of steps that we can do? 6а) Same as problem 5, but this time we can draw edges to 8 neighboring vertices. b) Same as 6a, but the resulting graph has to be symmetrical against the x-axis and the y-axis.
6. A tree is constructed by the process outlined in problem 5. For a fixed number k, let’s look at all possible graphs and create a cycle with length k by drawing some edges between neighboring (8 directions) vertices such that the cycle contains the maximum number of vertices from the original tree. Let n be the maximum amount of vertices used from the original tree. What is n?