USACO DEC06 Problem 'dream' Analysis

by Rob Kolstad

The essence of this problem is the count of all the digits of numbers in an interval. One can imagine using a system program to convert digits to characters and then counting those, but the problem was set up to preclude this working for the larger test cases.

The counting part is easy:

      foreach (digit in the number) {
          count[digit]++;
      }
but how to isolate the digits?

The key observation is that n%10 is the last digit of n. Furthermore, n/10 is the rest of the digits. This peels the digits off a number in reverse order. Happily, we don't care what order the digits appear for the tallying process.

The solution falls out of this analysis:

#include <stdio.h>
int counts[15];
main () {
    FILE *fin = fopen ("dream.in", "r");
    FILE *fout = fopen ("dream.out", "w");
    int i, m, n, x;
    fscanf(fin, "%d %d", &m, &n);
    for (i = m; i <= n; i++)         /* i spans the range of numbers */
        for (x = i; x; x /= 10)         /* x%10 is the final digit */
            counts[x%10]++;
    for (i = 0; i < 10; i++) {
        if (i > 0) fprintf (fout, " ");
        fprintf (fout, "%d", counts[i]);
    }
    fprintf (fout, "\n");
    exit (0);
}