# UVa 10940

## 10940 - Throwing cards away II[edit]

## Summary[edit]

This is similar to UVa 10935 - Throwing cards away I, except for **n** can now be as big as 500000. You can solve it using Dynamic Programming by breaking it into smaller problems.

## Explanation[edit]

We can solve this using Dynamic Programming by looking at each problem of length **n** in the following method, given **n** cards, after one iteration of the simulation, we will go from:

12345...n

to

345...n2

which is a problem of length **n-1**, but with an offset. So we can calculate the answer for **n-1**, and then shift the answer to match the offset. We can also do this from the bottoms up, as it is trivial.

Alternatively, test your code from UVa 10935 - Throwing cards away I on this one (you did solve that one first, right?). Try a bunch of sequential inputs, and you should discover a nice pattern.

## Solutions[edit]

## Input[edit]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 100 1000 500000 0

## Output[edit]

1 2 2 4 2 4 6 8 2 4 6 8 10 12 14 16 2 4 6 8 72 976 475712