ZOJ Problem Set - 3411
Because of recent update of ZOJ, some special judges were broken. You're requested to fix the special judge for Problem 0000.
The norm of a vector v = (v1, v2, ... , vn) is define as norm(v) = |v1| + |v2| + ... + |vn|. And in Problem 0000, there are n cases, the standard output is recorded as a vector x = (x1, x2, ... , xn). The output of a submitted solution is also records as a vector y = (y1, y2, ... , yn). The submitted solution will be accepted if and only if norm(x - y) ≤ m (a given tolerance).
Knowing that all the output xi are in range [a, b], an incorrent solution that outputs integer yi in range [a, b] with equal probability may also get accepted. Given the standard output xi, you are supposed to calculate the possibility of getting accepted using such solution.
The input contains no more than 100 test cases. The first line of each case contains 4 integers n, m, a, b (1 ≤ n, m ≤ 50, -50 ≤ a < b ≤ 50), as described above. Then follows a line contains n integers, x1, x2, ... , xn (a ≤ xi ≤ b), indicating the standard output of the n cases.
Process to end of input.
For each case, output the possibility as a irreducible fraction of getting accepted using the incorrent solution in a single line.
1 1 0 2 1
Author: LI, Dinghua
Contest: ZOJ Monthly, October 2010