PopcountRobot | Topcoder Archive

Problem Statement

In this problem, popcount(n) denotes the number of ones in the binary representation of n. For example, popcount(2015) = 10 because 2015 is 11111011111 in binary.

The horizontal plane is divided into an infinite grid of unit square cells. All cells are currently white. Cat Snuke has just bought a strange robot and placed it onto the grid. The current coordinates of the robot are (0, 0). The robot is going to paint some of the cells black.

You are given a long T. For each t from 0 to T-1, inclusive, the robot will execute the following sequence of steps:

The robot paints the current cell black. (If the cell is already black, the robot does nothing.)
If popcount(t) mod 4 = 0, the robot increases its x-coordinate by 1.
If popcount(t) mod 4 = 1, the robot increases its y-coordinate by 1.
If popcount(t) mod 4 = 2, the robot decreases its x-coordinate by 1.
If popcount(t) mod 4 = 3, the robot decreases its y-coordinate by 1.

You are also given four ints: Q, M, x, and y. Compute ans in the following pseudocode:

ans = 0;
for(i = 0; i &lt; Q; i++){
	if(the cell (x,y) is black after the robot stops working) ans++;
	x = ((x + M) * 7180087 + 5205425) % (2 * M + 1) - M;
	y = ((y + M) * 6132773 + 9326231) % (2 * M + 1) - M;
}
return ans;

Definition

Class:: PopcountRobot
Method:: countBlack
Parameters:: long, int, int, int, int
Returns:: int
Method signature:: int countBlack(long T, int Q, int M, int x, int y)
(be sure your method is public)

Notes

The intended solution can compute the colors of any set of up to 500,000 cells in the range [-10^9, 10^9] x [-10^9, 10^9].

Constraints

T will be between 1 and 10^18, inclusive.
Q will be between 1 and 500,000, inclusive.
M will be between 0 and 1,000,000,000, inclusive.
x and y will be between -M and M, inclusive.

Examples

```
5
```
```
10
```
```
2
```
```
-1
```
```
-2
```
```
Returns: 2
```
The ten coordinates you get in the pseudocode are: (-1, -2), (0, -1), (2, 2), (1, 1), (-1, -2), (0, -1), (2, 2), (1, 1), (-1, -2), and (0, -1). Two of them ((1, 1) twice) are colored black when T = 5.
```
30
```
```
500000
```
```
5
```
```
3
```
```
4
```
```
Returns: 0
```
```
2015
```
```
500000
```
```
50
```
```
12
```
```
34
```
```
Returns: 40000
```

1000000000000000000

1000000000

94296562

-42562967

Returns: 32306

720875421873

-288

Returns: 68000

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.