[POJ] 3208 Apocalypse Someday

Apocalypse Someday
Time Limit: 1000MS      Memory Limit: 131072K
Total Submissions: 2016     Accepted: 990
Description

The number 666 is considered to be the occult “number of the beast” and is a well used number in all major apocalypse themed blockbuster movies. However the number 666 can’t always be used in the script so numbers such as 1666 are used instead. Let us call the numbers containing at least three contiguous sixes beastly numbers. The first few beastly numbers are 666, 1666, 2666, 3666, 4666, 5666…

Given a 1-based index n, your program should return the nth beastly number.

Input

The first line contains the number of test cases T (T ≤ 1,000).

Each of the following T lines contains an integer n (1 ≤ n ≤ 50,000,000) as a test case.

Output

For each test case, your program should output the nth beastly number.

Sample Input

3
2
3
187
Sample Output

1666
2666
66666
Source

POJ Monthly--2007.03.04, Ikki, adapted from TCHS SRM 2 ApocalypseSomeday

数位DP第一道。
f[i][0/1/2/3]:
~[0/1/2] 长度为i的数中高位0/1/2位是6的非魔鬼数个数
~[3] 同上，高位3位以上是6的魔鬼数个数

就可以完整地描述状态了
f[i][3]=f[i-1][2]+10*f[i-1][3];
f[i][2]=f[i-1][1];
f[i][1]=f[i-1][0];
f[i][0]=9*(f[i-1][0]+f[i-1][1]+f[i-1][2]);

现在已知了i位长度的状况，可以定位第n个魔鬼数的长度，思想类似二分，然后循环每个数，求如果填当前数的魔鬼数个数，就可以确定这一位填还是不填。
感觉就像是优化过的暴力，索引？

//Stay foolish,stay hungry,stay young,stay simple
#include<iostream>
using namespace std;

const int MAXN=22;

long long f[MAXN][4];

void prework(){
    f[0][0]=1;
    for(int i=1;i<=20;i++){
        f[i][3]=f[i-1][2]+10*f[i-1][3];
        f[i][2]=f[i-1][1];
        f[i][1]=f[i-1][0];
        f[i][0]=9*(f[i-1][0]+f[i-1][1]+f[i-1][2]); 
    }
}

int n,t;

int main(){
    prework();
    cin>>t;
    while(t--){
        cin>>n;
        int len=3;
        while(f[len][3]<n) len++;
        int k=0;
        for(int i=len;i;i--){
            for(int j=0;j<=9;j++){
                long long cnt=f[i-1][3];
                if(j==6||k==3){
                    for(int l=max(3-k-(j==6),0);l<3;l++){
                        cnt+=f[i-1][l];
                    }
                }
                if(cnt<n) n-=cnt;
                else{
                    if(k<3){
                        if(j==6) k++;
                        else k=0;
                    }
                    cout<<j;
                    break;
                }
            }
        }
        cout<<endl;

    }
    return 0;
}