Connection Status:
Competition Arena > ReconstructNumber

ReconstructNumber

TCO19 SRM 752 · 2019-03-04 · by misof

TCO19 SRM 752 · 2019-03-04 · by misof · Dynamic Programming
Class Name: ReconstructNumber
Return Type: String
Method Name: smallest
Arg Types: (string)
Problem Statement

Problem Statement

You are given the String comparisons with n characters. Each character in comparisons is one of '<', '>', '=', and '!'. These represent the relations "is less than", "is greater than", "equals", and "does not equal", respectively.

A positive integer X with n+1 digits (and with no leading zeros) is said to match the given comparisons if all the relations are true for pairs of consecutive digits of X, in order. For example, suppose comparisons is "<<=!". One integer that matches these comparisons is 14770. This is because 1<4, 4<7, 7=7, and 7!=0.

If no (n+1)-digit integer matches all the given comparisons, return an empty String. Otherwise return a String with the digits of the smallest such number.

Constraints

  • comparisons will have between 0 and 2000 characters, inclusive.
  • Each character in comparisons will be one of "<>=!".
Examples
0)
">=!<"
Returns: "10012"

We have 1 > 0, 0 = 0, 0 != 1, and 1 < 2. There are other numbers that match these comparisons, but this one is the smallest of them all.

1)
"====!===="
Returns: "1111100000"
2)
""
Returns: "1"
3)
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>"
Returns: ""
4)
"<"
Returns: "12"

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

Coding Area

Language: C++17 · define a public class ReconstructNumber with a public method string smallest(string comparisons) · 91 test cases · 2 s / 256 MB per case

Submitting as anonymous