[Codeforces 1244C] The Football Season(扩展欧几里得)
原标题:[Codeforces 1244C] The Football Season(扩展欧几里得)
原文来自:CSDN 原文链接:https://blog.csdn.net/qq_33831360/article/details/102537512
xw+yd=p,x+y+z=n求x,y,z
首先尽量让他赢p/w次,剩下m=p%w分,剩下的分给平,m/d个平,为什么不先分给平呢?w比较大,所以这样x+y比较小,不容易让z<0。
可是m%d不一定是0,这时候要调整,+-w,+-d能怎么调呢?就要用到扩展欧几里得算法了,aw+bd=gcd(w,d),求出a,b,gcd.如果m%d%gcd不是0,那么无解,+-w,d调整的最小单位就是gcd。否则加上a*(m%d/gcd)个w和b*(m%d/gcd)个d,使得和为p。
还要注意,增加b/gcd个w同时减少w/gcd个d和是不变的,在胜利次数<0时可以这么调整。
#include <iostream> #include <queue> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; void exgcd(LL a, LL b, LL& x, LL& y, LL& c) { if(!b) {y = 0; x = 1; c = a; return;} exgcd(b,a%b,y,x,c); y -= a/b*x; } int main() { LL n,p,w,d; cin >> n >> p >> w >> d; // wx+dy = gcd w,d LL x,y,c; exgcd(w,d,x,y,c); LL v1 = p/w,v2 = 0,m = p%w; v2 = m/d; m = m%d; //cout << x << " " <<y<<"n"; if (m%c == 0) { LL t = m/c; v1 += t*x; v2 += t*y; LL t1 = w/c,t2 = d/c; // +t1 -t2 while (v1 < 0) { v1 += t2; v2 -= t1; if (v2 < 0) { puts("-1"); return 0; } } while (v2 < 0) { v1 -= t2; v2 += t1; if (v1 < 0) { puts("-1"); return 0; } } while (n-v1-v2 < 0) { if (t1 > t2) { v1 += t2; v2 -= t1; if (v2 < 0) { puts("-1"); return 0; } } else if (t1 < t2) { v1 -= t2; v2 += t1; if (v1 < 0) { puts("-1"); return 0; } } else { puts("-1"); return 0; } } if (v1>=0 && v2>=0 && n-v1-v2>=0) { cout << v1 << " " << v2 << " " << n-v1-v2 << "n"; return 0; } } puts("-1"); return 0; }
The football season has just ended in Berland. According to the rules of Berland football, each match is played between two teams. The result of each match is either a draw, or a victory of one of the playing teams. If a team wins the match, it gets ww points, and the opposing team gets 00 points. If the game results in a draw, both teams get dd points.
The manager of the Berland capital team wants to summarize the results of the season, but, unfortunately, all information about the results of each match is lost. The manager only knows that the team has played nn games and got pp points for them.
You have to determine three integers xx, yy and zz — the number of wins, draws and loses of the team. If there are multiple answers, print any of them. If there is no suitable triple (x,y,z)(x,y,z), report about it.
Input
The first line contains four integers nn, pp, ww and dd (1≤n≤1012,0≤p≤1017,1≤d<w≤105)(1≤n≤1012,0≤p≤1017,1≤d<w≤105) — the number of games, the number of points the team got, the number of points awarded for winning a match, and the number of points awarded for a draw, respectively. Note that w>dw>d, so the number of points awarded for winning is strictly greater than the number of points awarded for draw.
Output
If there is no answer, print −1−1.
Otherwise print three non-negative integers xx, yy and zz — the number of wins, draws and losses of the team. If there are multiple possible triples (x,y,z)(x,y,z), print any of them. The numbers should meet the following conditions:
x⋅w+y⋅d=px⋅w+y⋅d=p,
x+y+z=nx+y+z=n.
Examples
input
Copy
30 60 3 1output
Copy
17 9 4input
Copy
10 51 5 4output
Copy
-1input
Copy
20 0 15 5output
Copy
0 0 20Note
One of the possible answers in the first example — 1717 wins, 99 draws and 44 losses. Then the team got 17⋅3+9⋅1=6017⋅3+9⋅1=60 points in 17+9+4=3017+9+4=30 games.
In the second example the maximum possible score is 10⋅5=5010⋅5=50. Since p=51p=51, there is no answer.
In the third example the team got 00 points, so all 2020 games were lost.
免责声明:本文来自互联网新闻客户端自媒体,不代表本网的观点和立场。
合作及投稿邮箱:E-mail:editor@tusaishared.com
热门资源
Python 爬虫(二)...
所谓爬虫就是模拟客户端发送网络请求,获取网络响...
TensorFlow从1到2...
原文第四篇中,我们介绍了官方的入门案例MNIST,功...
TensorFlow从1到2...
“回归”这个词,既是Regression算法的名称,也代表...
机器学习中的熵、...
熵 (entropy) 这一词最初来源于热力学。1948年,克...
TensorFlow2.0(10...
前面的博客中我们说过,在加载数据和预处理数据时...
智能在线
400-630-6780
聆听.建议反馈
E-mail: support@tusaishared.com