102212: [AtCoder]ABC221 C - Select Mul

Problem Statement

You are given an integer $N$. Consider permuting the digits in $N$ and separate them into two positive integers.

For example, for the integer $123$, there are six ways to separate it, as follows:

• $12$ and $3$,
• $21$ and $3$,
• $13$ and $2$,
• $31$ and $2$,
• $23$ and $1$,
• $32$ and $1$.

Here, the two integers after separation must not contain leading zeros. For example, it is not allowed to separate the integer $101$ into $1$ and $01$. Additionally, since the resulting integers must be positive, it is not allowed to separate $101$ into $11$ and $0$, either.

What is the maximum possible product of the two resulting integers, obtained by the optimal separation?

Constraints

• $N$ is an integer between $1$ and $10^9$ (inclusive).
• $N$ contains two or more digits that are not $0$.

Input

Input is given from Standard Input in the following format:

$N$

Output

Print the maximum possible product of the two integers after separation.

Sample Input 1

123

Sample Output 1

63

As described in Problem Statement, there are six ways to separate it:

• $12$ and $3$,
• $21$ and $3$,
• $13$ and $2$,
• $31$ and $2$,
• $23$ and $1$,
• $32$ and $1$.

The products of these pairs, in this order, are $36$, $63$, $26$, $62$, $23$, $32$, with $63$ being the maximum.

Sample Input 2

1010

Sample Output 2

100

There are two ways to separate it:

• $100$ and $1$,
• $10$ and $10$.

In either case, the product is $100$.

Sample Input 3

998244353

Sample Output 3

939337176

问题描述

给你一个整数$N$。考虑将$N$的各个数字进行排列，并将它们分为两个正整数。

例如，对于整数$123$，有六种将其分开的方法，如下所示：

• $12$和$3$，
• $21$和$3$，
• $13$和$2$，
• $31$和$2$，
• $23$和$1$，
• $32$和$1$。

分开后的两个整数不能包含前导零。例如，不允许将整数$101$分为$1$和$01$。此外，由于得到的整数必须是正数，因此也不允许将$101$分为$11$和$0$。

通过最佳分离方法，得到的两个整数的最大可能乘积是多少？

约束

• $N$是一个介于$1$和$10^9$（含）之间的整数。
• $N$包含两个或更多个不是$0$的数字。

输入

输入从标准输入以以下格式给出：

$N$

输出

打印分开后得到的两个整数的最大可能乘积。

样例输入1

123

样例输出1

63

如问题描述所述，有六种将其分开的方法：

• $12$和$3$，
• $21$和$3$，
• $13$和$2$，
• $31$和$2$，
• $23$和$1$，
• $32$和$1$。

这些对的乘积，按此顺序，分别为$36$、$63$、$26$、$62$、$23$、$32$，其中$63$是最大的。

样例输入2

1010

样例输出2

100

有两种将其分开的方法：

• $100$和$1$，
• $10$和$10$。

无论哪种情况，乘积都是$100$。

样例输入3

998244353

样例输出3

939337176