ANARC08I - I Speak Whales
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 2^(N+1) can be constructed as the "union" of 4 Walsh Matrices of size 2^N arranged such that the lower right matrix is inverted whereas the other 3 matrices are not, i.e.:
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 , R , S , and E , write a program that will construct a Walsh Matrix of size 2^N and will print the sum of all the numbers in row #R between columns #S and #E (inclusive.)
Input
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 , R , S , and E , where 0 <= N <= 60 , 0 <= R < 2^N , 0 <= S <= E < 2N , and E - S <= 10,000 . The last line of the input file has four -1's and is not part of the test cases.
Output
For each test case, print the output on a single line.
Example
Input: 2 1 0 1 48 0 0 47 -1 -1 -1 -1 Output: 0 48
hide comments
Seckin Can Sahin:
2009-07-09 13:14:52
limits are correct. and also it is true that 0 <= S <= E < 2^N.
|
|
Dominik Kempa:
2009-07-08 17:49:53
I suppose the limits aren't correct, shouldn't there be 0 <= S <= E < 2^N ? |
|
Robert Gerbicz:
2009-07-05 07:22:41
My O(E-S+N) algorithm pass the problem. Last edit: 2009-07-05 07:23:01 |
|
[Trichromatic] XilinX:
2009-07-05 02:57:49
Time limit too strict!
|
Added by: | Ahmed Aly |
Date: | 2009-07-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | ANARC 2008 |