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;
}