範例程式碼 uva13242

//uva13242
#include <cmath>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

int main() {
    int kase;
    cin >> kase;
    while (kase--) {
        int pool, target;
        cin >> pool >> target;
        int n;
        cin >> n;
        vector<pair<int, int>> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i].first >> v[i].second;
        }

        vector<int> preVol(n + 1, 0);
        vector<long long> preTep(n + 1, 0);
        for (int i = 0; i < n; i++) {
            preVol[i + 1] = preVol[i] + v[i].first;
            preTep[i + 1] = preTep[i] + (long long)v[i].first * v[i].second;
        }

        int bestI = -1, bestJ = -1;
        long long bestDiff = 0;
        int bestVol = 0;
        bool found = false;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int volume = preVol[j + 1] - preVol[i];
                if (volume > pool)
                    break;
                if (volume < (pool + 1) / 2)
                    continue;

                long long hotSum = preTep[j + 1] - preTep[i];
                long long targetSum = (long long)target * volume;
                long long diff = abs(hotSum - targetSum);
                if (diff > 5 * volume)
                    continue;
                if (!found) {
                    bestI = i;
                    bestJ = j;
                    bestDiff = diff;
                    bestVol = volume;
                    found = true;
                } else {
                    if (diff * bestVol < bestDiff * volume) {
                        bestI = i;
                        bestJ = j;
                        bestDiff = diff;
                        bestVol = volume;
                    } else if (diff * bestVol == bestDiff * volume) {
                        if (i < bestI || (i == bestI && j < bestJ)) {
                            bestI = i;
                            bestJ = j;
                            bestDiff = diff;
                            bestVol = volume;
                        }
                    }
                }
            }
        }
        
        if (found)
            cout << bestI << " " << bestJ << "\n";
        else
            cout << "Not possible" << "\n";
    }
    return 0;
}