According to Wikipedia, a Walsh matrix is a specific square matrix, with dimensions equal to a power of 2, the entries of which are +1 or -1, and the property that the dot product of any two distinct rows (or columns) is zero. Below are the first three Walsh Matrices. (The gray lines are imaginary lines for illustration purpose only.)
A Walsh Matrix of size 2N+1
W2N+1 =
SRC="/ntujudge/problemdata/705-7.png"
ALT="$\displaystyle \left[\vphantom{\begin{array}{r\vert r}
W_{2^N} & W_{2^N} \\ \hline W_{2^N} & -W_{2^N} \\ \end{array} }\right.$">
SRC="/ntujudge/problemdata/705-8.png"
ALT="$\displaystyle \begin{array}{r\vert r}
W_{2^N} & W_{2^N} \\ \hline W_{2^N} & -W_{2^N} \\ \end{array}$">
SRC="/ntujudge/problemdata/705-9.png"
ALT="$\displaystyle \left.\vphantom{\begin{array}{r\vert r}
W_{2^N} & W_{2^N} \\ \hline W_{2^N} & -W_{2^N} \\ \end{array} }\right]$">
Let's number the rows of a given Walsh Matrix from the top starting with row 0. Similarly, let's number the columns of the matrix from the left starting with column 0. Given the four integers N
Your program will be tested on one or more test cases. Each test case is specified using a single line listing four integers in the following order: N
$0 \le N \le 60$
-->
0
SRC="/ntujudge/problemdata/705-10.png"
ALT="$ \le$">N
SRC="/ntujudge/problemdata/705-10.png"
ALT="$ \le$">60
$0 \le R < 2N$
-->
0
SRC="/ntujudge/problemdata/705-10.png"
ALT="$ \le$">R < 2N
$0 \le S \le E < 2N$
-->
0
SRC="/ntujudge/problemdata/705-10.png"
ALT="$ \le$">S
SRC="/ntujudge/problemdata/705-10.png"
ALT="$ \le$">E < 2N
$E - S \le 10, 000$
-->
E - S
SRC="/ntujudge/problemdata/705-10.png"
ALT="$ \le$">10, 000
For each test case, print the output on a single line.
2 1 0 1
48 0 0 47
-1 -1 -1 -1
0
48
Migrated from old NTUJ.
Arab & North Africa 2008
| No. | Testdata Range | Score |
|---|