ACM题解——训练赛2_B - Nirvana

题目描述

B - Nirvana

Kurt reaches nirvana when he finds the product of all the digits of some positive integer. Greater value of the product makes the nirvana deeper.

Help Kurt find the maximum possible product of digits among all integers from 11 to nn.

Input

The only input line contains the integer nn (1≤n≤2⋅1091≤n≤2⋅109).

Output

Print the maximum product of digits among all integers from 11 to nn.

 

Examples

Input

390

Output

216

Input

7

Output

7

Input

1000000000

Output

387420489

 

Note

In the first example the maximum product is achieved for 389389 (the product of digits is 3⋅8⋅9=2163⋅8⋅9=216).

In the second example the maximum product is achieved for 77 (the product of digits is 77).

In the third example the maximum product is achieved for 999999999999999999 (the product of digits is 99=38742048999=387420489).

题意

题目大意是给定一个数n，求小于等于n的情况下，求出数字每一位相乘得出结果的最大值。

 

题解

本题首先要明确的思路是对于某一位来说要么不变，要变就一定变成9，且需要向上一位借位；变成比自己小的数没有意义，只能让结果更小。因此对每一位的处理就是：变成9向上借位——递归下一位——回溯，用本身值，借位加回来，原本借位乘的数字也要除去——递归下一位。需要注意的是，当当前数字是9的时候就不要借位，因此处理不需要借位，回溯也不用将借位加回去。全程都需要算所有位相乘的值，并保存最大值，实时更新。这样就会求出所有过程的最大值。

本题还有一个递归的思路非常简洁：当n<10时，就输出其和1相比的最大值（就是避免最高位的0乘进来），否则就return max(当前位不做变化×处理高一位的结果,当前位变成9，借上面一位×处理高一位的结果）。当前位用n%10得到，去除当前位剩下的数是n/10。这样递归return的结果就是最终需要的最大值。

代码

方法一：

#include<iostream>
using namespace std;
long long int sub=1;
long long int maxx=1;
int getws(long long int n)
{
    int num=0;
    while(n>0)
    {
        num++;
        n/=10;
    }
    return num;             //求出n有几位，位数ws
}
void getmaxx(int *a,int ws,int pos)  //a存放每一位数字，数组最低位是数n的个位，ws是n的位数，pos是当前算到第几位
{
    if(pos==ws-1)           //当计算到最后一位数字时
    {
        if(a[pos]!=0)       //高位有可能因借位变成0，这是不用乘进去的
        {
            sub*=a[pos];
            if(sub>maxx)
                maxx=sub;   //记录最大值
        }
        return ;            //跳出函数
    }
    if(a[pos]<9)            //没到最后一位，且这一位比9小
    {
        a[pos+1]=a[pos+1]-1;  //借位
        sub*=9;               //乘积项乘上当前位    
        if(sub>maxx)
            maxx=sub;
        getmaxx(a,ws,pos+1);  //计算下一位
        for(int i=ws-1;i>=pos+1;i--) //当算出结果后回溯
        {                            //将当前位之后的所有处理的数字都除下去，回到刚刚只乘了不大于pos的对应位上的数字的情况
            if(a[i]!=0)
                sub/=a[i];
        }
        sub/=9;                      //把9除下去，换上pos原本的值，表明当前位不做变化
        sub*=a[pos];
        a[pos+1]=(a[pos+1]+1)%10;    //把借位补回去
        if(sub>maxx)
            maxx=sub;                //sub发生了变化，更新maxx（其实我觉得只要最后算出结果更新最大值即可，但是为了保险在每一次sub发生变化时就更新maxx）
        getmaxx(a,ws,pos+1);         //继续计算下一位
    }
    else                             //当前位本身就是9，不需要借位就乘上当前位再计算下一位
    {
        sub*=a[pos];
        if(sub>maxx)
            maxx=sub;
        getmaxx(a,ws,pos+1);
        for(int i=ws-1;i>=pos+1;i--) //回溯，不用补借位
        {
            if(a[i]!=0)
                sub/=a[i];
        }
        sub/=9;
        sub*=a[pos];
        if(sub>maxx)
            maxx=sub;
        getmaxx(a,ws,pos+1);
    }
}
int main()
{
    int a[10]={0};
    long long int n=0;
    cin>>n;
    int ws=getws(n);
    if(n==0)                  //这一步是多余的，n的范围没有0
        cout<<"0"<<endl;
    else
    {
        for(int i=0;i<ws;i++) //计算出n的每一位放入a数组
        {
            a[i]=n%10;
            n/=10;
        }
        getmaxx(a,ws,0);
        cout<<maxx<<endl;
    }
    return 0;
}

方法二：

#include<iostream>
using namespace std;
long long int maxx(long long int x,long long int y)
{
    if(x>y)
        return x;
    else
        return y;
}
long long int dfs(long long int n)
{
    if(n<10)
        return maxx(1,n);
    return maxx((n%10)*dfs(n/10),9*dfs(n/10-1));
}
int main()
{
    long long int n=0;
    cin>>n;
    cout<<dfs(n)<<endl;
    return 0;
}