Statistics

Problem Statement for "Sort"

Problem Statement

Fox Jiro and Eel Saburo are good friends. Saburo uses a strange way to compare integers. Please help Jiro understand it.


For a positive integer n, let d(n) be the sum of its digits in base 10. For example, d(407) = 4+0+7 = 11.


When comparing two different integers x and y, Saburo first compares their sums of digits, i.e., the values d(x) and d(y). If they differ, the one with the smaller sum is smaller. For example, for Saburo 50 is smaller than 16, because d(50) < d(16).


If the numbers have the same sum of digits, Saburo compares them lexicographically (i.e., as strings). For example, for Saburo the number 111 is smaller than the number 3, because d(111) = d(3) and "111" < "3". Also, the number 470 is smaller than 4700, because "470" < "4700".


Let A be the sequence of integers {0, 1, ..., 999999999999999998, 999999999999999999 (10^18 - 1)}. Let B be the sequence A, ordered according to Saburo's rules. You are given a long idx, representing a 1-based index into B. Return the corresponding element of B.

Definition

Class:
FoxAndSorting
Method:
get
Parameters:
long
Returns:
long
Method signature:
long get(long idx)
(be sure your method is public)

Notes

  • Given two distinct strings A and B, we say that A is lexicographically smaller than B if either A is a prefix of B, or A has a smaller character than B on the first position on which they differ.

Constraints

  • idx will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.

Examples

  1. 10

    Returns: 100000000

    First 10 elements of B are: {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000}.

  2. 1000000000000000000

    Returns: 999999999999999999

    The last element.

  3. 58

    Returns: 100000000100

  4. 314159265358979

    Returns: 646003042230121105

  5. 271828182845904523

    Returns: 132558071125756493

  6. 1

    Returns: 0

  7. 2

    Returns: 1

  8. 3

    Returns: 10

  9. 4

    Returns: 100

  10. 5

    Returns: 1000

  11. 6

    Returns: 10000

  12. 7

    Returns: 100000

  13. 8

    Returns: 1000000

  14. 9

    Returns: 10000000

  15. 11

    Returns: 1000000000

  16. 12

    Returns: 10000000000

  17. 13

    Returns: 100000000000

  18. 14

    Returns: 1000000000000

  19. 15

    Returns: 10000000000000

  20. 16

    Returns: 100000000000000

  21. 17

    Returns: 1000000000000000

  22. 18

    Returns: 10000000000000000

  23. 19

    Returns: 100000000000000000

  24. 20

    Returns: 100000000000000001

  25. 21

    Returns: 10000000000000001

  26. 22

    Returns: 100000000000000010

  27. 23

    Returns: 1000000000000001

  28. 24

    Returns: 10000000000000010

  29. 25

    Returns: 100000000000000100

  30. 26

    Returns: 100000000000001

  31. 27

    Returns: 1000000000000010

  32. 28

    Returns: 10000000000000100

  33. 29

    Returns: 100000000000001000

  34. 30

    Returns: 10000000000001

  35. 40

    Returns: 100000000000100000

  36. 45

    Returns: 1000000000010000

  37. 50

    Returns: 1000000000100

  38. 55

    Returns: 100000000010000000

  39. 60

    Returns: 10000000010000

  40. 65

    Returns: 100000001

  41. 70

    Returns: 10000000100000

  42. 75

    Returns: 10000001

  43. 80

    Returns: 1000000100000

  44. 85

    Returns: 100000010000000000

  45. 90

    Returns: 10000010000

  46. 95

    Returns: 1000001000000000

  47. 100

    Returns: 10000100

  48. 110

    Returns: 100001000000000000

  49. 120

    Returns: 10001000000000

  50. 130

    Returns: 100100000

  51. 140

    Returns: 101

  52. 160

    Returns: 110000

  53. 180

    Returns: 20000000

  54. 200

    Returns: 100000000000000200

  55. 220

    Returns: 100000000000011000

  56. 240

    Returns: 100000000000110000

  57. 266

    Returns: 10000000000110000

  58. 271

    Returns: 100000000002000

  59. 283

    Returns: 10000000001000100

  60. 299

    Returns: 100000000011000

  61. 305

    Returns: 1000000000200

  62. 331

    Returns: 100000000100100000

  63. 372

    Returns: 10000000100010

  64. 400

    Returns: 100000001100000000

  65. 999999999999999999

    Returns: 999999999999999998

  66. 999999999999999998

    Returns: 999999999999999989

  67. 999999999999999997

    Returns: 999999999999999899

  68. 999999999999999996

    Returns: 999999999999998999

  69. 999999999999999995

    Returns: 999999999999989999

  70. 999999999999999994

    Returns: 999999999999899999

  71. 999999999999999993

    Returns: 999999999998999999

  72. 999999999999999992

    Returns: 999999999989999999

  73. 999999999999999991

    Returns: 999999999899999999

  74. 999999999999999990

    Returns: 999999998999999999

  75. 999999999999999989

    Returns: 999999989999999999

  76. 999999999999999988

    Returns: 999999899999999999

  77. 999999999999999987

    Returns: 999998999999999999

  78. 999999999999999986

    Returns: 999989999999999999

  79. 999999999999999985

    Returns: 999899999999999999

  80. 999999999999999984

    Returns: 998999999999999999

  81. 999999999999999983

    Returns: 989999999999999999

  82. 999999999999999982

    Returns: 899999999999999999

  83. 999999999999999981

    Returns: 999999999999999997

  84. 999999999999999980

    Returns: 999999999999999988

  85. 702750078829924099

    Returns: 151811425483786996

  86. 230953084107792107

    Returns: 454453885290145050

  87. 266414747660238052

    Returns: 815282934752941300

  88. 13533880734584352

    Returns: 523123513200613539

  89. 475043313880445062

    Returns: 745580988175202117

  90. 404801417921961925

    Returns: 560428585723271445

  91. 59787019843024470

    Returns: 411195463053466004

  92. 370938904326123640

    Returns: 47806263259042928

  93. 664488589083249559

    Returns: 77184760889041736

  94. 410038224744286824

    Returns: 71136738684008178

  95. 645715718829286376

    Returns: 199124202964699814

  96. 775948717519523578

    Returns: 864255097727490087

  97. 175813456102191246

    Returns: 149864602031219428

  98. 339425279788394851

    Returns: 437028600666943462

  99. 358204279145179049

    Returns: 131975170468013669

  100. 65072632448898308

    Returns: 108335072636241291

  101. 995360179298504262

    Returns: 964485329678959972

  102. 736967646002262449

    Returns: 413554730843983769

  103. 447954609775467455

    Returns: 892095095618870002

  104. 357896124468326036

    Returns: 1238265095998154

  105. 484061008196541172

    Returns: 1099398631658346

  106. 46205260633269038

    Returns: 9547801123241049

  107. 274835172267658833

    Returns: 217363843864830800

  108. 494217919348875195

    Returns: 392806100865225969

  109. 506726110561802199

    Returns: 732105590497275096

  110. 621221024934183293

    Returns: 392992878101631808

  111. 34417438182415845

    Returns: 283728220130186051

  112. 120198504290114684

    Returns: 173906299032322027

  113. 32475118014047323

    Returns: 112207300158039953

  114. 276414099925016510

    Returns: 260467144693404464

  115. 4356738488474

    Returns: 1010160321025206

  116. 5467

    Returns: 11000001010000

  117. 423472340572489

    Returns: 515100474100360220

  118. 4527457444521411

    Returns: 110335149203082512

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: