Проблемы от конкуренции программирования ... Digit сумм

Question

Мне нужна помощь в решении problem N from this earlier competition:

Задача N: Digit Сумма

давались 3 целые положительные числа A, B и C, найти как многие положительные целые числа меньше, чем или равны А, при экспрессии в базовой B, имеют цифры, сумма которых равна C.

вход будет состоять из серии , каждый из которых содержит три целых числа, A, B и C, 2 ≤ B ≤ 100, 1 ≤ A, C ≤ 1,000,000,000. Цифры A, B и C приведены в основании 10 и разделены одним или несколькими заготовками. Входной сигнал заканчивается линией, содержащей три нулей.

Выходной сигнал будет состоять из числа цифр, для каждой входной линии (в базе 10 должно быть указано ).

ввода образца

100 10 9 
100 10 1 
750000 2 2 
1000000000 10 40 
100000000 100 200 
0 0 0 

выходные Образец

10 
3 
189 
45433800 
666303 

Соответствующие правила:

1. Прочтите все данные с клавиатуры, т. Е. Используйте stdin, System.in, cin или аналогичные. Ввод будет перенаправлен из файла, чтобы сформировать ввод для вашего представления.

2. Запишите все выходные данные на экран, то есть используйте stdout, System.out, cout или их эквивалент. Не пишите на stderr. НЕ используйте или даже не включайте любой модуль, который позволяет напрямую манипулировать экраном, например conio, Crt или что-то подобное. Вывод из вашей программы перенаправляется в файл для последующей проверки. Использование прямого ввода-вывода означает, что такой вывод не перенаправляется и, следовательно, не может быть проверен. Это может означать, что правильная программа отвергается!

3. Если не указано иное, все целые числа на входе будут вписываться в стандартное 32-разрядное компьютерное слово. Смежные целые числа в строке будут разделены одним или несколькими пробелами.

Конечно, это справедливо сказать, что я должен узнать больше, прежде чем пытаться решить эту проблему, но я бы очень признателен, если кто-то здесь сказал мне, как это делается.

Заранее спасибо, Джон.

Answer 1

Другие люди указали на тривиальное решение: перечислить все числа от 1 до A. Но эта проблема, фактически, может быть решена почти в постоянное время: O(length of A), что составляет O(log(A)).

1. Предоложенный код для основания 10. Адаптация его к произвольной базе тривиальна.
2. Чтобы достигнуть вышеуказанной оценки времени, вам нужно добавить memorization в рекурсию. Дайте мне знать, если у вас есть вопросы об этой части.

Теперь, рекурсивная функция сама. Написано на Java, но все должно работать на C#/C++ без каких-либо изменений. Он большой, но в основном из-за комментариев, где я пытаюсь прояснить алгоритм.

// returns amount of numbers strictly less than 'num' with sum of digits 'sum' 
// pay attention to word 'strictly' 
int count(int num, int sum) { 
    // no numbers with negative sum of digits 
    if (sum < 0) { 
     return 0; 
    } 

    int result = 0; 

    // imagine, 'num' == 1234 
    // let's check numbers 1233, 1232, 1231, 1230 manually 
    while (num % 10 > 0) { 
     --num; 

     // check if current number is good 
     if (sumOfDigits(num) == sum) { 
      // one more result 
      ++result; 
     } 
    } 

    if (num == 0) { 
     // zero reached, no more numbers to check 
     return result; 
    } 

    num /= 10; 

    // Using example above (1234), now we're left with numbers 
    // strictly less than 1230 to check (1..1229) 
    // It means, any number less than 123 with arbitrary digit appended to the right 
    // E.g., if this digit in the right (last digit) is 3, 
    // then sum of the other digits must be "sum - 3" 
    // and we need to add to result 'count(123, sum - 3)' 

    // let's iterate over all possible values of last digit 
    for (int digit = 0; digit < 10; ++digit) { 
     result += count(num, sum - digit); 
    } 

    return result; 
} 

Вспомогательная функция

// returns sum of digits, plain and simple 
int sumOfDigits(int x) { 
    int result = 0; 
    while (x > 0) { 
     result += x % 10; 
     x /= 10; 
    } 
    return result; 
} 

Теперь, давайте напишем немного тестером

int A = 12345; 
    int C = 13; 

    // recursive solution 
    System.out.println(count(A + 1, C)); 

    // brute-force solution 
    int total = 0; 
    for (int i = 1; i <= A; ++i) { 
     if (sumOfDigits(i) == C) { 
      ++total; 
     } 
    } 
    System.out.println(total); 

Вы можете написать более всесторонний тестер проверки всех значений, но в целом решение представляется правильным. (Я попробовал несколько случайных A и C.)

Не забывайте, вы не можете проверить решение для A == 1000000000 без запоминания: он будет работать слишком долго. Но с запоминанием вы можете проверить его даже на A == 10^1000.

редактировать
Просто, чтобы доказать концепцию, запоминанию бедняка. (в Java, на других языках hashtables объявляются по-разному). Но если вы хотите чему-то научиться, лучше попробовать это сделать самостоятельно.

// hold values here 
private Map<String, Integer> mem; 

int count(int num, int sum) { 
    // no numbers with negative sum of digits 
    if (sum < 0) { 
     return 0; 
    } 

    String key = num + " " + sum; 
    if (mem.containsKey(key)) { 
     return mem.get(key); 
    } 

    // ... 
    // continue as above... 
    // ... 

    mem.put(key, result); 
    return result; 
} 

Answer 2

Это не полное решение (без синтаксического анализа ввода). Чтобы получить номер в базе B, повторно выполняйте по модулю B, а затем делите на B до тех пор, пока результат не станет 0. Это эффективно вычисляет цифру base-B справа, а затем сдвигает число вправо.

int A,B,C; // from input 
for (int x=1; x<A; x++) 
{ 
    int sumDigits = 0; 
    int v = x; 
    while (v!=0) { 
     sumDigits += (v % B); 
     v /= B; 
    } 
    if (sumDigits==C) 
     cout << x; 
} 

Это подход грубой силы. Возможно, это можно будет вычислить быстрее, определив, какие наборы базовых цифр B складываются до C, упорядочивая их во всех перестановках, которые меньше A, а затем работают назад от этого, чтобы создать исходный номер.

Answer 3

Yum.

Попробуйте это:

int number, digitSum, resultCounter = 0; 

for(int i=1; i<=A, i++) 
{ 
    number = i; //to avoid screwing up our counter 
    digitSum = 0; 
    while(number > 1) 
    { 
     //this is the next "digit" of the number as it would be in base B; 
     //works with any base including 10. 
     digitSum += (number % B); 
     //remove this digit from the number, square the base, rinse, repeat 
     number /= B; 
    } 
    digitSum += number; 

    //Does the sum match?  
    if(digitSum == C) 
     resultCounter++; 
} 

Это ваш основной алгоритм для одной строки. Теперь вы переносите это в другой цикл For для каждой введенной строки, которой предшествует сама входная фаза. Этот процесс можно упростить, но мне не хочется кодировать весь ваш ответ, чтобы увидеть, работает ли мой алгоритм, и это выглядит правильно, тогда как более простые трюки сложнее пройти путем проверки.

Как это работает, по модулю деления на силу базы. Простой пример, 1234 в базе 10:

1234 % 10 = 4 
1234/10 = 123 //integer division truncates any fraction 
123 % 10 = 3 //sum is 7 
123/10 = 12 
12 % 10 = 2 //sum is 9 
12/10 = 1 //end condition, add this and the sum is 10 

Более трудный пример, чтобы выяснить обследованием было бы такое же количество в базе 12:

1234 % 12 = 10 //you can call it "A" like in hex, but we need a sum anyway 
1234/12 = 102 
102 % 12 = 6 // sum 16 
102/12 = 8 
8 % 12 = 8 //sum 24 
8/12 = 0 //end condition, sum still 24. 

Так 1234 в базе 12 будет написано 86А. Проверьте математику:

8*12^2 + 6*12 + 10 = 1152 + 72 + 10 = 1234 

Удачи, обертывая остальную часть кода вокруг этого.

Answer 4

Вот же memoized рекурсивное решения, которое отправило Рыбак, но с более простой реализацией, по моему скромному мнению:

HashMap<String, Integer> cache = new HashMap<String, Integer>(); 

int count(int bound, int base, int sum) { 
    // No negative digit sums. 
    if (sum < 0) 
     return 0; 

    // Handle one digit case. 
    if (bound < base) 
     return (sum <= bound) ? 1 : 0; 

    String key = bound + " " + sum; 
    if (cache.containsKey(key)) 
     return cache.get(key); 

    int count = 0; 
    for (int digit = 0; digit < base; digit++) 
     count += count((bound - digit)/base, base, sum - digit); 

    cache.put(key, count); 
    return count; 
}