思路与算法

用s表示每件商品的补贴，负s表示税金。成本为c，预期价为P，预期销量为C。若某竞争整数价q的销量为D(q)，必须满足C(P-c+s)≥D(q)(q-c+s)，即(C-D(q))s≥D(q)(q-c)-C(P-c)。系数为正给s的下界，为负给上界，系数为0则要直接检查常数项是否矛盾。把所有这些整数上下界求交，若空集就输出NO SOLUTION；否则区间含0取0，完全为正取下端，完全为负取上端。

不能逐个枚举价格，因为原题没有价格上界。把相邻已知价位之间的需求写成D(q)=A-Bq，B≥0。原题同时假设整数价格与整数销量，故一致的输入在线段覆盖的每个整数价位都给出整数销量。非整数斜率的两组端点会违反这个约定，不能擅自向下取整需求。

当B>0，令E=A-C-BP，边界函数为L(q)=[D(q)(q-c)-C(P-c)]/[C-D(q)]。整理得L(q)=c-q+C/B+CE/[B(C-A+Bq)]。除分母为0的点外，导数为-1-CE/(C-A+Bq)^2。因此E≥0时分段单调；E<0时只有C-A+Bq=±sqrt(C(-E))可能改变单调性。只需检查段端点、P±1，以及这两个驻点附近的整数。用精确整数平方根floor(sqrt(C(-E)))定位，不使用浮点；根值误差小于1，B为正整数，候选价误差小于1，向两侧各检查2个整数足够。分母为0时直接处理原始不等式，不做除法。B=0时边界至多是线性，检查端点即可。

最后一个价位之后使用输入的固定减少量。销量不可能为负，减至非正后按物理销量0处理；这是一条自然语义解释，不声称原文逐字给出了“截零”一词。若减少量为0且尾部销量正，则售价可无限提高而保持正销量，任何有限补贴都不能让有限目标价最优，直接NO SOLUTION；若尾部销量0，则是零销量平台。

正确性说明

原始利润比较不等式与变形后的一次不等式完全等价。正系数时必须向上取整得到整数下界，负系数时反向得到向下取整的整数上界；零系数矛盾则无任何s可行。所有竞争价约束的交集正是使P利润最大的全部整数补贴。绝对值函数在负区间向右递减、正区间向右递增，因此从最终区间选离0最近的端点或0就是所求。

在每个需求线段内部，分母符号只在D(q)=C处改变；该处原始比较已单独处理。其他位置的L是连续可微有理函数，导数的零点仅有上述至多两个，所以各单调片段的整数极值只可能出现在区间端点或包夹驻点的相邻整数。程序既检查端点和P邻域，也检查以精确平方根定位的驻点左右2个整数，覆盖所有这些极值，故约束缩减不遗漏任何整数价。

固定尾部减少量为正时，最后一个非负线性销量价位可用整数除法直接算出；之后所有价格销量0，利润恒0，只产生同一项目标利润≥0的约束，选一个代表价即可。目标销量为0时，也仍用同一原始不等式与全部正销量价位比较，不把0/0当成有效分式。减少量为0的两种尾部情形分别按无界利润和零平台直接证明。于是价格虽无上界，有限个精确候选已覆盖全部合法价格。

复杂度

设已知价位数K，输入整数、精确乘积、平方根及边界的最大十进制位数为L。排序O(K log K)次大整数比较；每段生成常数个候选，使用朴素多精度乘除法和按两位开平方，每次O(L²)量级，合计O(KL²+KL log K)时间。读取、排序和保存K个价位与分段使用O(KL)空间，临时大整数O(L)；没有按最高售价、销量、税金或补贴数值逐个循环的部分。初始化和全部分段构造已计入。

易错点

s为正是补贴、为负是税金；移项后除以负数必须反向。向0截断的整数除法不等于向下取整，尤其负界限要显式处理余数。目标价低于成本不能出售，直接NO SOLUTION。目标销量为0、平坦需求段、重复达到相同销量的不同价格和零减少量都需回到原始不等式判断。已知价格应按数值排序，不能按字符串排序。对相邻价位插值不默加取整规则；若资料与整数销量约定不一致，须补充原资料。全部构造数据为自编训练数据，非官方原始测试数据。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};

cpp_int fromString(string s) {
    cpp_int a;
    a.neg = !s.empty() && s[0] == '-';
    if (!s.empty() && (s[0] == '-' || s[0] == '+'))
        s.erase(s.begin());
    a.s = s;
    a.norm();
    return a;
}
cpp_int absBig(cpp_int a) {
    a.neg = false;
    return a;
}
cpp_int pow10(size_t n) {
    cpp_int a;
    a.s = "1" + string(n, '0');
    return a;
}
cpp_int operator*(const cpp_int &a, const cpp_int &b) {
    vector<long long> d(a.s.size() + b.s.size());
    for (int i = (int)a.s.size() - 1; i >= 0; --i)
        for (int j = (int)b.s.size() - 1; j >= 0; --j)
            d[i + j + 1] += (a.s[i] - '0') * (b.s[j] - '0');
    for (int i = (int)d.size() - 1; i > 0; --i) {
        d[i - 1] += d[i] / 10;
        d[i] %= 10;
    }
    cpp_int c;
    c.s.clear();
    for (auto x : d)
        c.s += char('0' + x);
    c.neg = a.neg != b.neg;
    c.norm();
    return c;
}
pair<cpp_int, cpp_int> divmod(cpp_int a, cpp_int b) {
    bool sign = a.neg != b.neg, negrem = a.neg;
    a.neg = b.neg = false;
    cpp_int q, rem;
    q.s.clear();
    cpp_int mul[10];
    for (int i = 0; i < 10; ++i)
        mul[i] = b * i;
    for (char z : a.s) {
        rem = rem * 10 + (z - '0');
        int lo = 0, hi = 9;
        while (lo < hi) {
            int mi = (lo + hi + 1) / 2;
            if (mul[mi] <= rem)
                lo = mi;
            else
                hi = mi - 1;
        }
        q.s += char('0' + lo);
        rem -= mul[lo];
    }
    q.neg = sign;
    q.norm();
    rem.neg = negrem;
    rem.norm();
    return {q, rem};
}
cpp_int floorDiv(cpp_int a, const cpp_int &b) {
    auto z = divmod(a, b);
    if (a.neg && z.second != 0)
        z.first -= 1;
    return z.first;
}
cpp_int rootBig(const cpp_int &a) {
    cpp_int root, rem;
    string s = a.s;
    if (s.size() % 2)
        s = "0" + s;
    for (size_t i = 0; i < s.size(); i += 2) {
        rem = rem * 100 + (s[i] - '0') * 10 + s[i + 1] - '0';
        int x = 9;
        while ((root * 20 + x) * x > rem)
            --x;
        rem -= (root * 20 + x) * x;
        root = root * 10 + x;
    }
    return root;
}
string fixedBig(cpp_int rounded, int digits) {
    bool neg = rounded.neg;
    string s = rounded.s;
    while (s.size() <= (size_t)digits)
        s = "0" + s;
    if (digits)
        s.insert(s.size() - digits, ".");
    return (neg ? "-" : "") + s;
}
cpp_int roundedRational(cpp_int a, cpp_int b) {
    bool neg = a.neg != b.neg;
    a.neg = b.neg = false;
    auto q = divmod(a, b);
    if (q.second * 2 >= b)
        q.first += 1;
    q.first.neg = neg && q.first != 0;
    return q.first;
}
struct Segment {
    cpp_int a, b, l, r;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cpp_int P, p, v, rate;
    cin >> P;
    vector<pair<cpp_int, cpp_int>> knots;
    while (cin >> p >> v) {
        if (p == -1 && v == -1)
            break;
        knots.push_back({p, v});
    }
    cin >> rate;
    sort(knots.begin(), knots.end(),
         [](const pair<cpp_int, cpp_int> &x, const pair<cpp_int, cpp_int> &y) {
             return x.first < y.first;
         });
    knots.erase(unique(knots.begin(), knots.end()), knots.end());
    cpp_int cost = knots[0].first;
    if (P < cost) {
        cout << "NO SOLUTION\n";
        return 0;
    }
    vector<Segment> seg;
    for (size_t i = 1; i < knots.size(); i++) {
        cpp_int l = knots[i - 1].first, r = knots[i].first;
        auto z = divmod(knots[i - 1].second - knots[i].second, r - l);
        assert(z.second == 0);
        cpp_int b = z.first;
        seg.push_back({knots[i - 1].second + b * l, b, l, r});
    }
    auto last = knots.back();
    assert(rate >= 0);
    if (rate == 0 && last.second > 0) {
        cout << "NO SOLUTION\n";
        return 0;
    }
    cpp_int R = last.first;
    if (rate > 0)
        R += floorDiv(last.second, rate);
    seg.push_back({last.second + rate * last.first, rate, last.first, R});
    cpp_int C = 0;
    for (auto x : seg)
        if (x.l <= P && P <= x.r)
            C = x.a - x.b * P;
    if (C < 0)
        C = 0;
    bool ok = true, hasLo = false, hasHi = false;
    cpp_int low, high;
    auto test = [&](cpp_int q, cpp_int D) {
        if (q == P)
            return;
        cpp_int den = C - D, num = D * (q - cost) - C * (P - cost);
        if (den == 0) {
            if (num > 0)
                ok = false;
            return;
        }
        if (den > 0) {
            cpp_int bound = -floorDiv(-num, den);
            if (!hasLo || low < bound) {
                low = bound;
                hasLo = true;
            }
        } else {
            cpp_int bound = floorDiv(-num, -den);
            if (!hasHi || bound < high) {
                high = bound;
                hasHi = true;
            }
        }
    };
    for (auto x : seg) {
        vector<cpp_int> candidate = {x.l, x.r, P - 1, P + 1};
        cpp_int E = x.a - C - x.b * P;
        if (x.b > 0 && E < 0) {
            cpp_int z = rootBig(C * (-E));
            for (int sign : {-1, 1}) {
                cpp_int q = floorDiv(x.a - C + z * sign, x.b);
                for (int d = -2; d <= 2; d++)
                    candidate.push_back(q + d);
            }
        }
        for (auto q : candidate)
            if (x.l <= q && q <= x.r)
                test(q, x.a - x.b * q);
    }
    test(max(P + 1, R + 1), 0);
    if (!ok || (hasLo && hasHi && low > high)) {
        cout << "NO SOLUTION\n";
        return 0;
    }
    if (hasLo && low > 0)
        cout << low;
    else if (hasHi && high < 0)
        cout << high;
    else
        cout << 0;
    cout << '\n';
}