Sort
SRM 535 · 2012-01-31 · by wrong
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
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.
10 Returns: 100000000
First 10 elements of B are: {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000}.
1000000000000000000 Returns: 999999999999999999
The last element.
58 Returns: 100000000100
314159265358979 Returns: 646003042230121105
271828182845904523 Returns: 132558071125756493
Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FoxAndSorting with a public method long long get(long long idx) · 118 test cases · 2 s / 256 MB per case