You are given integers a, b and n. Consider the array lst[i] = a*i + b, 1 ≤ i ≤ n.
A removelst operation is defined as follows:
- Remove from the current array all the elements with an even index
- Obtain a new array with the remaining elements.
- Repeat the previous steps until the array contains only 2 elements.
Your task is to print the last 2 remaining elements.
Input
Three space-separated integers: a, b and n.
Output
The last 2 remaining elements, separated by space.
Constraints
- 2 ≤ n ≤ 109
- -1000 ≤ a, b ≤ 1000
Sample
| Input | Output | Explanation |
|---|---|---|
| 3 2 5 | 5 17 | The array transformation looks like this:
|
We can observe that:
- The first element is always on an odd position, so it never gets removed.
- The second value we need to output is located at position 1 + 2i-1, where i is the largest value such that 1 + 2i-1 < N.
A similar approach, implemented in Haskell:
import Data.Bits import Data.Int closestPower x = if null smallerPowers then max 1 $ closestPower (x-1) else x - sum (init smallerPowers) where smallerPowers = [2^i | i <- [0..32], not $ elem (x .&. (shift 1 i)) [0, x]] main = do input <- getContents let [a,b,n] = map read $ words input :: [Int64] putStrLn $ show (a + b) ++ " " ++ show (a * (succ $ closestPower n) + b)
