TopCoder Statistics - Problem Statement

Problem Statement

We use the following pseudocode to visit each cell of an N x N x N cube exactly once:

for sum = 0 .. 3*N-3:
    for x = 0 .. N-1:
        for y = 0 .. N-1:
            for z = 0 .. N-1:
                if x+y+z == sum:
                    visit (x,y,z)

You are given the int N and the long index: a 0-based index into the sequence of cells visited by the above pseudocode. Return a int[] containing the coordinates of that cell.

Definition

Class:: IterateOverACube
Method:: findCell
Parameters:: int, long
Returns:: int[]
Method signature:: int[] findCell(int N, long index)
(be sure your method is public)

Constraints

N will be between 1 and 10^6, inclusive.
index will be between 0 and N^3 - 1, inclusive.

Examples

3

9

Returns: {2, 0, 0 }

The first ten cells visited are (0,0,0), (0,0,1), (0,1,0), (1,0,0), (0,0,2), (0,1,1), (0,2,0), (1,0,1), (1,1,0), and (2,0,0).
3

10

Returns: {0, 1, 2 }

The next visited cell is (0,1,2).
4747

106968940722

Returns: {4746, 4746, 4746 }

The very last cell visited in this cube.
4

32

Returns: {0, 2, 3 }
1000000

1000000000

Returns: {113, 391, 1312 }
1000000

10000000000

Returns: {2490, 940, 483 }
1000000

100000000000

Returns: {1513, 2841, 4079 }
1000000

100000000000000

Returns: {12109, 28955, 43278 }
1000000

1000000000000000

Returns: {5468, 119826, 56417 }
1000000

100000000000000000

Returns: {355480, 317744, 170207 }
1000000

999999999999999999

Returns: {999999, 999999, 999999 }
1000000

999999999999314159

Returns: {999978, 999949, 999911 }
181

524499

Returns: {47, 53, 45 }
221

9288539

Returns: {192, 129, 132 }
233

9576276

Returns: {127, 140, 166 }
176

2159461

Returns: {63, 101, 74 }
263

12970702

Returns: {95, 185, 191 }
201

5163702

Returns: {113, 85, 139 }
21

6857

Returns: {15, 3, 19 }
338

1587786

Returns: {191, 10, 9 }
491

13751391

Returns: {82, 302, 50 }
1

0

Returns: {0, 0, 0 }
483

106333279

Returns: {405, 241, 465 }
247

12144314

Returns: {69, 211, 200 }
280

306545

Returns: {37, 76, 8 }
470

42356098

Returns: {414, 182, 49 }
291

14351211

Returns: {191, 208, 68 }
118

498580

Returns: {3, 76, 65 }
268

17245392

Returns: {259, 92, 222 }
184

3709618

Returns: {117, 41, 140 }
491

32487243

Returns: {19, 153, 409 }
18

4595

Returns: {12, 4, 17 }
192

6012385

Returns: {124, 113, 152 }
353

23719800

Returns: {350, 54, 142 }
308

11472722

Returns: {133, 273, 10 }
286

19297256

Returns: {140, 231, 195 }
391

13152217

Returns: {55, 146, 227 }
123

1653833

Returns: {91, 97, 72 }
431

4735057

Returns: {21, 142, 141 }
65

175074

Returns: {43, 19, 46 }
51

95115

Returns: {46, 4, 40 }
297

12870765

Returns: {20, 159, 262 }
261

8483718

Returns: {136, 95, 151 }
50

85040

Returns: {24, 37, 25 }
447

30461759

Returns: {284, 16, 272 }
475

93846145

Returns: {234, 360, 399 }
433

44944005

Returns: {239, 386, 54 }
112

987821

Returns: {64, 36, 98 }
382

7391752

Returns: {292, 58, 2 }
396

27961596

Returns: {249, 105, 212 }
310

11846359

Returns: {96, 44, 281 }
346

19214496

Returns: {114, 316, 71 }
921856

411527553924696741

Returns: {394821, 676922, 342156 }
558561

11560864683195456

Returns: {291675, 70902, 48300 }
507455

81099115717248592

Returns: {349325, 232562, 261876 }
817538

150020310244919764

Returns: {163738, 536271, 269255 }
990520

598826350956977294

Returns: {240287, 459414, 941214 }
838457

238754233416425461

Returns: {121155, 551166, 478442 }
398320

18240564982126700

Returns: {208241, 70901, 201626 }
632837

43004629463328980

Returns: {263430, 359759, 13442 }
465449

78829942151347831

Returns: {226296, 440056, 220451 }
657622

219478815169623479

Returns: {540273, 58213, 643319 }
86797

299204922133549

Returns: {57880, 27413, 39983 }
536069

137344702763454609

Returns: {412125, 446209, 285353 }
820339

251113753260025121

Returns: {559756, 435872, 185440 }
383337

54704590077132805

Returns: {229797, 364674, 341874 }
34794

18647063472441

Returns: {7848, 27752, 13924 }
942873

701707653598957062

Returns: {522540, 608570, 761863 }
542079

135989981441467425

Returns: {517862, 472745, 116628 }
958842

735937495250479787

Returns: {436059, 863972, 620537 }
837263

363162269471163301

Returns: {531572, 602930, 255486 }
869825

243686940656174981

Returns: {393775, 251651, 506787 }
362770

12730949575617617

Returns: {307866, 12702, 105106 }
492614

28632296060115519

Returns: {69447, 308897, 178415 }
134089

615460646283113

Returns: {126403, 23173, 5368 }
765901

328364293399283908

Returns: {578649, 548643, 268765 }
360768

28272565088928489

Returns: {360214, 94726, 135746 }
113336

999620424582825

Returns: {27011, 96679, 75366 }
474

87593894

Returns: {460, 123, 353 }
128321

151240461811355

Returns: {18953, 10186, 67674 }
387186

19041058990981864

Returns: {153118, 9242, 327411 }
43732

25495529047484

Returns: {12534, 19449, 21856 }
775050

115954171956499518

Returns: {222821, 542963, 122135 }
821123

467907127958767027

Returns: {608600, 512912, 540620 }
518726

65369357269403097

Returns: {312247, 145167, 298758 }
590984

2878657022197592

Returns: {214494, 25429, 18567 }
728798

100951114960570490

Returns: {282547, 242708, 323230 }
876372

390082474188679734

Returns: {712117, 364517, 331348 }
666397

26912492139157267

Returns: {202682, 123651, 218212 }
920168

270361549640470091

Returns: {140542, 135638, 912691 }
746841

218322486522878777

Returns: {606858, 332365, 205046 }
129131

199484146438490

Returns: {25005, 15155, 66013 }
317434

31678304617225749

Returns: {303226, 217271, 309124 }
574469

68921058052483831

Returns: {346497, 84294, 324778 }
642412

211565742049445965

Returns: {573569, 228834, 439736 }
560871

158506026406337378

Returns: {496430, 443562, 267011 }
607921

78733183376324058

Returns: {538015, 191928, 58446 }
649056

23261102945220903

Returns: {16411, 45051, 457250 }
590306

98781084527022623

Returns: {309414, 549182, 11290 }
583556

119176877575642413

Returns: {332006, 367129, 254407 }
437934

81327208505088830

Returns: {381385, 269004, 411559 }
885305

564072768509662490

Returns: {468067, 438077, 829680 }
626693

18313084019948824

Returns: {145519, 124050, 209395 }
532546

130789260850591833

Returns: {303576, 489901, 308923 }
863676

501039997086049037

Returns: {293327, 770877, 575386 }
849005

601969269871064143

Returns: {726593, 737701, 691212 }
800498

38156807140583186

Returns: {239995, 28076, 343678 }
819584

165806837894652858

Returns: {401203, 601032, 2355 }
821817

282582364040391435

Returns: {671309, 485342, 86066 }
526799

101511574568577541

Returns: {507643, 18010, 405547 }
834931

192442926016731686

Returns: {285619, 354777, 418863 }
485031

84699817485842748

Returns: {424686, 148727, 319342 }
1000000

512345678901234567

Returns: {857461, 282243, 376757 }
1000000

987654321987654321

Returns: {820565, 915866, 843594 }
1000000

10000000

Returns: {111, 24, 255 }
3

2

Returns: {0, 1, 0 }
1000000

499999999999999999

Returns: {999999, 499999, 0 }
3

1

Returns: {0, 0, 1 }
100

100000

Returns: {16, 6, 61 }
4

4

Returns: {0, 0, 2 }

Statistics

Problem Statement for "IterateOverACube"

Problem Statement

Definition

Constraints

Examples