2

На вход поступают 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;
}
  • дз, не для соревнований
8
  • Что вы подразумеваете под "суммой элементов"? Сумма разрядов числа? Или сумма каких-то найденных чисел должна равняться sum?
    – Eluv
    Commented 6 апр. 2019 в 11:51
  • а можете привести 2-3 примера чисел на входе и корректного ожидаемого результата? Commented 6 апр. 2019 в 11:52
  • @Eluv да, разрядов числа Commented 6 апр. 2019 в 11:57
  • @Дмитрий в вопрос добавила те, что в исходном задании как пример приведены Commented 6 апр. 2019 в 11:58
  • Алгоримт плохо реализован, с нарастанием значений моя машинка перестает справляться и вычисления становятся довольно таки долгими, например, 60 на 9 занимает 17 сек времени, а 61 на 10 занимает около 1 мин 15 сек !!! Нужно перестроить алгоритм
    – GinTasan
    Commented 6 апр. 2019 в 12:17

2 ответа 2

2

Простой алгоритм с мемоизацией на Python работает быстро ideone

import functools

@functools.lru_cache(328)
def digsum(summ, leng, mindig=1):
    if (leng == 1):
        return 1 if (10 > summ >= 0) else 0
    return sum([digsum(summ - i, leng - 1, 0) for i in range(mindig, min(10, summ + 1))])

print(digsum(91, 18))

На Java можно создать словарь, в который по ключу-параметрам выдаст уже имеющееся решение, или вашу lookup-таблицу использовать

Вот в таком виде, может, проще разобраться, если с Python не сталкивались:

dict = {}

def digsum(summ, leng, mindig=1):
    t = summ * 100000 + leng * 100 + mindig
    if t in dict:
        return dict[t]
    if (leng == 1):
        if (10 > summ >= 0):
            return 1
        else:
            return 0
    res = 0
    for i in range(mindig, min(10, summ + 1)):
        res += digsum(summ - i, leng - 1, 0)
    dict[t] = res
    return res

print(digsum(91, 18))
3
  • не проходит один из тестов, который код из вопроса проходит. Доступа к тестам нет, так что не скажу точно какой. Для s = 0 тоже не пройдет, но его я исправила Commented 6 апр. 2019 в 13:58
  • @maria_rheon Упустил ограничение на цифру: (10 > summ >= 0 )
    – MBo
    Commented 6 апр. 2019 в 14:06
  • Спасибо, все тесты прошли. Пойду попробую исправить на джаве. Commented 6 апр. 2019 в 14:38
0
    import java.util.Scanner;
import java.util.stream.LongStream;

public class SumOfDigits {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);        
        int sum = in.nextInt();
        int n = in.nextInt();

        long limit = (long) Math.pow(10, n);
        long count = LongStream.range(limit / 10, limit)
                .parallel()
                .filter(i -> calculateSum(i) == sum)
                .count();

        System.out.println(count);

    }

    private static int calculateSum(long x) {
        int sum = 0;
        for (long i = x; i > 0; i /= 10) sum += i % 10;
        return sum;
    }
}

Я бы использовал стрим хотя бы потому, что он позволяет легко распаралелить задачу, а это дает огромный прирост в производительности расчетов. Возможно для минимальных значений нужно добавит условие, но это уже дело техники.

2
  • Не стоит считать все суммы. Даже со всемогущими стримами обсчитать 9*10^17 значений будет не так уж быстро.
    – MBo
    Commented 6 апр. 2019 в 15:39
  • @MBo у каждого рано или поздно возникает понимание того, что использование близких к железу языков и быстрых технологий не компенсирует отсутствия алгоритмической базы :)
    – extrn
    Commented 6 апр. 2019 в 15:43

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.