TopCoder Statistics - Problem Statement

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

500000

1000000000

94296562

-42562967

Returns: 32306
720875421873

500000

312

-288

36

Returns: 68000
197392864547455

500000

401521775

245649509

102912154

Returns: 61
166779980

500000

50968

23750

23871

Returns: 4321
4110421

500000

238406485

-205910762

99944174

Returns: 0
90353721053122336

500000

400407931

-197457350

-31941400

Returns: 25271
1649392638425

500000

304690653

-71134598

-218824753

Returns: 1
6132212237

500000

588276038

-79263767

-447995842

Returns: 0
90

500000

1000000000

-308312547

-66557516

Returns: 0
319166412955

500000

1000000000

268037322

1100407

Returns: 0
2134067978547277

500000

1000000000

620159081

247199513

Returns: 101
21

500000

53094530

4255332

-14613764

Returns: 0
73123106060

500000

68

0

-40

Returns: 51469
14195449

500000

3761

1704

-2509

Returns: 49868
74

500000

12668

667

9278

Returns: 0
326

500000

654565947

13316359

-523160397

Returns: 0
3395565786

500000

958961111

680952918

84325350

Returns: 0
2610656145901080

500000

6510240

600204

-3813880

Returns: 39163
20126885136

500000

1000000000

155495184

163304129

Returns: 0
402971145856812736

500000

1000000000

-615168005

-277732918

Returns: 18177
8055198805505466

500000

1000000000

830368963

621874618

Returns: 402
484194

500000

6425401

-3554222

-4699596

Returns: 0
3972335568289

500000

597

467

-76

Returns: 53575
10461899

500000

53268286

-14019794

2604385

Returns: 0
1761612801603059

500000

14

1

-14

Returns: 107144
4026953711252437

500000

988336771

-362198990

-486691280

Returns: 203
667650011480474

500000

774095033

-107622104

103917204

Returns: 66
310

500000

707152255

-220174893

-217762110

Returns: 0
28094388192

500000

1000000000

554987592

-456371326

Returns: 0
128864565976200

500000

1000000000

822399790

-323832736

Returns: 2
1656932

500000

1000000000

56838610

-781751547

Returns: 0
3639160263

500000

10176803

1577832

6641402

Returns: 0
7409522433

500000

23791432

-18134512

-18407354

Returns: 0
19

500000

6701

2859

3576

Returns: 0
10567993341

500000

64502687

-9281808

-23957294

Returns: 0
150543554349601

500000

733503356

-594326507

397822199

Returns: 16
312160617913

500000

23483863

21410866

16256089

Returns: 32
2631

500000

988845544

-408014973

-656870693

Returns: 0
214171096967

500000

1000000000

-851253835

60672564

Returns: 0
1

500000

1000000000

26200220

-78693921

Returns: 0
269555604

500000

1000000000

10018900

-163637585

Returns: 0
85966872114964311

500000

149873

-13528

-109488

Returns: 48515
729532867341263699

500000

77

6

-65

Returns: 75000
764453254677419033

500000

5

1

-4

Returns: 100000
225966143707773943

500000

25

16

-9

Returns: 83339
512413199499324224

500000

199731610

-11646479

-10412368

Returns: 35689
187233904329877208

500000

584288576

443781142

-213328406

Returns: 26331
279297165855534137

500000

401064369

263071118

341548625

Returns: 35132
235660488801125276

500000

1000000000

-573104229

-185640547

Returns: 11307
888311594778383949

500000

1000000000

992897122

-320532585

Returns: 32492
530685537310030123

500000

1000000000

-103556887

-339933370

Returns: 22872
670805556290418211

500000

3884327

3741216

3852594

Returns: 43103
150266329228020646

500000

23936

4487

16222

Returns: 51565
568385818021235434

500000

163

-92

-145

Returns: 60186
645938877488928923

500000

34

-23

33

Returns: 128787
904584888466417940

500000

180086166

-77060040

-19158619

Returns: 35072
49001594928261225

500000

286760769

16536293

-232340722

Returns: 28834
102205377907849285

500000

208403836

-180935302

29131501

Returns: 35322
933764705703994206

500000

1000000000

35948298

717717271

Returns: 32059
921116819761469196

500000

1000000000

890456143

709483900

Returns: 32236
592577213497384436

500000

1000000000

309944813

-121328896

Returns: 25987
45643985641639668

500000

1182

351

-658

Returns: 58340
218987930820364967

500000

562363

220396

-356784

Returns: 47733
222862214116716104

500000

10100

-7785

-6678

Returns: 52852
923756405898024848

500000

2655657

-1312861

-252670

Returns: 41275
964704468960584239

500000

930249034

288368403

766441760

Returns: 32650
691035187878088412

500000

184014264

146244987

112530396

Returns: 34998
945804643457764415

500000

905803163

222704970

682166197

Returns: 32336
973232005084865334

500000

1000000000

129537382

-867669821

Returns: 32206
23062581002338297

500000

1000000000

-724598052

993028603

Returns: 1146
941450657300297419

500000

1000000000

556769525

636833060

Returns: 32370
1000000000000000000

500000

706764645

-519274152

-501443521

Returns: 34242
1000000000000000000

500000

1364

-708

-450

Returns: 51505
1000000000000000000

500000

144

-110

-135

Returns: 71701
1000000000000000000

500000

2

1

-2

Returns: 125000
1000000000000000000

500000

295428469

-252549562

181981274

Returns: 38778
1000000000000000000

500000

515840353

346051469

-151613960

Returns: 39494
1000000000000000000

500000

626031362

191601826

358986301

Returns: 36510
1000000000000000000

500000

1000000000

210803182

202082950

Returns: 32107
1000000000000000000

500000

1000000000

-406030114

-208569984

Returns: 32367
1000000000000000000

500000

1000000000

244067792

14122322

Returns: 32423
1000000000000000000

500000

232878

151612

187547

Returns: 46818
1000000000000000000

500000

85656130

48649777

27035633

Returns: 36736
1000000000000000000

500000

407456

403606

151558

Returns: 40764
1000000000000000000

500000

12484757

-11259340

-5114822

Returns: 38695
1000000000000000000

500000

873602474

145762670

775829940

Returns: 32970
1000000000000000000

500000

284737270

246584197

58201634

Returns: 39664
1000000000000000000

500000

900436154

-622549785

679807314

Returns: 32600
1000000000000000000

500000

1000000000

975246409

-68712594

Returns: 32556
1000000000000000000

500000

1000000000

119028741

372896520

Returns: 32200
1000000000000000000

500000

1000000000

-363740448

-496421486

Returns: 32145
1000000000000000000

500000

1

0

0

Returns: 333333
1000000000000000000

500000

5866

2093

1435

Returns: 49305
1000000000000000000

500000

326517030

-108191840

158079509

Returns: 36357
1000000000000000000

500000

57591

55205

8867

Returns: 49675
1000000000000000000

500000

711113307

-345175801

153036849

Returns: 34259
1000000000000000000

500000

250907449

-247386675

36131968

Returns: 39462
1000000000000000000

500000

814870348

244543473

107004759

Returns: 34334
1000000000000000000

500000

1000000000

806156321

-299464213

Returns: 32353
1000000000000000000

500000

1000000000

-150701736

834819748

Returns: 31932
1000000000000000000

500000

1000000000

944048524

15126126

Returns: 32302

Statistics

Problem Statement for "PopcountRobot"

Problem Statement

Definition

Notes

Constraints

Examples