SRM544 Div1 Easy(275) ElectionFraudDiv1

ElectionFraudDiv1

有権者数を決めて、それぞれの候補者の最小と最大の票数を足し合わせて、有権者数がその間にあれば良い。証明は分からないけど、答えは高々201らしい。票数は負にならないことに注意。

#include <vector>
using namespace std;

class ElectionFraudDiv1{public:
int MinimumVoters( vector <int> percentages )
{
    int n = (int)percentages.size();

    for ( int X=1; X<1000; X++ )
    {
        int minx = 0;
        int maxx = 0;

        for ( int i=0; i<n; i++ )
        {
            minx += max(0,((10*percentages[i]-5)*X+999)/1000);
            maxx += ((10*percentages[i]+5)*X+999)/1000-1;
        }
        if ( minx<=X && X<=maxx )
            return X;
    }

    return -1;
}};