BearPlays
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 two piles of stones. Initially, one of the piles has A and the other has B stones in it.
Limak has decided to perform a sequence of K operations. In each operation he will double the size of the currently smaller pile. Formally, if the current pile sizes are labeled X and Y in such a way that X <= Y, he will move X stones from the second pile to the first one. After this move the new pile sizes will be X+X and Y-X.
You are given the
Formally, suppose that the final pile sizes are labeled P and Q in such a way that P <= Q. Return P.
Notes
- Pay attention to the unusual time limit.
Constraints
- A and B will be between 1 and 1,000,000,000, inclusive.
- K will be between 1 and 2,000,000,000, inclusive.
4 7 2 Returns: 5
The process will look as follows: Initially, the pile sizes are 4 and 7. First operation: Limak doubles the pile of size 4 by moving 4 stones from the other pile to this pile. The new pile sizes are 8 and 3. Second operation: Limak doubles the pile of size 3. The final pile sizes are 5 and 6. As 5 <= 6, the correct return value is 5.
5 5 3 Returns: 0
The initial pile sizes are 5 and 5. In the first operation Limak will double one of them, so after the operation the new pile sizes will be 10 and 0. The second and third operation do nothing: in each of them Limak doubles the size of an empty pile. As 0 ≤ 10, the correct return value is 0.
2 6 1 Returns: 4
After the only operation the pile sizes will be 4 and 4, hence the correct return value is 4.
2 8 2000000000 Returns: 2
900000000 350000000 3 Returns: 300000000
Submissions are judged against all 150 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BearPlays with a public method int pileSize(int A, int B, int K) · 150 test cases · 2 s / 256 MB per case