A9479. Predict Outcome of the Game
编程题
普及/提高-
知识点
题目描述
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 $k$ games. 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 $d_{1}$ and that of between second and third team will be $d_{2}$ .
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.
You are an avid football fan, but recently you missed the whole $k$ games. Fortunately, you remember a guess of your friend for these $k$ games. 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 $d_{1}$ and that of between second and third team will be $d_{2}$ .
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.
输入格式
The first line of the input contains a single integer corresponding to number of test cases $t$ $(1<=t<=10^{5})$ .
Each of the next $t$ lines will contain four space-separated integers $n,k,d_{1},d_{2}$ $(1<=n<=10^{12}; 0<=k<=n; 0<=d_{1},d_{2}<=k)$ — data for the current test case.
Each of the next $t$ lines will contain four space-separated integers $n,k,d_{1},d_{2}$ $(1<=n<=10^{12}; 0<=k<=n; 0<=d_{1},d_{2}<=k)$ — data for the current test case.
输出格式
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).
输入输出样例
输入 #1
5 3 0 0 0 3 3 0 0 6 4 1 0 6 3 3 0 3 3 3 2
输出 #1
yes yes yes no no
说明/提示
Sample 1. There has not been any match up to now $(k=0,d_{1}=0,d_{2}=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 $d_{1}=0$ and $d_{2}=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 $d_{1}=1,d_{2}=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).
Sample 2. You missed all the games $(k=3)$ . As $d_{1}=0$ and $d_{2}=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 $d_{1}=1,d_{2}=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).