Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <set>
- using namespace std;
- int knapsack(vector<int> weights, vector<int> profits, int target){
- vector<int> w;
- vector<int> p;
- w = weights;
- p = profits;
- vector<vector<pair<int, int>>> dp;
- int n = w.size() - 1; // Number of items
- int totalDelegsUpForContest = 0;
- for (int i = 0; i < weights.size(); i++){
- totalDelegsUpForContest += w[i];
- }
- int c = totalDelegsUpForContest; // Number of delegates up for contest
- dp.resize(n+1, vector<pair<int, int>>(c+1, {1000000000, 100000000}));
- dp[0][0] = {0,0};
- // Tabulate
- for (int i = 1; i < n + 1; i++){
- for (int j = 1; j < c + 1; j++){
- if (j - w[i] < 0){
- dp[i][j].first = dp[i-1][j].first;
- dp[i][j].second = dp[i-1][j].second;
- }
- else{
- dp[i][j].first = min(dp[i-1][j].first, dp[i-1][j-w[i]].first + p[i]);
- if (dp[i-1][j].first > dp[i-1][j-w[i]].first + p[i]){
- dp[i][j].second += dp[i-1][j].second;
- }
- else {
- dp[i][j].second += dp[i-1][j-w[i]].second + w[i];
- }
- }
- }
- }
- /**
- for (auto row : dp){
- for (auto elem : row){
- cout << "{ " << elem.first << ", " << elem.second << "} ";
- }
- cout << "\n";
- }
- **/
- // Linear search in the proper area of the table for the pairs
- set<pair<int, int>> valid;
- for (int i = 0; i < n + 1; i++){
- for (int j = target; j < c + 1; j++){
- if (dp[i][j].second >= target){
- valid.insert(dp[i][j]);
- }
- }
- }
- // Return first item in the ordered set's minimum number of voters
- return (*valid.begin()).first;
- }
- int main()
- {
- int s, di, ci, fi, ui;
- cin >> s;
- // Stores stateNum : [di, ci, fi, ui]
- map<int, vector<int>> m;
- // Vector of pairs ({State Number, Number of Delegates})
- vector<pair<int, int>> S;
- int delegsToF = 0;
- int delegsToC = 0;
- int totalDelegs = 0;
- bool end = false;
- for (int i = 0; i < s; i++){
- cin >> di >> ci >> fi >> ui;
- totalDelegs += di;
- vector<int> stateDataVec {di, ci, fi, ui};
- m.insert({i, stateDataVec});
- // Get the only undecided voters that matter into S
- if (fi + ui < ci){
- delegsToC += di;
- }
- else if (ci + ui <= fi){
- delegsToF += di;
- }
- else{
- S.push_back({i, di});
- }
- }
- if (S.empty() && delegsToC <= delegsToF){
- cout << "impossible" << endl;
- end = true;
- }
- else if (S.empty() && delegsToC > delegsToF){
- cout << 0 << endl;
- end = true;
- }
- // Calculate sum of delegates Ci can get
- int posDelegsC = 0;
- for (auto i : S){
- posDelegsC += i.second;
- }
- // If number of delegates F has already won is greater than
- // number of delegates C has already won and delegates in contest
- // then it is impossible to win
- if ( (delegsToF >= (delegsToC + posDelegsC)) and !end){
- cout << "impossible" << endl;
- end = true;
- }
- // Find minimum voters required such that delegSum (number of delegates to C)
- // is greater than the majority
- if (!end){
- // Create profit and weight arrays
- vector<int> weights;
- vector<int> profits;
- weights.push_back(0);
- profits.push_back(0);
- for (int i = 0; i < S.size(); i++){
- weights.push_back(S[i].second);
- // Calculate min_ui
- int stateNum = S[i].first;
- vector<int> stateData = m[stateNum];
- int totalVotersInState = stateData[1] + stateData[2] + stateData[3];
- int min_ui = (totalVotersInState / 2) + 1 - stateData[1];
- profits.push_back(min_ui);
- }
- // Calculate target
- // Target to hit should be the total delegates / 2 + 1 - delegsToC
- int target = totalDelegs/2 + 1 - delegsToC;
- int ans = knapsack(weights, profits, target);
- cout << ans;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment