OperationsArrangement

SRM 285 · 2006-01-24 · by Andrew_Lazarev

SRM 285 · 2006-01-24 · by Andrew_Lazarev · Brute Force, Dynamic Programming, Math

Show categories

Class Name: OperationsArrangement

Return Type: String

Method Name: arrange

Arg Types: (string)

Problem Statement

You are given a sequence of digits. You must insert either a '+' (addition) operator or a '*' (multiplication) operator between each pair of adjacent digits in such a way that minimizes the value of the resulting expression. The expression should be evaluated using the standard order of operations (multiplication has a higher precedence than addition).

You will be given a String sequence. Perform the procedure described above on the sequence and return the resulting expression. If there are several possible answers, return the one that comes first lexicographically. Note that '*' comes before '+' lexicographically.

Constraints

sequence will contain between 2 and 50 characters, inclusive.
Each character in sequence will be a digit ('0'-'9').

Examples

"222"
Returns: "2*2+2"

The minimal result can be obtained in three ways: "2*2+2", "2+2*2" and "2+2+2". The first one comes first lexicographically.

"322"
Returns: "3+2*2"

"307"
Returns: "3*0*7"

"391118571"
Returns: "3+9*1*1*1+8+5+7*1"

"111221911212"
Returns: "1*1*1*2*2*1+9*1*1+2*1*2"

Submissions are judged against all 135 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class OperationsArrangement with a public method string arrange(string sequence) · 135 test cases · 2 s / 256 MB per case