C - Select Mul 解説 by en_translator
There are at most \(9! \times 8=2903040\) ways of separations (or \(\frac{2903040}{2}=1451520\) ways when the order of two separated integers are ignored), which is small enough.
Therefore, we can brute force over all possible ways of separations.
When implementing, for example in C++, there is a useful function called next_permutation which is included in the standard library.
Sample code (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
string N; cin >> N;
sort(N.begin(),N.end());
int ans = 0;
do{
for(int i=1; i<N.size(); i++){
string l = "", r = "";
for(int j=0; j<i; j++) l += N[j];
for(int j=i; j<N.size(); j++) r += N[j];
if(l[0]=='0' || r[0]=='0') continue;
ans = max(ans,stoi(l)*stoi(r));
}
}while(next_permutation(N.begin(),N.end()));
cout << ans << endl;
}
With a little more observation, we can see that accepting leading zeros does not affect the answer.
Sample code (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
string N; cin >> N;
sort(N.begin(),N.end());
int ans = 0;
do{
for(int i=1; i<N.size(); i++){
int l = 0, r = 0;
for(int j=0; j<i; j++) l = l*10+N[j]-'0';
for(int j=i; j<N.size(); j++) r = r*10+N[j]-'0';
ans = max(ans,l*r);
}
}while(next_permutation(N.begin(),N.end()));
cout << ans << endl;
}
With more observation, we can see that, when the maximum value is achieved, the separated two variables are monotonically non-increasing when viewed as a sequence of digits.
With this property, we can see that the number of separations that we should inspect are \(2^9\) (or \(2^8\) if the order of the two separated integers are ignored).
When implementing, it would be simple to use bit brute forcing.
Sample code (Python)
N = sorted(input(),reverse=True)
ans = 0
for i in range(1<<len(N)):
l = 0
r = 0
for j in range(len(N)):
if i & (1<<j):
l = l*10+ord(N[j])-ord('0')
else:
r = r*10+ord(N[j])-ord('0')
ans = max(ans,l*r)
print(ans)
投稿日時:
最終更新: