ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Черепаха, Чертёжник и Робот.
| КЭС: | 3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность 3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат 3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры, нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена» 3.5 Многоразрядные целые числа, задачи длинной арифметики |
| Тип ответа: | Краткий ответ |
Ответ: 414
Решение.
Положим исходную клетку в начало координат: x растёт вправо, y — вверх. Команды 1, 2, 3, 4 означают соответственно вверх, вниз, вправо и влево.
Выпишем клетки после команд программы 3233241:
(0; 0) → (1; 0) → (1; −1) → (2; −1) → (3; −1) → (3; −2) → (2; −2) → (2; −1).
Конечная клетка имеет координаты (2; −1). Для возвращения в (0; 0) необходимо суммарное смещение на две клетки влево и на одну вверх.
За три команды это возможно только двумя движениями 4 и одним движением 1. Возможные порядки: 144, 414 и 441. Но гарантированно свободны лишь уже пройденные переходы между соседними клетками.
Для 414 получаем (2; −1) → (1; −1) → (1; 0) → (0; 0). Все три перехода входят в исходный маршрут, поэтому стен на них нет.
Для 144 первым используется переход (2; −1) → (2; 0). Исходная программа его не проходила; там может быть стена.
Для 441 вторым используется переход (1; −1) → (0; −1). Этот переход также не был пройден и может быть закрыт стеной.
Проверка: программа 414 содержит ровно три команды, целиком проходит по известным свободным переходам и заканчивается в исходной клетке. Остальные порядки не гарантируют безопасного возвращения.
Ответ: 414.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFB41709.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.