UVa 10940

From Algorithmist
Jump to navigation Jump to search

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