407008: GYM102680 C The Halting Problem

In the deterministic land of Babbalon, founded by Charles Babbage, of course, all cars have been replaced by fully-autonomous, Turing-complete driving machines. For safety reasons, the two driving machines will never be in the same intersection at the same time, and a machine will halt before an intersection if there is another machine in that intersection. Babbage, late to his afternoon meeting with Mrs. Lovelace, would like to know whether any of the driving machines will stop before going through an intersection.

If $$$n$$$ driving machines each take $$$s$$$ seconds to pass through an intersection, each one arriving at time $$$t_i$$$, will any machines have to stop before crossing the intersection?

The times the driving machines will arrive at the intersection will not necessarily be inputted in chronological order. A machine will not halt if it reaches the intersection at the exact same that time another leaves it.

The first line will contain a single integer $$$T$$$, the number of test cases

The first line of each test case will contain two integers, $$$n$$$ and $$$s$$$, the number of driving machines and the number of seconds it takes any driving machine to get through the intersection.

The following line contains $$$n$$$ integers, $$$t_i$$$, the time in seconds that the $$$i$$$th car arrives at the intersection

$$$0 \leq T \leq 40$$$

$$$0 \leq n, s \leq 100$$$

$$$0 \leq t_i \leq 1000$$$

Output $$$T$$$ lines, each containing either "YES" if at least one driving machine will have to halt, or "NO" otherwise.

2
3 3
1 4 10
2 5
4 0

NO
YES

For the first test case, driving machines will arrive at times 1, 4, and 10, and take 3 seconds to get through. No machine will have to wait for its turn, so we output "NO".

For the second test case, a driving machine that arrives at time 0 will occupy the intersection up to, but not including, time 5. When another driving machine arrives at time 4, it will have to wait, so we output "YES".