Mission Control operates an experimental power grid: a relay station sits at every integer coordinate (x, y) on an infinite plane, and the station at (x, y) generates exactly |x| + |y| gigawatts. Engineers want to enclose the hub at the origin with a square containment fence whose sides are parallel to the axes and whose corners are (p, p), (p, -p), (-p, p) and (-p, -p) for some integer p >= 0. The fence encloses every relay station with -p <= x <= p and -p <= y <= p, including stations sitting exactly on the boundary.
Given the total generation capacity that must be captured, find the minimum possible perimeter of a fence that captures at least that much power in total, summed over every enclosed station (boundary included).
A single line containing one integer need, the required total generation capacity.
A single integer: the minimum perimeter of a valid fence.
Example 1
Input
1
Expected
8
Explanation
total(0)=0 apples is below the requirement of 1, but total(1)=2*1*2*3=12 already meets it, so the smallest fence uses p=1, giving perimeter 8*1=8.
Example 2
Input
100
Expected
24
Explanation
total(1)=12 and total(2)=2*2*3*5=60 are both below 100, but total(3)=2*3*4*7=168 meets the requirement, so p=3 and the perimeter is 8*3=24.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →