Largest Expression
Autumn Tournament (2017)
Submission name: izraz.cpp
Problem summary
Reorder three nonnegative integers and put one operator between each adjacent pair. Choose from +, -, *; an operator may be used at most once. Find the greatest value under ordinary arithmetic precedence, without parentheses.
Input
Three integers a, b, c.
Output
The maximum expression value.
Constraints
0 ≤ a, b, c ≤ 100000.
Worked example
First official statement sample.
Input
2 5 1
Output
11
Solution analysis
- Enumerate every ordering of the three numbers and every ordered pair of distinct operators. This gives at most 6 × 6 = 36 expressions.
- Evaluate multiplication before addition or subtraction. If the first operator is multiplication, combine the first two operands; if the second is multiplication, combine the last two. Otherwise evaluate + and - from left to right.
- For 2, 5, 1, the expression 2 * 5 + 1 gives 11. Using + twice or * twice is forbidden, even if it would yield a larger value.
Why it works
Every valid expression has one enumerated number order and one enumerated distinct operator pair. The evaluator follows standard precedence for each possible location of multiplication and left associativity otherwise. Taking the maximum therefore returns exactly the best valid value.
Watch out. Use long long because a product can reach 10^10. Do not add parentheses or reuse an operator.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<limits>
#include<string>
using namespace std;
long long apply(long long a,long long b,char op){
if(op=='+'){
return a+b;
}
if(op=='-'){
return a-b;
}
return a*b;
}
int main(){
array<long long,3>a;
cin>>a[0]>>a[1]>>a[2];
sort(a.begin(),a.end());
const string ops="+-*";
long long best=numeric_limits<long long>::lowest();
do{
for(char first:ops){
for(char second:ops){
if(first==second){
continue;
}
long long value;
// Perform the only possible multiplication first.
if(second=='*'){
value=apply(a[0],a[1]*a[2],first);
}
else{
value=apply(apply(a[0],a[1],first),a[2],second);
}
best=max(best,value);
}
}
}
while(next_permutation(a.begin(),a.end()));
cout<<best<<'\n';
}