10940 - Throwing cards away II

Given is an ordered deck of n cards numbered 1 to n with card 1 at the top and card n at the bottom. The following operation is performed as long as there are at least two cards in the deck:

Throw away the top card and move the card that is now on the top of the deck to the bottom of the deck.

Your task is to find the last, remaining card.
Each line of input (except the last) contains a positive number n ≤ 500000. The last line contains 0 and this line should not be processed. For each number from input produce one line of output giving the last remaining card. Input will not contain more than 500000 lines.

Sample input

7
19
10
6
0

Output for sample input

6
6
4
4

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1881

---

此題的操作具有遞迴關係。首先2張牌的情況，經過題目所說的操作答案就是第2張牌，至於3張牌的情況，經過題目所說的操作之後會變成2張牌的情況，4張牌的情況經過操作之後會變成3張牌的情況 ... n張牌的情況經過操作會變成n - 1張牌的情況。所以每個情況的解都可以由前一個情況來推算，利用dynamic programming的觀念，先把2到500000張牌的每個情況都推算出來並且記起來，接下來就看題目要的是哪個情況就把哪個情況的解叫出來就好了。至於如何從n - 1張牌情況的解推出n張牌情況的解呢?若n - 1張牌情況的解是最後一張，則n張牌情況的解就是第2張，若n - 1張情況的解不是最後一張，那這個解的位置加上2就是n張牌情況的解。此題還有一點要注意的是若輸入是1則輸出就是1，因為無法進行任何操作。

c++ code:

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> table;

    table[1] = 1;
    table[2] = 2;
    for (int i=3; i<=500000; i++) {
        if (table[i - 1] == i - 1)
            table[i] = 2;
        else
            table[i] = table[i - 1] + 2;
    }
    while (true) {
        int n;

        cin >> n;
        if (!n)
            break;
        cout << table[n] << endl;
    }

    return 0;
}