C - Select Mul 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300

問題文

整数 N が与えられます。N の各桁の数字を取り出して並べ(並べる順序は好きに変えてよい)、2 つの正整数に分離することを考えましょう。

例えば、123 という整数に対しては以下の 6 通りの分離の仕方が考えられます。

  • 123
  • 213
  • 132
  • 312
  • 231
  • 321

なお、ここで分離されたあとの 2 整数に leading zero が含まれていてはなりません。例えば、101 という整数を 1012 つに分離することはできません。また上述の「正整数に分離する」という条件より、1011102 つに分離することもできません。

適切に N を分離したとき、分離後の 2 数の積の最大値はいくらになりますか?

制約

  • N1 以上 10^9 以下の整数
  • N には 0 でない桁が 2 つ以上含まれる

入力

入力は以下の形式で標準入力から与えられる。

N

出力

分離後の 2 数の積の最大値を出力せよ。


入力例 1

123

出力例 1

63

問題文中にある通り、以下の 6 通りの分離の仕方が考えられます。

  • 123
  • 213
  • 132
  • 312
  • 231
  • 321

積はそれぞれ 36, 63, 26, 62, 23, 32 であり、この中の最大値は 63 です。


入力例 2

1010

出力例 2

100

考えられる分離の仕方は以下の 2 通りです。

  • 1001
  • 1010

いずれの場合にも積は 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