Shortest Path on a Triangular Grid
Time limit2sMemory limit128 MB
Given two cell indices in a triangular grid of small triangles arranged by rows, compute the minimum number of edge-adjacent moves between them for numbers up to one billion.
- Level
Medium7 of 10
- Topics
- Math, Geometry, Implementation
- Solved
- No attempts yet
Problem
There is a triangular grid made of small equilateral triangles. The top row contains one triangle numbered 1. For row r, there are 2r - 1 triangles, numbered consecutively from left to right. Therefore, the last number in row r is r^2.
You want to move from the triangle numbered A to the triangle numbered B. In one move, you may move only to a neighboring triangle that shares an edge with the current triangle. You cannot move through a vertex, and you cannot move outside the triangular grid.
The length of a path is the number of edges crossed along the way. Given A and B, find the minimum possible path length.
Input
The first line contains two integers A and B. (1 ≤ A, B ≤ 1,000,000,000)
Output
Print the length of the shortest path.