UVa 10940

10940 - Throwing cards away II

• http://acm.uva.es/p/v109/10940.html

Summary

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

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.

Input

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

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