/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 N が与えられます。N の各桁の数字を取り出して並べ（並べる順序は好きに変えてよい）、2 つの正整数に分離することを考えましょう。
例えば、123 という整数に対しては以下の 6 通りの分離の仕方が考えられます。
- 12 と 3
- 21 と 3
- 13 と 2
- 31 と 2
- 23 と 1
- 32 と 1
なお、ここで分離されたあとの 2 整数に leading zero が含まれていてはなりません。例えば、101 という整数を 1 と 01 の 2 つに分離することはできません。また上述の「正整数に分離する」という条件より、101 を 11 と 0 の 2 つに分離することもできません。
適切に N を分離したとき、分離後の 2 数の積の最大値はいくらになりますか？
制約
- N は 1 以上 10^9 以下の整数
- N には 0 でない桁が 2 つ以上含まれる
入力
入力は以下の形式で標準入力から与えられる。
N
出力
分離後の 2 数の積の最大値を出力せよ。
入力例 1
123
出力例 1
63
問題文中にある通り、以下の 6 通りの分離の仕方が考えられます。
- 12 と 3
- 21 と 3
- 13 と 2
- 31 と 2
- 23 と 1
- 32 と 1
積はそれぞれ 36, 63, 26, 62, 23, 32 であり、この中の最大値は 63 です。
入力例 2
1010
出力例 2
100
考えられる分離の仕方は以下の 2 通りです。
- 100 と 1
- 10 と 10
いずれの場合にも積は 100 となります。
入力例 3
998244353
出力例 3
939337176
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