本文共 1162 字，大约阅读时间需要 3 分钟。

【题意】

用4,9按大小构造数字序列a[]为[4,9,44,49,94,99....]，定义499为1Z，输入k(1<=k<=1e8)，输出第kZ个数字。

比如k=1，输出为第499个数字，99994944。

【题解】

因为只有4,9两个数字，我们很容易联想到0,1，从而想到二叉树。我们这样构造二叉树，结点X的左儿子的编号为0X，右儿子的编号为1X，以此类推，我们可以得到整棵树的编号。我们令根结点为1，那么就可以通过编号的奇偶性判断它是父亲的左儿子还是右儿子，并且得到父亲的编号。所以，我们可以轻而易举的从儿子推到根结点的第一个儿子为止，输出这条路径即可。

【代码】

#include 
   
    using namespace std;typedef long long ll;int ans[105];int main(){    ll k;    while(~scanf("%lld",&k)){        if(k==0) break;        k=k*499+1;        ll deep=1,x=2;        while(x*2-1
    
     0;i--)            ans[i]=k%2,k/=2;        for(int i=1;i<=deep;i++)            if(ans[i]&1) printf("9");            else printf("4");        printf("\n");    }    return 0;}
    
   

【题面】

Description

众所周知，每一年的下半学期是XCPC区域赛比较密集的时候，众多acmers在这个时候终于可以出去比赛惹。ZZL带着他的队友们去了冰城，然后发生了一系列悲伤的故事，从此这座城市又多了三个悲伤的人。。。ZZL回到学校后看到4，9这两个数字就会想起那些悲伤的故事，于是他把4，9这两个数字称为悲伤数字。一个整数是悲伤数字，当且仅当它的十进制表示只包含悲伤数字。定义499为1Z。现在让你给出从小到大第kZ个悲伤数字。

第1个的悲伤数字是4，第2个的悲伤数字是9，第三个的悲伤数字是44。

Input

输入包含多组，每行为一组数据，包含一个整数k(1 \leq k \leq 10^8)k(1≤k≤108)。

文件结束为0，单独占一行，无需对应输出。

Output

每组输出仅一行，为第kZ个的悲伤数字，行末无空格。

Sample Input 1 

1

Sample Output 1

99994944

Hint

样例解释：99994944为从小到大第499个悲伤数字

输入输出较大，请注意输入输出效率

Source

zust - 出题组：朱展乐

转载地址：http://ghfen.baihongyu.com/