EnclosedArea
SRM 850 · 2023-10-25 · by misof
Problem Statement
Below is a simple ASCII art showing one specific rendering of the digits 0 through 9 on a seven-segment digital display. This particular "font" is the one used in this problem.
0 1 2 3 4 5 6 7 8 9 +-+ + + +-+ +-+ + + +-+ +-+ +-+ +-+ +-+ | | | | | | | | | | | | | | + + + + +-+ +-+ +-+ +-+ +-+ + + +-+ +-+ | | | | | | | | | | | | | +-+ + + +-+ +-+ + + +-+ +-+ + + +-+ +-+
Note that if the individual segments that form a digit touch at their endpoints, some of the digits enclose one or two areas completely: the digits 0, 6 and 9 enclose one area each, the digit 8 encloses two.
This generalizes naturally to arbitrary positive integers. For example, a digital representation of the number 1000 contains three enclosed areas, 8968 contains six, and 12345 contains none.
For a given value E we now consider the sequence of all positive integers that have exactly E enclosed areas in their digital representation. We will assign ordinal numbers to the elements of this sequence, starting with number 0 for the smallest such integer.
Given E and N, return the integer that will have the ordinal number N in the above sequence.
Notes
- For the constraints given below it is guaranteed that the return value is smaller than 10^18 (and therefore fits into a signed 64-bit integer).
Constraints
- E will be between 0 and 20, inclusive.
- N will be between 0 and 10^9, inclusive.
1 0 Returns: 6
We want the smallest positive integer with one enclosed area. That integer is 6. (Note that 0 is not a positive integer.)
7 1 Returns: 8088
Here we want the second smallest positive integer with 7 enclosed areas. (The smallest is 6888.)
7 8 Returns: 8898
The first eight integers in this sequence (i.e., those with ordinals 0-7) are 6888, 8088, 8688, 8808, 8868, 8880, 8886, and 8889. The next one is the one we seek.
0 123456789 Returns: 17125735114
Integers with no enclosed areas are simply integers written only using digits 1, 2, 3, 4, 5, and 7. There is a fairly obvious relationship between this sequence and integers written in base 6. Note that the return value does not fit into a 32-bit integer. Watch out for overflows!
4 123456 Returns: 805519
Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EnclosedArea with a public method long long construct(int E, int N) · 70 test cases · 2 s / 256 MB per case