Un problème d'un concours de programmation ... Digit Sums

Question

J'ai besoin d'aide pour résoudre problem N from this earlier competition:

Problème N: Digit

Sums

Compte tenu des nombres entiers positifs 3 A, B et C, trouver comment de nombreux nombres entiers positifs moins ou égal à a, lorsqu'il est exprimé dans base B, ont des chiffres qui somme à C.

d'entrée se composent d'une série de lignes, chacune contenant trois nombres entiers, A, B et C, 2

La sortie sera le nombre de chiffres, pour chaque ligne d'entrée (il doit être donné dans la base 10).

entrée d'échantillon

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

exemple de sortie

10 
3 
189 
45433800 
666303 

Les règles pertinentes:

1. Lire toutes les entrées du clavier, c'est-à-dire utiliser stdin, System.in, cin ou équivalent. Les entrées seront redirigées à partir d'un fichier pour former la contribution à votre soumission.

2. Ecrivez toutes les sorties à l'écran, c'est-à-dire, utilisez stdout, System.out, cout ou équivalent. N'écrivez pas au stderr. N'utilisez PAS, ni même n'incluez aucun module permettant une manipulation directe de l'écran, tel que conio, Crt ou quoi que ce soit de similaire. La sortie de votre programme est redirigée vers un fichier pour vérification ultérieure. L'utilisation d'E/S directes signifie qu'une telle sortie n'est pas redirigée et ne peut donc pas être vérifiée. Cela pourrait signifier qu'un programme correct est rejeté!

3. Sauf indication contraire, tous les entiers de l'entrée s'inséreront dans un mot d'ordinateur standard de 32 bits. Les entiers adjacents sur une ligne seront séparés par un ou plusieurs espaces.

Bien sûr, il est juste de dire que je devrais en savoir plus avant d'essayer de résoudre ce problème, mais j'apprécierions vraiment si quelqu'un m'a dit ici comment faire.

Merci d'avance, John.

Answer 1

D'autres personnes ont fait remarquer une solution triviale: parcourir tous les nombres de 1 à A. Mais ce problème, en fait, peut être résolu en temps presque constant: O(length of A), qui est O(log(A)).

1. Le code fourni est pour la base 10. L'adapter à une base arbitraire est trivial.
2. Pour atteindre l'estimation ci-dessus pour le temps, vous devez ajouter memorization à la récursivité. Faites-moi savoir si vous avez des questions sur cette partie.

Maintenant, la fonction récursive elle-même. Écrit en Java, mais tout devrait fonctionner en C#/C++ sans aucun changement. C'est gros, mais surtout à cause des commentaires où j'essaie de clarifier l'algorithme.

// 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; 
} 

fonction d'aide

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

Maintenant, nous allons écrire un petit testeur

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); 

Vous pouvez écrire plus tester complète vérifier toutes les valeurs de A, mais solution globale semble être correcte. (J'ai essayé plusieurs A et C aléatoires.)

N'oubliez pas, vous ne pouvez pas tester la solution pour A == 1000000000 sans mémorisation: ça va tourner trop longtemps. Mais avec la mémorisation, vous pouvez le tester même pour A == 10^1000.

modifier
juste pour prouver un concept, la mémorisation de l'homme pauvre. (en Java, dans d'autres langues, les hashtables sont déclarés différemment) Mais si vous voulez apprendre quelque chose, il vaudrait mieux essayer de le faire vous-même.

// 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

Ceci n'est pas la solution complète (pas d'analyse d'entrée). Pour obtenir le nombre dans la base B, prenez de façon répétée le modulo B, puis divisez par B jusqu'à ce que le résultat soit 0. Cela calcule effectivement le chiffre de base B à partir de la droite, puis décale le nombre à droite.

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; 
} 

Ceci est une approche par force brute. Il peut être possible de calculer cela plus rapidement en déterminant quels ensembles de chiffres de base B s'additionnent à C, en les arrangeant dans toutes les permutations inférieures à A, et en retraçant ensuite cela pour créer le nombre original.

Answer 3

Yum.

Essayez ceci:

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++; 
} 

C'est votre algorithme de base pour une ligne. Maintenant, vous enveloppez ceci dans une autre boucle For pour chaque ligne d'entrée que vous avez reçue, précédée par la phase de collecte d'entrée elle-même. Ce processus peut être simplifié, mais je n'ai pas envie de coder toute votre réponse pour voir si mon algorithme fonctionne, et cela semble juste alors que les astuces les plus simples sont plus difficiles à passer par l'inspection.

La façon dont cela fonctionne est de diviser modulo par les puissances de la base. Exemple simple, 1234 en base 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 

Un exemple plus difficile à comprendre par l'inspection serait le même nombre dans la base 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. 

Donc 1234 dans la base 12 serait écrite 86A. Vérifiez les maths:

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

Amusez-vous à faire le reste du code.

Answer 4

est ici la même solution récursive memoized que Rybak a affiché, mais avec une mise en œuvre plus simple, à mon humble avis:

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; 
}