04
Дек
2017

Олимпиадная задача на вероятность

Есть проблема с одной олимпиадной задачей, но решить мне её нужно на 100. Задача находится https://www.e-olymp.com/ru/problems/7272 по этому адресу. Задачу решить нужно на любом языке программирования. Моё решение проходит лишь на 81%. Условие задачи состоит в следующем:

Вася попал в серьёзную передрягу. Он задолжал мафии N долларов, и время расплаты почти подошло. Вася хорошо знает, чем грозит несвоевременный возврат долга, поэтому он хочет собрать N долларов любой ценой.

Однако, на данный момент у него есть только M долларов. Приятель, который узнал о проблемах Васи, предложил Васе игру — в этот раз на деньги. У Васи есть K попыток сделать ставку на любую сумму от нуля до той суммы, которая у него есть — не обязательно даже целую. С вероятностью P % Вася получает ставку в двойном объёме, иначе не получает ничего. Васе не важно, сколько денег у него останется в итоге, главное, чтобы было N долларов, чтобы расплатиться. Вася, конечно же, играет оптимально. Узнайте, с какой вероятностью ему повезёт и он расплатится деньгами.

Есть чувство, что я не учитываю какую-то очень важную особенность

Вот код, которым я пытался решать:

#include "iostream"
#include "stdio.h"

using namespace std;

int main()
{
    long int dolg;
    long int deng;
    long int popitki;
    double chance;
    cin >> dolg >> deng >> popitki >> chance;
    chance *= 0.01;
    double chance_now = chance;

    double answer = 0;
    double left, right, middle;
    left = 0;
    right = dolg;
    middle = dolg / 2;

    if (dolg > deng)
    {
        while (popitki > 0)
        {
            if (deng < middle)
            {
                chance_now *= chance;
                right = middle;
                middle = (right + left) / 2;
            }
            else
            {
                answer += chance_now;
                chance_now *= (1 - chance);
                left = middle;
                middle = (right + left) / 2;
            }
            popitki--;
        }
    }
    else
        answer = 1;
    printf("%f\n", answer);
    return 0;
}

Источник: https://ru.stackoverflow.com/questions/753557/%D0%9E%D0%BB%D0%B8%D0%BC%D0%BF%D0%B8%D0%B0%D0%B4%D0%BD%D0%B0%D1%8F-%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0-%D0%BD%D0%B0-%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C

Тебе может это понравится...

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