JOIN
Get Time

   Problem Statement  

 Problem Statement for BearPlays

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 ints A, B, and K. Determine the pile sizes after Limak finishes all his operations. Return the size of the smaller of those piles.



Formally, suppose that the final pile sizes are labeled P and Q in such a way that P <= Q. Return P.

 

Definition

    
Class:BearPlays
Method:pileSize
Parameters:int, int, int
Returns:int
Method signature:int pileSize(int A, int B, int K)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
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.
1)
    
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)
    
2
6
1
Returns: 4
After the only operation the pile sizes will be 4 and 4, hence the correct return value is 4.
3)
    
2
8
2000000000
Returns: 2
4)
    
900000000
350000000
3
Returns: 300000000

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 664 Round 1 - Division I, Level One