Statistics

Problem Statement for "EnclosedArea"

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.

Definition

Class:
EnclosedArea
Method:
construct
Parameters:
int, int
Returns:
long
Method signature:
long construct(int E, int N)
(be sure your method is public)

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.

Examples

  1. 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.)

  2. 7

    1

    Returns: 8088

    Here we want the second smallest positive integer with 7 enclosed areas. (The smallest is 6888.)

  3. 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.

  4. 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!

  5. 4

    123456

    Returns: 805519

  6. 0

    999999998

    Returns: 243121245343

  7. 0

    67135996

    Returns: 7354542445

  8. 0

    55

    Returns: 132

  9. 1

    1000000000

    Returns: 31755339173

  10. 1

    612881816

    Returns: 17413516711

  11. 1

    43

    Returns: 129

  12. 2

    999999997

    Returns: 11973547951

  13. 2

    550233048

    Returns: 5139172027

  14. 2

    49

    Returns: 266

  15. 3

    999999999

    Returns: 5963032275

  16. 3

    660954037

    Returns: 3925027359

  17. 3

    5

    Returns: 108

  18. 4

    999999999

    Returns: 5117038107

  19. 4

    707195253

    Returns: 3596177097

  20. 4

    3

    Returns: 388

  21. 5

    999999994

    Returns: 5584756787

  22. 5

    672808

    Returns: 6269093

  23. 5

    33

    Returns: 3898

  24. 6

    1000000000

    Returns: 7056748784

  25. 6

    777236230

    Returns: 5816861414

  26. 6

    69

    Returns: 9988

  27. 7

    999999993

    Returns: 9748915058

  28. 7

    985054900

    Returns: 9639674380

  29. 7

    40

    Returns: 38868

  30. 8

    999999999

    Returns: 16910811060

  31. 8

    247011136

    Returns: 5786877186

  32. 8

    30

    Returns: 83888

  33. 9

    999999998

    Returns: 30355869818

  34. 9

    474831280

    Returns: 16604825860

  35. 9

    30

    Returns: 268888

  36. 10

    999999993

    Returns: 64886760309

  37. 10

    602310884

    Returns: 41018887805

  38. 10

    47

    Returns: 868889

  39. 11

    999999998

    Returns: 98909099050

  40. 11

    645292743

    Returns: 84168832288

  41. 11

    43

    Returns: 2888808

  42. 12

    999999996

    Returns: 268566668867

  43. 12

    256215501

    Returns: 86889661979

  44. 12

    93

    Returns: 8880808

  45. 13

    999999993

    Returns: 663979886989

  46. 13

    134754254

    Returns: 106800607868

  47. 13

    42

    Returns: 26888888

  48. 14

    999999994

    Returns: 1006809580800

  49. 14

    389595110

    Returns: 728618988698

  50. 14

    74

    Returns: 88088088

  51. 15

    999999999

    Returns: 3287888889458

  52. 15

    545789266

    Returns: 1888861607686

  53. 15

    69

    Returns: 289888888

  54. 16

    999999997

    Returns: 8087881480866

  55. 16

    104258988

    Returns: 1688888008973

  56. 16

    83

    Returns: 880880888

  57. 17

    999999996

    Returns: 18614880876888

  58. 17

    995373686

    Returns: 18601858786888

  59. 17

    89

    Returns: 3888868888

  60. 18

    999999998

    Returns: 60858698488869

  61. 18

    234670574

    Returns: 18688986900968

  62. 18

    60

    Returns: 8388888888

  63. 19

    999999994

    Returns: 89069888996860

  64. 19

    830082728

    Returns: 88809189888601

  65. 19

    53

    Returns: 18888898888

  66. 20

    999999998

    Returns: 386078880890898

  67. 20

    724619712

    Returns: 287889082889808

  68. 20

    36

    Returns: 78888888888

  69. 20

    1000000000

    Returns: 386078880891888

  70. 0

    999918851

    Returns: 243115421537

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: