## 100 - RemoveLst

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
, where`1 + 2`^{i-1}is the largest value such that`i`.`1 + 2`^{i-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)

## 250 - Keyboard

We can solve the problem using dynamic programming:

Let ` dp[i][L][R] = the minimum total cost of typing the first i characters, such that we end up with the left finger on the L key and the right finger on R`.

Initially, ** dp[0]['F']['J'] = 0** and

**.**

`dp[everything else] = inf`Now, assume we are in the state

**. There are two ways of having reached this state:**

`[i][L][R]`- from
, by moving the left finger from`[i-1][prevL][R]`to`prevL``L` - from
, by moving the right finger from`[i-1][L][prevR]`to`prevR``R`

In addition, we know that by reaching

**, we have just typed the**

`[i][L][R]`**character.**

`i`^{th}As a consequence, either

**or**

`L`**must be equal to**

`R`**.**

`s[i]`Finally, we construct the following recursion:

`dp[i][s[i]][prevR] = min(dp[i][s[i]][prevR], dp[i-1][prevL][prevR] + manhattanDist[prevL][s[i]]);``dp[i][prevL][s[i]] = min(dp[i][prevL][s[i]], dp[i-1][prevL][prevR] + manhattanDist[prevR][s[i]]);`

The answer is the minimum value of ** dp[N][L][R]**, for any

**in the alphabet.**

`L, R`## 500 - AndInt

### Haskell implementation:

solve [a, b] = (sum $ map subsequences deltas) `mod` (10^9+7) where deltas = zipWith (-) (tail interestPoints) interestPoints interestPoints = a : (dropWhile (<= a) $ takeWhile (<= b) powers) ++ [b+1] subsequences x = (x * succ x) `div` 2 powers = map (2^) [1..] main = do input <- getContents let queries = map ((map read) . words) $ (tail . lines) input sequence $ map (print . solve) queries

## 1000 - Peculiar Function

The first observation we can make is that ` 0 ≤ orSum(S') < 2^19` for any subset

`of`

**S'**`. Let's see if we can construct a set`

**S1**`, having`

**Q**`using the integer values from`

**0 ≤ orSum(Q) < 2^19**`. It is enough to consider for this all elements of`

**S1****which are**

`S1`**completely included**in

**. An element**

`Q`**is**

`x`**completely included**in a set

**if**

`S`**, i.e. there is no position**

`orSum(S) | x = orSum(S)``for which`

**0 ≤ i < 19****. If these are not enough to form**

`orSum(S) & 2^i == 0 and x & 2^i != 0`**, then we cannot obtain**

`Q`**at all.**

`Q` We now need to compute for each such ** Q** the orSum of all elements â€œcompletely includedâ€ in

**. We can compute**

`S1`**, where**

`dp[x] = orSum(dp[x - 2^i])`**and**

`0 ≤ i < 19`**. Remark: if**

`x & 2^i == 2^i`**belongs to**

`x`**, then**

`S1`**.**

`dp[x] = x` Now, ** S2** needs to contain all numbers

**having**

`x`**and**

`dp[x] = x`**This assures us that they cannot be generated by applying orSum on a subset of numbers from**

`orSum({dp[x - 2^i] where 0 ≤ i < 19 and x & 2^i == 2^i}) < x.`**, so they must be in**

`S1`**.**

`S2`