BearPlaysDiv2
SRM 664 · 2015-06-30 · by Errichto
Problem Statement
Limak is a little bear who loves to play. Today he is playing by moving some stones between three piles of stones. Initially, the piles contain A, B, and C stones, respectively. Limak's goal is to produce three equal piles.
Limak will try reaching his goal by performing a sequence of zero or more operations. In each operation he will start by choosing two unequal piles. Let's label their sizes X and Y in such a way that X < Y. He will then double the size of the smaller chosen pile by moving some stones between the two chosen piles. Formally, the new sizes of the two chosen piles will be X+X and Y-X.
You are given the
Constraints
- A, B and C will be between 1 and 500, inclusive.
10 15 35 Returns: "possible"
One valid sequence of operations looks as follows: The initial pile sizes are 10, 15, and 35. For the first operation Limak will choose the piles with 15 and 35 stones. After doubling the size of the smaller pile the new sizes of these two piles will be 30 and 20. After the first operation the pile sizes are 10, 30, and 20. For the second operation Limak will choose the piles with 10 and 30 stones. After doubling the size of the smaller pile the new sizes of these two piles will be 20 and 20. After the second operation each pile has 20 stones, which means that Limak has reached his goal.
1 1 2 Returns: "impossible"
No matter what Limak does, there will always be two piles with a single stone each and one pile with 2 stones.
4 6 8 Returns: "impossible"
18 18 18 Returns: "possible"
Sometimes Limak can reach his goal without making any operations.
225 500 475 Returns: "possible"
471 471 471 Returns: "possible"
important test
Submissions are judged against all 67 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BearPlaysDiv2 with a public method string equalPiles(int A, int B, int C) · 67 test cases · 2 s / 256 MB per case