Ваня большой фанат шахмат, он перепробовал уже кучу вариаций игры. И вот, когда казалось, что Ваня уже прошел шахматы, он придумал новый вариант, который он гордо называет Шахматы 2.0! В данную игру можно играть даже одному, в ней есть всего два вида

Добавлена: 08.06.2026
Обновлена: 08.06.2026
Предмет: Искусство
Автор: Кэмп

#Теория искусства
#Проектирование в искусстве

Условие:

Ваня большой фанат шахмат, он перепробовал уже кучу вариаций игры. И вот, когда казалось, что Ваня уже прошел шахматы, он придумал новый вариант, который он гордо называет Шахматы 2.0! В данную игру можно играть даже одному, в ней есть всего два вида хода: 1) Добавить Ферзя в любую свободную клетку на доске 2) Спросить про любую клетку, может ли хотя бы один Ферзь добраться до нее не более чем за один ход.

Напомним вам, что, несмотря на внушительные размеры доски, Ферзь все еще может перемещаться на любое количество клеток по вертикали, горизонтали и диагонали.

Решение:

Для решения этой задачи нам необходимо эффективно отслеживать положение ферзей на доске размером $N \times N$ и быстро проверять, бьется ли заданная клетка $(x, y)$ хотя бы одним из них.

Анализ условий

Ферзь бьет клетку $(x, y)$ , если он находится:

В той же строке: его координата $x_i = x$ .
В том же столбце: его координата $y_i = y$ .
На той же главной диагонали: $x_i - y_i = x - y$ .
На той же побочной диагонали: $x_i + y_i = x + y$ .

Так как $N$ может достигать $10^9$ , мы не можем использовать двумерный массив. Однако количество ходов $q$ ограничено $2 \times 10^5$ . Это значит...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какой из перечисленных подходов является наиболее эффективным для отслеживания положения ферзей и проверки атакуемых ими клеток на шахматной доске размером $N \times N$, где $N$ может быть очень большим ($10^9$), но количество ферзей $q$ ограничено ($2 \times 10^5$)?

Использование двумерного массива для представления доски и пометки занятых клеток.

Хранение координат ферзей в четырех отдельных множествах (для строк, столбцов, главной и побочной диагоналей) и проверка наличия координат в этих множествах.

Создание списка всех ферзей и для каждого запроса перебор всех ферзей для проверки, атакуют ли они заданную клетку.