На вход поступают 2 числа - sum ( 0 <=..<= 128) и n (1 <=..<= 18).
Требуется найти количество чисел с длиной n (дополненные нулями спереди не считаются), сумма разрядов которых = sum.
Примеры (sum n - outp):
5 2 - 5
1 1 - 1
10 10 - 48619
Написала код на основе одного найденного, вылетает один из автоматических тестов("неправильный ответ"), не могу понять что за тест конкретно. Может кто-нибудь объяснить где ошибка в алгоритме?
import java.io.PrintWriter;
import java.util.Scanner;
public class SumOfDigits {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);
int sum, n;
sum = in.nextInt();
n = in.nextInt();
int result = 0;
if (sum == 0 && n == 1) {
result = 1;
} else if (sum == 0 && n > 1){
result = 0;
} else{
result = finalCount(n, sum);
}
out.println(result);
out.close();
}
static int lookup[][] = new int[19][163];
static int countRec(int n, int sum) {
if (n == 0) {
return sum == 0 ? 1 : 0;
}
if (lookup[n][sum] != -1) {
return lookup[n][sum];
}
int ans = 0;
for (int i = 0; i < 10; i++) {
if (sum - i >= 0) {
ans += countRec(n - 1, sum - i);
}
}
return lookup[n][sum] = ans;
}
static int finalCount(int n, int sum) {
for (int i = 0; i < 19; ++i) {
for (int j = 0; j < 163; ++j) {
lookup[i][j] = -1;
}
}
int ans = 0;
for (int i = 1; i <= 9; i++) {
if (sum - i >= 0) {
ans += countRec(n - 1, sum - i);
}
}
return ans;
}
- дз, не для соревнований