Connection Status:
Competition Arena > LuckySum

LuckySum

SRM 665 · 2015-06-30 · by tehqin

SRM 665 · 2015-06-30 · by tehqin · Brute Force, Greedy
Class Name: LuckySum
Return Type: long
Method Name: construct
Arg Types: (string)
Problem Statement

Problem Statement

A lucky number is a positive integer such that each of its digits is a 4 or a 7. A lucky sum is the sum of two (not necessarily distinct) lucky numbers. Cat loves lucky sums!


Cat has a String note. Each character in note is either a digit or a question mark. A number matches note if it can be produced from note by changing each question mark to a single digit. Note that the number produced this way must not have any leading zeros: after the changes, note[0] must be between '1' and '9', inclusive.


Find and return the smallest lucky sum that matches note. If there are no lucky sums that match note, return -1.

Constraints

  • note will contain between 1 and 14 characters, inclusive.
  • Each character of note will be either a digit ('0'-'9') or a question mark ('?').
  • The first character of note will not be '0'.
  • At least one character of note will be '?'.
Examples
0)
"?"
Returns: 8

4+4=8, which is the smallest lucky sum.

1)
"?1"
Returns: 11

4+7=11

2)
"4?8"
Returns: 448

4+444=448

3)
"2??"
Returns: -1

The numbers that match this note are the numbers 200 through 299. None of these numbers is a lucky sum.

4)
"??????????????"
Returns: 11888888888888

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

Coding Area

Language: C++17 · define a public class LuckySum with a public method long long construct(string note) · 203 test cases · 2 s / 256 MB per case

Submitting as anonymous