FarmFence
SRM 142 · 2003-04-15 · by TangentZ
Problem Statement
Your friend, John, is a poor farmer living in the rural area. Each year, he has to produce a certain amount of crops in order to support his family of five.
One unit of crops can be produced from a 1 by 1 square of farm land. John needs to protect his farm from intruders and animals by putting barbed wire fences along the boundary of the farm. Being so poor, John wants to minimize the length of the fence he has to purchase to protect his farm. John can change the shape of his farm to any rectangle with integral width and height in order to achieve this minimal fencing. He turns to you for help.
You are given the amount of crops that John needs to produce each year. Your task is to write a function that returns the minimum length of barbed wire fence needed to protect John's farm. The farm must have exactly the area required to produce the amount of crops specified and must be a rectangle with integral length sides.
Constraints
- crops is between 1 and 1,000,000, inclusive
6 Returns: 10
The possible dimensions of the farm are 1x6 and 2x3 (ignoring rotations). The amount of fencing is 14 for 1x6 and 10 for 2x3. 10 is the minimum.
18 Returns: 18
The possible dimensions are 1x18, 2x9, and 3x6 (ignoring rotations). The required fencing are 38, 22, and 18, respectively. 18 is the minimum.
987 Returns: 136
123456 Returns: 1670
1000000 Returns: 4000
Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FarmFence with a public method int minFencing(int crops) · 70 test cases · 2 s / 256 MB per case