This is the 16th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge
1953. Maximum number of weeks you can work
Thought analysis
If sum >= Max, work at maximum sum + Max weeks; otherwise, work at maximum 2 * sum + 1 weeks.
(A simple math problem)
1954. Collect enough apples for the smallest garden perimeter
Thought analysis
You will buy is (0, 0) is the center coordinates of a square of land, therefore the perimeter is multiplied by the distance from the center in you, and because of the number of apple tree each node and the node coordinates have a fixed relationship, so must have a formula, can be calculated when the distance of I, all the nodes of the tree number Sum.
For the circle of apple trees whose lower left corner is (-i,-i) and upper right corner is (I, I), the circle is divided into four corners of 44 apple trees whose coordinates contain four apple trees of 0. Due to symmetry, the rest of the apple trees can be regarded as the apple trees from (I,1) to (I,i-1). There are 8 segments.
The four apple trees at the four corners have 8i apples, and the four apple trees at the zero coordinates have 4I apples, From (I, 1) to (I, I – 1) of the apple tree I (I – 1) 2 + I (I) – 1 \ dfrac {I (I – 1)} {2} + I (I – 1) 2 (I) (I – 1) + I (I – 1) an apple, multiplied by 8 to 12 I (I – 1) an apple, so a total of 12 of the lap the I ^ 2 apples.
According to the Sum of squares formula, Sum = 2n(n+1)(2n+1).
In the case of the formula, we can get the answer by traversal, but this problem can also be solved by pruning.
Obviously, the time complexity can be reduced by binary search in the range (1,n)