Матч
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;
}
};