Skynet: The Chasm

Вторая по списку игра на сайте codingame.com проверяет умение примата пользоваться условными операторами, интуицией и программой по физике за десятый класс. По легенде, на постапокалиптических просторах Земли будущего раскинулась зловещая империя враждебных человеку роботов, но инженерный гений непокоренных программистов-взломщиков дает человечеству шанс на выживание. Подрывная деятельность начинается с малого: под дистанционный контроль удалось взять кремниевые мозги скоростного робота, внешностью и повадками напоминающего модифицированный мотоцикл. Наша задача — создать алгоритм управления, позволяющий машине преодолевать препятствия.

Инициализация:
Каждый уровень поделен на три этапа:

  1. Движение по стартовой площадке.
  2. Прыжок через пропасть.
  3. Торможение на финишной прямой.

До начала игрового цикла программа считывает данные о длине каждого из элементов уровня и сохраняет соответственно в переменные [latex]R, G, L[/latex].

Игровой цикл
На каждой итерации входной поток содержит:

  1. Координату мотоцикла [latex]X[/latex].
  2. Мгновенную скорость мотоцикла [latex]S[/latex].

В выходной поток необходимо вывести одну из четырех команд:

  1. JUMP — совершить прыжок.
  2. SPEED — увеличить скорость на единицу.
  3. SLOW — уменьшить скорость на единицу.
  4. WAIT — ждать следующего хода.

Прежде чем приступить к решению, проанализируем и формализуем задачу.

  1. Размеры мотоцикла не играют роли, потому его движение в рамках рассматриваемой задачи эквивалентно движению материальной точки.
  2. Движение равномерное ([latex]a = 1 \vee a = -1 \vee a = 0[/latex]).
  3. Скорость движения должна быть достаточно большой, чтобы успешно перемахнуть через пропасть, но и достаточно маленькой, чтобы успеть затормозить на финишной прямой. И первое, и второе условие нетрудно рассмотреть аналитически: [latex]S > G + 1 \wedge L > \frac {S^{2}}{2}[/latex]. В первом условии скорость взята «с запасом», так как мотоцикл не обязательно прыгает с края платформы. Второе условие нетрудно получить из уравнения равнозамедленного движения по финишной платформе: [latex]L = vt — \frac {t^{2}}{2} => t^{2} — 2vt + 2L = 0 \quad D = v^{2} — 2L \ge 0 => L \ge \frac {v^{2}}{2}[/latex]. Таким образом, оба условия обоснованы.
  4. Если условие [latex]X+S > R[/latex] истинно, мотоциклисту следует совершить прыжок.

Резюмируя: для успешного прохождения полосы препятствий необходимо:

  • Привести скорость мотоцикла к значению, удовлетворяющему условию (3).
  • Прыгнуть через пропасть, когда значения координаты и скорости удовлетворяют условию (4).
  • Затормозить.

Программная реализация алгоритма:

Эффективность предложенного алгоритма:
Программа успешно проходит все четыре испытания. В процессе тестирования ни один робот не пострадал.

Технические детали реализации:
В коде использованы инструменты потокового ввода-вывода из заголовочного файла iostream и условные операторы.

Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

3 thoughts on “Skynet: The Chasm

  1. Принято. только если уже есть решения этой задачи, то нужно дать ссылку и обосновать почему важно рассмотреть ещё раз.
    Лучше избегать повторов, просто при необходимости писать комментарии и дополнения к уже имеющейся работе.

Добавить комментарий