Connection Status:
Competition Arena > IterateOverACube

IterateOverACube

SRM 775 · 2020-01-15 · by misof

SRM 775 · 2020-01-15 · by misof · Simple Math, Simple Search, Iteration
Class Name: IterateOverACube
Return Type: int[]
Method Name: findCell
Arg Types: (int, long long)
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.

Constraints

  • N will be between 1 and 10^6, inclusive.
  • index will be between 0 and N^3 - 1, inclusive.
Examples
0)
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).

1)
3
10
Returns: {0, 1, 2 }

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

2)
4747
106968940722
Returns: {4746, 4746, 4746 }

The very last cell visited in this cube.

3)
4
32
Returns: {0, 2, 3 }
4)
1000000
1000000000
Returns: {113, 391, 1312 }

Submissions are judged against all 120 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class IterateOverACube with a public method vector<int> findCell(int N, long long index) · 120 test cases · 2 s / 256 MB per case

Submitting as anonymous