RestoreExpression

SRM 323 · 2006-10-19 · by Pawa

SRM 323 · 2006-10-19 · by Pawa · Brute Force

Show categories

Class Name: RestoreExpression

Return Type: String

Method Name: restore

Arg Types: (string)

Problem Statement

Consider a simple arithmetic expression, A+B=C, where A, B, C are nonnegative integers without leading zeroes. Unfortunately, some digits are unknown and are replaced by the symbol '?'. You task is to restore the expression.

You are given a String expression. The resulting String must contain the same expression, but with the symbols '?' replaced by digits so that the expression is correct. Numbers in the resulting String must not have leading zeroes.

For example, given the string "5+?=?4" you should return "5+9=14".

If multiple solutions exist, return the one with the maximum possible C. If more than one such solution exists, return the one among them that maximizes the value of A. If there is no solution, return "no solution" (quotes for clarity).

Constraints

expression will contain between 5 and 50 characters, inclusive.
expression will be formatted as "A+B=C" (quotes for clarity), where A, B and C are nonnegative integers (without leading zeroes) with some digits possibly replaced by '?'.

Examples

"5+?=?4"
Returns: "5+9=14"

This is the example from the problem statement. 5+9=14 is the only solution.

"?+?=4"
Returns: "4+0=4"

There are five possible solutions, all of which have the same value of C. 4+0=4 maximizes A.

"?+?=?"
Returns: "9+0=9"

"?2+?2=4"
Returns: "no solution"

"??+1=1?"
Returns: "18+1=19"

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

Coding Area

Language: C++17 · define a public class RestoreExpression with a public method string restore(string expression) · 68 test cases · 2 s / 256 MB per case