Матч 19, Бросание стрел (DartThrow)

 

По кругу расположены цели, в которые Вы стараетесь попасть стрелами. Вероятность попадания стрелы в цель в процентах равна prob. Если стрела не попадает в заданную цель, то она обязательно попадет в одну из соседних целей с одинаковой вероятностью. Например, если Вы целились и не попали в цель с номером 0, то попадание имело место либо в цель 1, либо в цель n – 1 (n равно количеству целей в круге, цели нумеруются с 0 до n – 1). Элемент payout[i] содержит размер выплаты, которую Вы получаете в случае поражения i - ой цели. Определить среднюю сумму выплаты, которую можно получить при оптимальной игре.

 

Класс: DartThrow

Метод: double bestScore(vector<int> payout, int prob)

Ограничения: payout содержит от 3 до 50 элементов, 0 £ payout[i] £ 100, 0 £ prob £ 100.

 

Вход. Массив выплат payout и вероятность попадания prob.

 

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

 

Пример входа

payout

prob

{10,40,50}

80

{20,1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5}

20

{16,99,96,26,71,9,89,43,11,41,58,84,27,8,17,54,26,36,87}

66

 

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

45.0

15.4

84.61

 

 

РЕШЕНИЕ

вероятность

 

Если 0.01 * prob – вероятность попадания в i - ую цель, то вероятность попадания в соседние цели одинакова и равна (1 – 0.01 * prob) / 2. При бросании стрелы в i - ую цель средняя сумма выплаты равна

0.01 * prob * payout[i] + (1 – 0.01 * prob) / 2 * (payout[(i – 1 + n) % n] + payout[(i + 1) % n]

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

 

ПРОГРАММА

 

#include <cstdio>

#include <vector>

using namespace std;

 

class DartThrow

{

  public:

  double bestScore(vector <int> payout, int prob)

  {

    int i,n=payout.size();

    double s,res = 0;

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

    {

      s = 0.01*prob*payout[i] + (1-0.01*prob)/2*(payout[(i-1+n)%n] +

          payout[(i+1)%n]);

      if (s > res) res = s;

    }

    return res;

  }

};