Three Sons
Time limit1sMemory limit512 MB
Split an integer n into three strictly increasing positive parts a < b < c whose squares sum to the minimum possible value.
- Level
Medium5 of 10
- Topics
- Math, Greedy, Implementation
- Solved
- No attempts yet
Problem
In the domain of the king of Flatlandia there is a straight road kilometers long, and a huge forest lies on one side of it. The king of Flatlandia took up the ideas of nature conservation and decided to turn his forest into a nature reserve. But his sons objected: they wanted to receive these lands as an inheritance.
The king has three sons: the youngest, the middle, and the eldest. The king decided that the parts of the forest he leaves to his sons as an inheritance will not be included in the reserve. When drawing up the will, the king wants the following conditions to hold for the plots:
- Each plot must be a square whose side length is expressed by a positive integer. One side of each square must lie on the road. Let the plots have sizes , , and .
- The sides of the squares must completely cover the road: the value of must equal .
- The youngest son's plot must be strictly smaller than the middle son's plot, and the middle son's plot must in turn be strictly smaller than the eldest son's plot, that is, the inequality must hold.
- The total area of the plots must be minimal.
You must write a program that, given the length of the road, determines the sizes of the plots to be allotted to the king's sons.
Input
The input file contains a single integer ().
Output
The output file must contain three positive integers separated by spaces: , , and , the side lengths of the plots to be allotted to the youngest, middle, and eldest son, respectively. If there are several optimal solutions, you may output any of them.
Hint
