LightOJ 1079 Solution

Just another Robbery  : Solution

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int t, k = 1;

    cin >> t;

    while(t--)

    {

        double probability;

        int n;

        cin >> probability >> n;

        probability = 1 - probability;

        double p[n];

        int sum = 0, money[n];

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

        {

            cin >> money[i] >> p[i];

            sum += money[i];

            p[i] = 1 - p[i];

        }

        double chance[sum+2];

        chance[0] = 1;

        for(int i=1; i<=sum; i++)

            chance[i] = 0;

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

        {

            for(int j=sum; j>=money[i]; j--)

            {

                double new_probability = chance[j - money[i]] * p[i];

                chance[j] = max(chance[j],new_probability);

            }

        }

        int i = sum;

        while(chance[i] < probability)

            i--;

        cout << "Case " << k++ << ": " << i << "\n";

    }

    return 0;

}