Score : $300$ points

问题描述

给定一个整数 $N$。考虑将 $N$ 的各位数字进行排列，并将其分割成两个 正整数。

例如，对于整数 $123$，有六种分割方式如下：

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

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

通过最优分割方式能得到的最大可能的两个结果整数之积是多少？

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:44:55