[CF1244C] The Football Season

Description

有 (n) 场比赛，共 (p) 分，胜利一场得 (win) 分，平局一场得 (draw) 分，输一场得 (0) 分。给定 (n,p,win,draw (win,draw le 10^5))，构造合法的胜平负场次数量 (x,y,z) 或者判定无解。

Solution

显然我们要求满足 (x+y le n, wincdot x + draw cdot y = p) 的最小的 (x+y) 的非负的 (x,y)。

先考虑求出任意一组可行解。由于 (win le 10^5)，因此 (0 le y < win) 中一定有一个满足条件的 (y)，因此我们只需要暴力枚举 (y) 就可以找到一个可行的 (y)。

现在假设已经得到的可行解为 (x',y')，我们考虑如何让 (x+y) 最小化。

设 (g= ext{gcd}(win,draw))，则 (y+win/g, x-draw/g) 即可找到一组新的可行解，此时 (x+y) 的变化量为 (win/g - draw/g)。

如果这个值 (>0)，那么我们就操作 (frac {x} {draw/g}) 次，这时 (x+y) 达到最小。

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n, p, win, draw;

    cin >> n >> p >> win >> draw;

    int x, y = 0;
    while (y < win && !(p >= y * draw && (p - y * draw) % win == 0))
        ++y;

    x = (p - y * draw) / win;

    if (x < 0)
    {
        cout << -1 << endl;
        return;
    }
    int g = __gcd(win, draw);

    int t = y / (win / g);

    x += (draw / g) * t;
    y -= (win / g) * t;

    int z = n - x - y;

    if (z < 0 || x * win + y * draw != p)
    {
        cout << -1 << endl;
        return;
    }

    cout << x << " " << y << " " << z << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    solve();
}