FruitTrees
TCO13 Round 2B · 2013-02-19 · by rng_58
TCO13 Round 2B · 2013-02-19 · by rng_58 · Brute Force, Math
Problem Statement
Problem Statement
There is an infinitely long straight road.
Fox Ciel is going to plant trees of three kinds: apple trees, kiwi trees, and grape trees.
There will be infinitely many trees of each kind.
Trees of each kind will be placed along the entire road in regular intervals.
More precisely, you are givenint s apple, kiwi, and grape with the following meaning:
The distance between any two consecutive apple trees must be apple, the distance between any two consecutive kiwi trees must be kiwi, and the distance between any two consecutive grape trees must be grape.
Ciel can only plant the trees at integer coordinates, but she gets to choose those coordinates as long as the above conditions are satisfied. In other words, Ciel gets to choose three integers x, y, and z such that:
More precisely, you are given
Ciel can only plant the trees at integer coordinates, but she gets to choose those coordinates as long as the above conditions are satisfied. In other words, Ciel gets to choose three integers x, y, and z such that:
- She plants apple trees at coordinates ..., x - 2 * apple, x - apple, x, x + apple, x + 2 * apple, ...
- She plants kiwi trees at coordinates ..., y - 2 * kiwi, y - kiwi, y, y + kiwi, y + 2 * kiwi, ...
- She plants grape trees at coordinates ..., z - 2 * grape, z - grape, z, z + grape, z + 2 * grape, ...
Constraints
- apple will be between 1 and 2,000, inclusive.
- kiwi will be between 1 and 2,000, inclusive.
- grape will be between 1 and 2,000, inclusive.
Examples
0)
1 5 8 Returns: 0
Apple trees will be planted at all integer coordinates, so at least two trees will be planted where a kiwi tree is planted.
1)
3 3 6 Returns: 1
One of the optimal solutions is as follows: Plant apple trees at ..., -5, -2, 1, 4, ... Plant kiwi trees at ..., -4, -1, 2, 5, ... Plant grape trees at ..., -9, -3, 3, 9, ...
2)
40 30 20 Returns: 5
3)
899 1073 1147 Returns: 14
4)
2000 2000 2000 Returns: 666
Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FruitTrees with a public method int maxDist(int apple, int kiwi, int grape) · 128 test cases · 2 s / 256 MB per case