CF1244C足球赛季的数学思维题有哪些解题方法？

本文共计918个文字，预计阅读时间需要4分钟。

在线评测系统：Luogu，Codeforces 赛事

Online Judge：Luogu，Codeforces Round #592 (Div. 2) C

Label：数学，思维题， 枚举

题目描述

某球队一共打了\(n\)场比赛，总得分为\(p\)，已知赢一场得\(w\)分，平局一场得\(d\)分，输一场不加分也不减分，问一共赢了几场(x)，平局了几场(y)，输了几场(z)？如果不存在合法方案输出"-1"，如果存在多组可能的方案，任意输出一组(Special Judge)。

也就是任求一组符合条件的非负整数三元组\((x,y,z)\)，满足:
\[ x\cdot w+y\cdot d=p \x+y+z=n \]

输入

四个整数\(n,p,w,d\)。

输出

输出三个整数表示符合条件的三元组，如果不存在，则输出"-1"。

样例

Input#1

30 60 3 1

Output#1

17 9 4

Input#2

10 51 5 4

Output#2

-1

Input#3

20 0 15 5

Output#3

0 0 20

Hint

\(1<=n<=10^{12}\)，\(0<=p<=10^{17}\)，\(1<=d<w<=10^{15}\)。

注意，题目数据保证了\(d<w\)，也就是赢一场的得分严格大于平局一场的得分。

题解

一开始看题，直接打了个exgcd去解不定方程最小解，结果好像中间会爆long long 就WA掉了。其实仔细读题，根本根本不需要这样搞。

现在需要解一个这样的方程组
\[ x+y+z=n....①\x\cdot w+y\cdot d=p....②\\]
①式可以转化为\(x+y<=n\)，\(z\)的大小再根据\(x,y\)具体调整即可。

假设存在一组二元组\((x,y)\)，已经能够满足②式了，现在考虑再构造一组解，使得\(x+y\)尽量小，能满足①式。

则有
\[ x\cdot w+w\cdot d-w\cdot d+y\cdot d=p\\→(x+d)\cdot w+(y-w)\cdot d=p\\]
也就是说必然还存在一组满足②式的解\((x+d,y-w)\)，多次进行这样的操作，可以得到\((x+2d,y-2w)\)，\((x+3d,y-3w)\)，......，由于需要满足\(x>0,y>0,z>0\)，必然有一个下限使得此时的\(y'<w\)，减不动了，可以证明此时的这组解一定是最优的（也就是此时的\(x'+y'\)最小）。为什么呢，由于题目强调了\(w>d\)，也就是\(x->x'\)的增量小于\(y->y'\)减量，所以此时的\(x'+y'\)一定最小。

所以只用枚举\(y∈[0,w-1]\)即可，然后分别带入计算得到此时的\(x\)，再判一下\(x+y<=n\)这个条件，如果这个范围内都没有满足条件的解，\(y\)再往大枚举也不可能出现满足条件的解了。

综上时间复杂度为\(O(W)\)，\(W<=10^5\)。

#include <bits/stdc++.h> using namespace std; #define int long long typedef long long ll; ll n,p,w,d; signed main(){ cin>>n>>p>>w>>d; for(int y=0;y<w;y++){ int left=p-y*d; if(left%w)continue; int x=left/w; if(x>=0&&x+y<=n){ printf("%lld %lld %lld\n",x,y,n-x-y); return 0; } } puts("-1"); }