Eva

Description

筑地市场是位于日本东京都中央区筑地的公营批发市场，为东京都政府设置的中央批发市场之一，亦是日本最大的鱼市场。其规模之大与知名度之广，不只是东京，更是日本首屈一指的批发市场。全球百分之五十的金枪鱼，从世界的各地被运往这里，在每天的清晨，进行着繁忙的拍卖，它们是寿司中最不可或缺的食材，如何能够买到上等的金枪鱼，成为了每家寿司店都关注的大事。

当地的鱼贩，会取出鱼腹的一小块进行观察，以辨别鱼品质的好坏...

我们将取出的小块可以看成是一个十进制数字串（没有前缀0），其中包含数字4或者7的数字串，被认为是好的。岛娘想知道所有的数字串中，数字串转为十进制数后排第 k 小（从1开始）的好字符串是多少，你可以帮助她吗？

Input 

输入数据包含一行一个整数 k（k ≤ 1018）。

Output

输出数据包含一行，表示对应的十进制数字串。

Sample Input

19

Sample Output

54

#include<iostream>

#include<cstdio>

using namespace std;

long long k;

long long dp[25][2];

int n[25];

long long dfs(int x,int y,int z)

{

    if(x==-1&&y)

        return 1;

    if(x==-1)

        return 0;

    if(!z&&dp[x][y]!=-1)

        return dp[x][y];

    int e=9;

    if(e==z) e=n[x];

    long long ans=0;

    for(int i=0;i<=e;i++)

        ans+=dfs(x-1,y||(i==4)||(i==7),z&&(i==e));

    if(!z)

        dp[x][y]=ans;

    return ans;

}

long long solve(long long x)

{

    int num=0;

    while(x)

    {

        n[num++]=x%10;

        x/=10;

    }

    memset(dp,-1,sizeof(dp));

    return dfs(num-1,0,1);

}

int main()

{

    scanf("%lld",&k);

    long long l=1,r=2e18,ans=4;

    while(l<=r)

    {

        long long mid = (l+r)/2;

        if(solve(mid)>=k)

            r=mid-1,ans=mid;

        else l=mid+1;

    }

    cout<<ans<<endl;

    return 0;

}