Connection Status:
Competition Arena > RevealTriangle

RevealTriangle

SRM 404 · 2008-06-05 · by boba5551

SRM 404 · 2008-06-05 · by boba5551 · Simple Math
Class Name: RevealTriangle
Return Type: String[]
Method Name: calcTriangle
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Suppose there is a triangle of digits like the following: 

74932
1325
457
92
1

Each digit, with the exception of those in the top row, is equal to the last digit of the sum of its upper and upper-right neighboring digits.

You will be given a String[] questionMarkTriangle containing a triangle where only one digit in each row is known and all others are represented by '?'s (see example 0 for clarification). Each element of questionMarkTriangle represents a row of the triangle, and the rows are given from top to bottom. Each element contains exactly one digit ('0'-'9') and the remaining characters are all '?'s. Restore the triangle and return it as a String[] without '?'s.

Constraints

  • questionMarkTriangle will contain between 1 and 50 elements, inclusive.
  • Element i (0 indexed) of questionMarkTriangle will contain exactly n-i characters, where n is the number of elements in questionMarkTriangle.
  • Each element of questionMarkTriangle will contain exactly one digit ('0'-'9') and all others characters will be '?'s.
Examples
0)
{"4??", 
 "?2", 
 "1"}
Returns: {"457", "92", "1" }

Let's substitute '?'s with unknown variables: 4ab c2 1 Having done that, we start solving for the variables from the bottom to the top. First, we know that the last digit of (c + 2) is 1. Therefore, c must be 9: 4ab 92 1 Now we know that the last digit of (4 + a) is 9, which means a is 5: 45b 92 1 And, finally, the last digit of (5 + b) is 2, so b is 7.

1)
{"?????1?", "2?????", "??4??", "?8??", "6??", "?2", "4"}
Returns: {"1111111", "222222", "44444", "8888", "666", "22", "4" }
2)
{"1"}
Returns: {"1" }
3)
{"1????????", "?2??????", "??3????", "???4??", "????5", "6???", "?7?", "8?", "9"}
Returns: {"184090732", "92499705", "1638675", "791432", "60575", "6522", "174", "81", "9" }
4)
{"???2", "??2", "?2", "2"}
Returns: {"0002", "002", "02", "2" }

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

Coding Area

Language: C++17 · define a public class RevealTriangle with a public method vector<string> calcTriangle(vector<string> questionMarkTriangle) · 67 test cases · 2 s / 256 MB per case

Submitting as anonymous