Soluție HackerRank pentru Decibinary Numbers. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Decibinary Numbers
Cerinta completa
Let’s talk about binary numbers. We have an [Expresie matematică indisponibilă în copia arhivată]-digit binary number, [Expresie matematică indisponibilă în copia arhivată], and we denote the digit at index [Expresie matematică indisponibilă în copia arhivată] (zero-indexed from right to left) to be [Expresie matematică indisponibilă în copia arhivată]. We can find the decimal value of [Expresie matematică indisponibilă în copia arhivată] using the following formula:
For example, if binary number [Expresie matematică indisponibilă în copia arhivată], we compute its decimal value like so:
Meanwhile, in our well-known decimal number system where each digit ranges from [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată], the value of some decimal number, [Expresie matematică indisponibilă în copia arhivată], can be expanded in the same way:
Now that we’ve discussed both systems, let’s combine decimal and binary numbers in a new system we call decibinary! In this number system, each digit ranges from [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată] (like the decimal number system), but the place value of each digit corresponds to the one in the binary number system. For example, the decibinary number [Expresie matematică indisponibilă în copia arhivată] represents the decimal number [Expresie matematică indisponibilă în copia arhivată] because:
Pretty cool system, right? Unfortunately, there’s a problem: two different decibinary numbers can evaluate to the same decimal value! For example, the decibinary number [Expresie matematică indisponibilă în copia arhivată] also evaluates to the decimal value [Expresie matematică indisponibilă în copia arhivată]:
This is a major problem because our new number system has no real applications beyond this challenge!
Consider an infinite list of non-negative decibinary numbers that is sorted according to the following rules:
- The decibinary numbers are sorted in increasing order of the decimal value that they evaluate to.
- Any two decibinary numbers that evaluate to the same decimal value are ordered by increasing decimal value, meaning the equivalent decibinary values are strictly interpreted and compared as decimal values and the smaller decimal value is ordered first. For example, [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] both evaluate to [Expresie matematică indisponibilă în copia arhivată]. We would order [Expresie matematică indisponibilă în copia arhivată] before [Expresie matematică indisponibilă în copia arhivată] because [Expresie matematică indisponibilă în copia arhivată].
Here is a list of first few decibinary numbers properly ordered:
You will be given [Expresie matematică indisponibilă în copia arhivată] queries in the form of an integer, [Expresie matematică indisponibilă în copia arhivată]. For each [Expresie matematică indisponibilă în copia arhivată], find and print the the [Expresie matematică indisponibilă în copia arhivată] decibinary number in the list on a new line.
Function Description
Complete the decibinaryNumbers function in the editor below. For each query, it should return the decibinary number at that one-based index.
decibinaryNumbers has the following parameter(s):
- x: the index of the decibinary number to return
Input Format
The first line contains an integer, [Expresie matematică indisponibilă în copia arhivată], the number of queries.
Each of the next [Expresie matematică indisponibilă în copia arhivată] lines contains an integer, [Expresie matematică indisponibilă în copia arhivată], describing a query.
Constraints
- [Expresie matematică indisponibilă în copia arhivată]
- [Expresie matematică indisponibilă în copia arhivată]
Subtasks
- [Expresie matematică indisponibilă în copia arhivată] for [Expresie matematică indisponibilă în copia arhivată] of the maximum score
- [Expresie matematică indisponibilă în copia arhivată] for [Expresie matematică indisponibilă în copia arhivată] of the maximum score
- [Expresie matematică indisponibilă în copia arhivată] for [Expresie matematică indisponibilă în copia arhivată] of the maximum score
Output Format
For each query, print a single integer denoting the the [Expresie matematică indisponibilă în copia arhivată] decibinary number in the list. Note that this must be the actual decibinary number and not its decimal value. Use 1-based indexing.
Sample Input 0
5
1
2
3
4
10
Sample Output 0
0
1
2
10
100
Explanation 0
For each [Expresie matematică indisponibilă în copia arhivată], we print the [Expresie matematică indisponibilă în copia arhivată] decibinary number on a new line. See the figure in the problem statement.
Sample Input 1
7
8
23
19
16
26
7
6
Sample Output 1
12
23
102
14
111
4
11
Sample Input 2
10
19
25
6
8
20
10
27
24
30
11
Sample Output 2
102
103
11
12
110
100
8
31
32
5
Limbajul de programare folosit: java8
Cod:
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
static final int LIMIT_D = 19;
static final int LIMIT_S = 300000;
static long[][] f;
static long[] c;
public static void main(String[] args) {
buildF();
buildC();
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
for (int tc = 0; tc < q; tc++) {
long x = sc.nextLong();
System.out.println(solve(x));
}
sc.close();
}
static BigInteger solve(long x) {
int s = findS(x);
long g = x - (s == 0 ? 0 : c[s - 1]);
StringBuilder result = new StringBuilder();
for (int d = LIMIT_D; d >= 1; d--) {
int j = -1;
long prevNumberCount = -1;
long numberCount = 0;
while (numberCount < g) {
j++;
prevNumberCount = numberCount;
numberCount += f[d - 1][s - j * (1 << (d - 1))];
}
result.append(j);
s -= j * (1 << (d - 1));
g -= prevNumberCount;
}
return new BigInteger(result.toString());
}
static int findS(long x) {
int index = Arrays.binarySearch(c, x);
if (index < 0) {
index = -1 - index;
}
return index;
}
static void buildF() {
f = new long[LIMIT_D + 1][LIMIT_S + 1];
for (int d = 0; d <= LIMIT_D; d++) {
for (int s = 0; s <= LIMIT_S; s++) {
if (d == 0) {
if (s == 0) {
f[d][s] = 1;
} else {
f[d][s] = 0;
}
} else {
f[d][s] = 0;
for (int i = 0; i <= 9; i++) {
long nextS = s - i * (1L << (d - 1));
if (nextS >= 0) {
f[d][s] += f[d - 1][(int) nextS];
}
}
}
}
}
}
static void buildC() {
c = new long[LIMIT_S + 1];
long sum = 0;
for (int i = 0; i < c.length; i++) {
sum += f[LIMIT_D][i];
c[i] = sum;
}
}
}
Scor obtinut: 1.0
Submission ID: 464603427
Link challenge: https://www.hackerrank.com/challenges/decibinary-numbers/problem