2012-09-23 10:45:01Morris
[ZJ][數學解] a532. 奇特的數列
內容 ：
有一個數列的前十項：0、1、8、11、69、88、96、101、111、181，這個數列是在一次考古研究中發現，考古學家想要知道這個數列的後續發展，或許能預測人類的未來。你的任務是寫一支程式求得這個數列的任一項數值。
輸入說明
：
每行一個十進位正整數Ｎ（0＜Ｎ＜＝1000000），以Ｎ＝0代表輸入結束。
輸出說明
：
輸出一個非負整數，代表這個奇特數列的第Ｎ項
範例輸入 ：
1 2 3 0
範例輸出 ：
0 1 8
提示
：
背景知識：
DP
測資自己出的，有錯請提出><
測資自己出的，有錯請提出><
出處
：
2012成功高中校內賽第五題
(管理：eddy841021)
因為數字裡面出會出現 {0,1,6,8,9} => {0,1,2,3,4},
一樣的方法, 我們只看一半的位數, 此時要分成兩種情況討論,
長度為奇數則尾數不為 6 或 9, 因此要特別考慮, 而且 0 不能當作開頭,
那麼我們將每個一半的數字都當作一個 5 進制的數字去看, 找出 rank 之後, 再打回去對應
#include <stdio.h>
int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int dp[20] = {0,3}, x5[20] = {1}, stk[20];
int i, j;
char buf[5] = {'0','1','6','8','9'};
char buf2[5] = {'0','1','9','8','6'};
char str[30];
for(i = 1; i < 20; i++) x5[i] = x5[i-1]*5;
for(i = 2; i < 20; i++) {
j = i/2;
if(i&1)
dp[i] = (x5[j]-x5[j-1])*3;
else
dp[i] = (x5[j]-x5[j-1]);
}
int n, l;
while(ReadInt(&n) && n) {
for(i = 1; i < 20; i++) {
if(n <= dp[i]) {
l = i;
break;
}
n -= dp[i];
}
int idx = 0;
j = l/2;
if(l&1) {
int n3 = n/3+x5[j-1]-(n%3 == 0);
n = n - n/3*3;
while(n3) {
stk[idx++] = n3%5;
n3 /= 5;
}
} else {
n += x5[j-1] - 1;
while(n) {
stk[idx++] = n%5;
n /= 5;
}
}
int at = 0;
for(i = j-1; i >= 0; i--)
str[at++] = buf[stk[i]];
if(l&1) {
if(!n) str[at++] = '8';
else if(n == 1) str[at++] = '0';
else str[at++] = '1';
}
for(i = 0; i < j; i++)
str[at++] = buf2[stk[i]];
str[at] = '\0';
puts(str);
}
return 0;
}
因為數字裡面出會出現 {0,1,6,8,9} => {0,1,2,3,4},
一樣的方法, 我們只看一半的位數, 此時要分成兩種情況討論,
長度為奇數則尾數不為 6 或 9, 因此要特別考慮, 而且 0 不能當作開頭,
那麼我們將每個一半的數字都當作一個 5 進制的數字去看, 找出 rank 之後, 再打回去對應
#include <stdio.h>
int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int dp[20] = {0,3}, x5[20] = {1}, stk[20];
int i, j;
char buf[5] = {'0','1','6','8','9'};
char buf2[5] = {'0','1','9','8','6'};
char str[30];
for(i = 1; i < 20; i++) x5[i] = x5[i-1]*5;
for(i = 2; i < 20; i++) {
j = i/2;
if(i&1)
dp[i] = (x5[j]-x5[j-1])*3;
else
dp[i] = (x5[j]-x5[j-1]);
}
int n, l;
while(ReadInt(&n) && n) {
for(i = 1; i < 20; i++) {
if(n <= dp[i]) {
l = i;
break;
}
n -= dp[i];
}
int idx = 0;
j = l/2;
if(l&1) {
int n3 = n/3+x5[j-1]-(n%3 == 0);
n = n - n/3*3;
while(n3) {
stk[idx++] = n3%5;
n3 /= 5;
}
} else {
n += x5[j-1] - 1;
while(n) {
stk[idx++] = n%5;
n /= 5;
}
}
int at = 0;
for(i = j-1; i >= 0; i--)
str[at++] = buf[stk[i]];
if(l&1) {
if(!n) str[at++] = '8';
else if(n == 1) str[at++] = '0';
else str[at++] = '1';
}
for(i = 0; i < j; i++)
str[at++] = buf2[stk[i]];
str[at] = '\0';
puts(str);
}
return 0;
}