|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||256 MB||13||7||7||53.846%|
Knowledge of the game Risk is not necessary to solve this problem. All dice in this problem are six sided dice.
The game of Rizk is a Bulgarian variant of Risk. It is a game played between two players, each with their own army. Every time it’s your turn, you can choose to either attack or add more units to your army, but not both. An attack is played in the following way:
Let’s say player A is attacking, and has Ua units, and player B is defending, and has Ub units. The attacker has access to Da dice, and the defender has access to Dd dice. The attack consists of the following steps:
The winner of the battle is the player with units remaining at the end. Note that there will always be exactly one player with units remaining at the end.
Mike and his brother has been playing for hours. None of them dare to attack, because they fear to lose. It’s Mike’s turn, and he has decided to cheat a little bit in order to win. He has decided that he wants to attack if he has at least 75% chance of winning this turn. Mike has X units, and his brother has Y units. How many units does he have to sneak into the game in order to have at least 75% chance of winning this turn?
The first line of the input consists of a single integer, T, the number of test cases. Each test case consists of 4 integers, Da, Dd, X and Y , as explained in the problem statement.
For each test case, output the minimum number of additional units needed to have at least 75% chance of winning.
4 4 3 10 10 1 1 10 10 4 1 100 1 1 4 2 3
5 8 0 11