Задание 6 ЕГЭ по информатике

Question

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд $\textbf n$ (где $n$  –  целое число), вызывающая передвижение Черепахи на $n$ единиц в том направлении, куда указывает её голова; Назад $\textbf n$(где $n$  –  целое число), вызывающая передвижение в противоположном голове направлении; Направо $\textbf m$ (где $m$  –  целое число), вызывающая изменение направления движения на $m$ градусов по часовой стрелке, Налево $\textbf m$ (где $m$  –  целое число), вызывающая изменение направления движения на $m$ градусов против часовой стрелки.
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из $S$ команд повторится $k$ раз.
Черепахе был дан для исполнения следующий алгоритм:
Повтори 5 [Вперёд 21 Направо 90 Вперёд 27 Направо 90]
Поднять хвост
Вперёд 13 Направо 90 Вперёд 30 Направо 90
Опустить хвост
Повтори 5 [Вперёд 47 Направо 90 Вперёд 86 Направо 90].
Определите, сколько точек с целочисленными координатами будут находиться внутри объединения фигур, ограниченных заданными алгоритмом линиями, включая точки на границах этого объединения.

Accepted Answer

Способ 1. Аналитический подход
1. Разберём движение Черепахи.
После каждых двух выполнений команд:
Вперёд ... Направо 90 Вперёд ... Направо 90
Черепаха возвращается в исходную точку и полностью обводит прямоугольник, поэтому пять повторений не создают новую фигуру: Черепаха несколько раз проходит по тем же сторонам.
1.1. Первая фигура
Начальная точка: $(0;0)$, направление - вверх.
За первое повторение Черепаха проходит: $(0;0)→(0;21)→(27;21)$.
За второе повторение: $(27;21)→(27;0)→(0;0)$.
Получается прямоугольник с вершинами: $(0;0)$, $(0;21)$, $(27;21)$, $(27;0)$.
После пяти повторений Черепаха находится в точке $(27;21)$ и направлена вниз.
1.2. Переход ко второй фигуре
Хвост поднят, поэтому следующие перемещения линий не оставляют.
Черепаха проходит вперёд 13 единиц: $(27;21)→(27;8)$.
Поворачивает направо. Теперь она направлена влево.
Проходит вперёд 30 единиц: $(27;8)→(−3;8)$.
После ещё одного поворота направо Черепаха направлена вверх.
1.3. Вторая фигура
Начальная точка второй фигуры: $(−3;8)$.
За первые два повторения Черепаха обводит прямоугольник с вершинами:$(−3;8)$, $(−3;55)$, $(83;55)$, $(83;8)$.
Таким образом, получены два пересекающихся прямоугольника.
2. Подсчёт точек.
Для прямоугольника с целочисленными границами количество точек, включая границу, вычисляется по формуле: $(x_{max}-x_{min}+1)*(y_{max}-y_{min}+1)$.
Количество точек для первого прямоугольника: $(27-0+1)*(21-0+1)=28*22=616$.
Количество точек для второго прямоугольника: $(83-(-3)+1)*(55-8+1)=87*48=4176$.
Пересечение прямоугольников имеет границы: $0 \le x\le 27$ и $8 \le y \le 21$.
Соответственно, количество точек в пересечении: $(27-0+1)*(21-8+1)=28*14=392$.
Так как точки пересечения дублируются и для первого, и для второго прямоугольников, то:
$616+4176-392=4400$.
Ответ: 4400.
Способ 2. Программный подход
1. Построим маршрут передвижений Черепахи.
from turtle import *

# Настраиваем размер окна
screensize(2000, 2000)
# Отключаем анимацию рисования
tracer(0)

# Устанавливаем масштаб: одна единица алгоритма равна 10 пикселям
scale = 10

# Поворачиваем Черепаху налево, чтобы направить вдоль положительного направления оси ординат
left(90)
# Опускаем хвост перед началом движения
down()

# Рисуем первый прямоугольник
for _ in range(5):
forward(21 * scale)
right(90)
forward(27 * scale)
right(90)

# Поднимаем хвост и переходим к началу второй фигуры
up()
forward(13 * scale)
right(90)
forward(30 * scale)
right(90)

# Опускаем хвост
down()

# Рисуем второй прямоугольник
for _ in range(5):
forward(47 * scale)
right(90)
forward(86 * scale)
right(90)

# Поднимаем хвост, чтобы не оставлять линии
up()

# Отмечаем целочисленные точки координатной плоскости
for x in range(-100, 100):
for y in range(-100, 100):
setpos(x * scale, y * scale)
dot(4, 'blue')

# Оставляем окно открытым
done()
exit()
Получаем рисунок:
2. Подсчёт точек.
Для прямоугольника со сторонами $a$ и $b$ число точек с целочисленными координатами, включая границу, равно $(a+1)*(b+1)$.
Прибавляем единицу, потому что на отрезке длиной $a$ расположено $a+1$ целочисленных точек. Например, на отрезке от 0 до 3 находятся точки 0, 1, 2, 3, то есть 4 точки.
Количество точек для первого прямоугольника:
$(27+1)*(21+1)=28*22=616$.
Количество точек для второго прямоугольника:
$(86+1)*(47+1)=87*48=4176$.
Пересечение прямоугольников по горизонтали имеет длину 27. По вертикали второй прямоугольник начинается на высоте 8, а первый заканчивается на высоте 21. Поэтому высота общей части равна $21−8=13$.
Соответственно, количество точек в пересечении:
$(27+1)*(13+1)=28*14=392$.
Так как точки пересечения дублируются и для первого, и для второго прямоугольников, то:
$616+4176-392=4400$.
Ответ: 4400.

Задание 6 ЕГЭ по информатике

Циклические программы для исполнителя Черепаха