Honeycomb
Time limit2sMemory limit128 MB
Given a hexagonal spiral numbering of honeycomb cells centered at 1, compute the minimum number of rooms on a shortest path from room 1 to room N.
- Level
Medium6 of 10
- Topics
- Math, Binary search, Geometry
- Solved
- No attempts yet
Problem
Hexagonal rooms are connected in a honeycomb pattern. The center room is numbered 1. Around it, neighboring rooms are numbered by increasing by 1 in order as the pattern expands outward. Given a positive integer N, find the minimum number of rooms that must be visited to move from room 1 to room N. Count both the starting room and the destination room.
Input
The first line contains an integer N. (1 ≤ N ≤ 1,000,000,000)
Output
Print the number of rooms visited on a shortest path from room 1 to room N.