18级暑假个人赛(二) 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 1
to n

.

Input

The only input line contains the integer n
(1≤n≤2⋅109

).

Output

Print the maximum product of digits among all integers from 1
to n

.

Sample Input
Input

390

Output

216

Input

7

Output

7

Input

1000000000

Output

387420489

Hint

In the first example the maximum product is achieved for 389
(the product of digits is 3⋅8⋅9=216

).

In the second example the maximum product is achieved for 7
(the product of digits is 7

).

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

题目思想并不难，但如果想错了方向就没了，比赛的时候就想着直接找规律输出答案，思考错了方向。
思路：每次更改后面一位变为9，寻找最大值，比如390->389->299……
代码：(注意要用G++17交，不然有可能会WA 7）

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define mem(a, b) memset(a, b, sizeof a)
#define IN freopen("in.txt", "r", stdin)
#define DEBUG(a) cout << (a) << endl
typedef long long ll;
const int INF = 0x3f3f3f3f;
int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int main()
{
     int i,n,m,j,k=1,l,max1=1;
    scanf("%d",&n);
    m=n;max1=1;k=1;
    while(m>0)
    {
        j=m%10;
        m=m/10;
        max1=max1*j;
    }
    for(i=1;;i++)
    {
        m=n; int ans=1;
        l=pow(10,i);
        m=(m/l-1)*l;
        if(m<0)break;
        m=m+l-1;
        while(m>0)
        {
        j=m%10;
        m=m/10;
        ans=ans*j;
        }
        max1=max(max1,ans);
    }
    printf("%d\n",max1);
    return 0;
}