102212: [AtCoder]ABC221 C - Select Mul

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $300$ points

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

Input

Output

分数:$300$分

问题描述

给你一个整数$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

加入题单

上一题 下一题 算法标签: