GridSpiral
TCO20 Round 2A · 2020-04-13 · by misof
Problem Statement
There is an infinite square grid. Each cell of the grid contains a non-negative integer, and each non-negative integer appears in exactly one cell.
Two cells of the grid are called adjacent if they share a side.
The integers are arranged into a spiral that starts with the number 0. For each n, the cells that contain numbers n and n+1 are adjacent. If you start at 0 and walk along the spiral, your sequence of steps will be as follows: 1 step up, 1 step right, 2 steps down, 2 steps left, 3 steps up, 3 steps right, 4 steps down, and so on.
Beginning of the spiral:
9 10 11 12
8 1 2 13
7 0 3 14
.. 6 5 4 15
.. .. .. .. 16
You are given the
Notes
- It is guaranteed that whenever an answer exists, it fits into a long.
Constraints
- D will be between 1 and 10^9, inclusive.
5 Returns: 0
Cells with values 0 and 5 are adjacent: a step down from cell 0 will take you to cell 5.
11 Returns: 2
The cell with value 13 is to the right of the cell with value 2. Cells 0 and 11 are not adjacent and neither are 1 and 12, so 2 is the smallest cell with the desired property.
47 Returns: 110
100 Returns: -1
1 Returns: 0
Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GridSpiral with a public method long long findCell(int D) · 45 test cases · 2 s / 256 MB per case