First, for each electoral district, we compute “how many voters should switch from Aoki to get the seats there?” It depends on the ordering between \(X_i\) and \(Y_i\):

• If \(X_i \gt Y_i\): Takahashi is already in majority, so \(0\) voters need to switch.
• If \(X_i \lt Y_i\): at least \(\frac{X_i + Y_i + 1}{2}\) pro-Takahashi voters are required to be the majority, so \(\frac{X_i + Y_i + 1}{2} - X_i = \frac{Y_i - X_i + 1}{2}\) voters need to switch.

Let \(W_i\) be these counts.

Also, let \(S = \sum_{i=1}^n Z_i\). With \(S\) and \(W_i\), this problem can be rephrased as follows:

There are \(N\) electoral districts.
In the \(i\)-th district, if \(W_i\) voters switch, \(Z_i\) seats can be obtained. How many voters must switch in order to get \(\frac{S+1}{2}\) or more seats?

This problem is in the same form as Knapsack problem, so it can be solved with a Dynamic Programming (DP) in the manner of Knapsack problem. Specifically, define a DP table \(\mathrm{dp}\) by:

• \(\mathrm{dp}[n]\) : the number of people that should switch to get exactly \(n\) voters (or \(\infty\) if there is no such way).

Procedurally, it is sufficient to process as follows:

• Let \(\mathrm{dp}\) be an array of length \((S+1)\). Initially, \(\mathrm{dp}[0] = 0\), and the other elements are initialized with \(\infty\).
• For each \(i=1, 2, \dots, N\) in this order, do the following:
  • For each \(n=S, S-1, \dots, Z_i\) in this order, do the following:
    • Let \(\mathrm{dp}[n]\) be \(\min(\mathrm{dp}[n], \mathrm{dp}[n-Z_i] + W_i)\).
• The answer to the problem is the minimum value among \(\mathrm{dp}[(S+1)/2], \mathrm{dp}[(S+1)/2 + 1], \dots, \mathrm{dp}[S]\) in the resulting DP table.

The complexity is \(\mathrm{O}(N \sum_{i=1}^N S_i)\), which is fast enough.

• Sample code (C++)

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
  long long inf = 1e18;

  int N;
  cin >> N;
  vector<int> X(N), Y(N), Z(N);
  for (int i = 0; i < N; i++) cin >> X[i] >> Y[i] >> Z[i];

  int z_sum = accumulate(begin(Z), end(Z), 0);
  vector<long long> dp(z_sum + 1, inf);
  dp[0] = 0;
  for (int i = 0; i < N; i++) {
    int x = X[i], y = Y[i], z = Z[i];
    int w = max(0, (x + y) / 2 + 1 - x);
    for (int j = z_sum; j >= z; j--) {
      dp[j] = min(dp[j], dp[j - z] + w);
    }
  }

  long long ans = inf;
  for (int j = z_sum / 2 + 1; j <= z_sum; j++) ans = min(ans, dp[j]);
  cout << ans << endl;
}