Матч 353, Прыгатель по платформам (PlatformJumper)

Дивизион 2, Уровень 3; Дивизион 1, Уровень 2

 

В старой аркадной игре Вы попали на бонусный уровень. Имеется набор платформ, на которых находятся монеты. Вы должны прыгать с одной платформы на другую, собирая деньги. С каждой платформы можно прыгать только на платформу, находящуюся ниже. Начальной можно выбрать любую платформу.

Опишем поведение игрока при прыжках. При каждом прыжке горизонтальная составляющая скорости является константой, не превышающей v. Движение вниз происходит по законам физики: ускорение свободного падения равно g. Начальная скорость игрока равна 0.

Каждая платформа является точкой и имеет формат “X Y C”, где X и Y – координаты платформы, а C – количество монет на ней. Большие значения координаты Y имеют платформы, находящиеся выше. Определить наибольшее количество монет, которое может собрать игрок.

 

Класс: PlatformJumper

Метод: int maxCoins(vector<string> platforms, int v, int g)

Ограничения: platforms содержит от 1 до 50 элементов, platforms[i] имеет формат “X Y C”,  0 £ X, Y £ 5000, 0 £ C £ 10000, 1 £ g, v £ 100.

 

Вход. Информация о платформах platforms, наибольшая возможная горизонтальная составляющая скорости игрока v и ускорение свободного падения g.

 

Выход. Наибольшее количество монет, которое может собрать игрок.

 

Пример входа

platforms

v

g

{"3 10 7", "5 15 7", "8 9 12" }

2

10

{"0 0 1", "2 4 1", "4 0 1"}

1

2

{"0 0 1", "5000 5000 10"}

100

87

 

Пример выхода

14

2

10

 

 

РЕШЕНИЕ

динамическое программирование

 

Поскольку игрок при прыжках всегда движется вниз, то его путь всегда конечный, а каждая платформа может быть посещена не более одного раза. Пусть opt[i] содержит наибольшее количество монет, которое можно собрать по всем путям, заканчивающихся на i - ой платформе. Обозначим через s[i] множество платформ, с каждой из которых за один прыжок можно попасть на i - ую платформу. Пусть coins[i] – количество монет, находящихся на i - ой платформе. Тогда имеет место рекуррентность:

opt[i] = coins[i] +

Остается научиться определять, можно ли прыгнуть из одной платформы на другую. Пусть платформы имеют координаты (x1, y1) и (x2, y2), y1 > y2. Игрок должен преодолеть по горизонтали расстояние |x1 – x2|, по вертикали |y1 – y2|. Наибольшая горизонтальная скорость движения при прыжке равна v, которая по условию задачи постоянна. Тогда время, за которое может быть преодолена горизонтальная составляющая, равно t = |x1 – x2| /  v. Вычислим расстояние, на которое переместится за это время игрок по оси ординат. Оно равно

dy = g * t2 / 2

Если dy > |y1 – y2|, то прыжок совершить невозможно. Перепишем последнее неравенство в виде:

g * |x1 – x2|2 /  2v2 > |y1 – y2|,

или для избежания операции деления:

g * |x1 – x2|2 > |y1 – y2| * 2v2

Отсортируем платформы по y - координате. Последовательно, начиная с наивысшей платформы, вычисляем значения массива opt согласно выше приведенной рекуррентной формуле. В переменной res накапливаем ответ – он равен наибольшему значений среди всех ячеек массива opt.

 

 

ПРОГРАММА

 

#include <cstdio>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

 

struct pos

{

  long long x, y, coins;

} c[50];

 

int f(pos a, pos b)

{

  return a.y < b.y;

}

 

class PlatformJumper

{

public:

  int maxCoins(vector<string> platforms, int v, int g)

  {

    int i, j, res, n = platforms.size(), opt[50];

    for(res = i = 0; i < n; i++)

      sscanf(platforms[i].c_str(),"%lld %lld %lld",

                                  &c[i].x,&c[i].y,&c[i].coins);

    sort(c,c+n,f);

    for(i = n - 1; i >= 0; i--)

    {

      opt[i] = c[i].coins;

      for(j = i + 1; j < n; j++)

        if ((opt[j] + c[i].coins > opt[i]) &&

           (g * (c[i].x - c[j].x) * (c[i].x - c[j].x) <=

                      (c[j].y - c[i].y) * 2 * v * v))

             opt[i] = opt[j] + c[i].coins;

        if (opt[i] > res) res = opt[i];

    }

    return res;

  }

};