codeforcesRound#258(div2)C解题报告_html/css_WEB-ITnose

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了codeforcesRound#258(div2)C解题报告_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4028字，纯文字阅读大概需要6分钟。

内容图文

time limit per test

memory limit per test

input

output

There are n games in a football tournament. Three teams are participating in it. Currently k games had already been played.

You are an avid football fan, but recently you missed the whole k games. Fortunately, you remember a guess of your friend for these kgames. Your friend did not tell exact number of wins of each team, instead he thought that absolute difference between number of wins of first and second team will be d1 and that of between second and third team will be d2.

You don't want any of team win the tournament, that is each team should have the same number of wins after n games. That's why you want to know: does there exist a valid tournament satisfying the friend's guess such that no team will win this tournament?

Note that outcome of a match can not be a draw, it has to be either win or loss.

Input

The first line of the input contains a single integer corresponding to number of test cases t (1?≤?t?≤?105).

Each of the next t lines will contain four space-separated integers n,?k,?d1,?d2 (1?≤?n?≤?1012; 0?≤?k?≤?n; 0?≤?d1,?d2?≤?k) ? data for the current test case.

Output

For each test case, output a single line containing either "yes" if it is possible to have no winner of tournament, or "no" otherwise (without quotes).

Sample test(s)

input

53 0 0 03 3 0 06 4 1 06 3 3 03 3 3 2

output

yesyesyesnono

Note

Sample 1. There has not been any match up to now (k?=?0,?d1?=?0,?d2?=?0). If there will be three matches (1-2, 2-3, 3-1) and each team wins once, then at the end each team will have 1 win.

Sample 2. You missed all the games (k?=?3). As d1?=?0 and d2?=?0, and there is a way to play three games with no winner of tournament (described in the previous sample), the answer is "yes".

Sample 3. You missed 4 matches, and d1?=?1,?d2?=?0. These four matches can be: 1-2 (win 2), 1-3 (win 3), 1-2 (win 1), 1-3 (win 1). Currently the first team has 2 wins, the second team has 1 win, the third team has 1 win. Two remaining matches can be: 1-2 (win 2), 1-3 (win 3). In the end all the teams have equal number of wins (2 wins).

题目大意：

有n场比赛，你错过了k场，然后再错过的k长中，一队与二队的胜利差值为d1，二队与三队的胜利差值为d2。如若有可能，三支队伍获胜次数都一样，则输出yes，否则输出no

解法：

比较有趣且复杂的模拟题，我们可以想象成三个柱子，已知第一个柱子跟第二个柱子的高度差的绝对值，第二个柱子跟第三个柱子高度差的绝对值，现在还有n-k个砖（1高度），要求使得三个柱子高度一样。

首先，给了d1和d2，我们可以枚举一下有那几种基本情况：

1. d1, 0, d2;

2. 0, d1, d1+d2;

3. 0, d2, d1+d2;

4. 0, d1, d1-d2;

5. 0, d2, d2-d1;

其中4和5这两种情况，取决于d1-d2是否为正数，其实两种是一种情况=_=#。

然后，根据这5种情况，对于每一种情况，x，y，z都必须 >= 0，且 x + y + z <= k && (k - x - y - z) % 3 == 0。 这里我们是为了保证我们枚举的情况是否符合基本要求：三个队伍的比赛次数为k。

接下来，我们需要保证的是，(n-k)%3 == 0 && n/3 >= x, y, z)。

代码：

#include #include #define LL long longusing namespace std;LL n, k, d1, d2;bool check(LL x, LL y, LL z) {	if (x < 0 || y < 0 || z < 0)  return false;	if (x + y + z > k)  return false;	if ((k-(x+y+z))%3 != 0)  return false;	LL tmp = x+y+z+(n-k);	LL dv = tmp/3;	LL md = tmp%3;	if (md == 0 && x <= dv && y <= dv && z <= dv)		return true;	else		return false;}void solve() {	cin >> n >> k >> d1 >> d2;	if (check(d1, 0, d2))		printf("yes\n");	else if (check(0, d1, d1+d2))		printf("yes\n");	else if (check(0, d2, d1+d2))		printf("yes\n");	else if (check(0, d1, d1-d2))		printf("yes\n");	else if (check(0, d2, d2-d1))		printf("yes\n");	else		printf("no\n");}int main() {	int tcase;	cin >> tcase;	while (tcase--) {		solve();	}}

内容总结

以上是互联网集市为您收集整理的codeforcesRound#258(div2)C解题报告_html/css_WEB-ITnose全部内容，希望文章能够帮你解决codeforcesRound#258(div2)C解题报告_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端