FoxAndCake2
TCO17 Round 2A · 2017-03-31 · by cgy4ever
TCO17 Round 2A · 2017-03-31 · by cgy4ever · Simple Math
Problem Statement
Problem Statement
Fox Ciel has c cherries and s strawberries.
She wants to bake some cakes.
While doing so, she wants to follow some rules:
You are given theint s c and s.
Return "Possible" if Ciel can bake cakes according to the above rules, or "Impossible" if she cannot do so.
- She must use exactly all cherries and all strawberries she has.
- The number of cakes can be arbitrary (i.e., any positive integer).
- Different cakes may contain different amounts of cherries and strawberries.
- Each cake must contain at least one cherry and at least one strawberry.
- A cake will taste bad if the number of cherries and the number of strawberries it contains happen to be coprime. Therefore, the numbers of cherries and strawberries in a cake must never be coprime. (Two positive integers are coprime if their greatest common divisor is 1.)
You are given the
Constraints
- c will be between 1 and 1,000,000,000, inclusive.
- s will be between 1 and 1,000,000,000, inclusive.
Examples
0)
74 109 Returns: "Possible"
One possible solution is to bake 3 cakes as follows: A cake with 21 cherries and 14 strawberries. A cake with 20 cherries and 40 strawberries. A cake with 33 cherries and 55 strawberries.
1)
1000000000 1000000000 Returns: "Possible"
Here Ciel can simply make one huge cake with 1000000000 cherries and 1000000000 strawberries.
2)
1 58 Returns: "Impossible"
Ciel only has 1 cherry, so the only option is to bake one cake with 1 cherry and 58 strawberries. However, 1 and 58 are coprime, so this is not a good cake.
3)
5 6 Returns: "Impossible"
4)
3 4 Returns: "Impossible"
Submissions are judged against all 252 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoxAndCake2 with a public method string isPossible(int c, int s) · 252 test cases · 2 s / 256 MB per case