D - Dice Game
Time limit : 2sec / Memory limit : 256MB

Score : 1000 points

Problem Statement
There are two (6-sided) dice: a red die and a blue die. When a red die is rolled, it shows i with probability pi percents, and when a blue die is rolled, it shows j with probability qj percents.

Petr and tourist are playing the following game. Both players know the probabilistic distributions of the two dice. First, Petr chooses a die in his will (without showing it to tourist), rolls it, and tells tourist the number it shows. Then, tourist guesses the color of the chosen die. If he guesses the color correctly, tourist wins. Otherwise Petr wins.

If both players play optimally, what is the probability that tourist wins the game?

Constraints
0≤pi,qi≤100
p1+…+p6=q1+…+q6=100
All values in the input are integers.

#include <bits/stdc++.h>
using namespace std;

double p[10], q[10];

double cal(double mid) {
    double ans = 0;
    for (int i = 0; i < 6; i++)
        ans += max(p[i] * mid / 100, q[i] * (1 - mid) / 100);
    return ans;
}

int main() {
    for (int i = 0; i < 6; i++) scanf("%lf", &p[i]);
    for (int i = 0; i < 6; i++) scanf("%lf", &q[i]);
    double l = 0, r = 1;
    for (int i = 0; i < 100; i++) {
        double ml = (l * 2 + r) / 3;
        double mr = (l + r * 2) / 3;
        if (cal(ml) > cal(mr)) l = ml;
        else r = mr;
    }
    printf("%.12f\n", cal(l));
    return 0;
}