UVA10940 - Throwing cards away II（找規律）

UVA10940 - Throwing cards away II（找規律）

UVA10940 - Throwing cards away II（找規律）

題目鏈接

題目大意:桌上有n張牌，按照1-n的順序從上到下，每次進行將第一張牌丟掉，然後把第二張放到這疊牌的最後。反復進行這樣的操作，直到只剩下一張牌。

解題思路：只能先暴力，將前面小點的n打印出來，看看有什麼規律。
規律：f【2^k + mod] = 2*mod;(mod > 0); n = 1需要特判.

代碼：

#include 
#include 

const int maxn = 5e5 + 5;
int f[maxn];

void init () {

    int tmp = 1;
    f[1] = 1;
    for (int i = 2; i <= maxn - 5; i++) {

        if(i > tmp * 2) {
            tmp *= 2;
            f[i] = 2 * (i - tmp);
        } else
            f[i] = 2 * (i - tmp);    
    }
}

int main () {

    init();
    int n;

    while (scanf ("%d", &n) && n) {

        printf ("%d\n", f[n]);
    }
    return 0;
}