USACO DEC06 wpb Analysis

USACO DEC06 Problem 'wpb' Analysis

by Rob Kolstad

The solution to wonderprimes requires a routine to test prime-ness along with code to process the integer parts of numbers that might qualify as wonderprimes.

Efficiency is generally important for prime-testing routines which require brute-force testing. The factors to be tested to disqualify a prime range from 2 through sqrt(n). Of course, even numbers starting with 4 need not be tested. One set of logic to do this looks like this:

prime (n) {
    int i;
    if (n > 0 && n <= 3) return 1;
    if (n %2 == 0) return 0;
    for (i = 3; i*i <= n; i+=2)
        if (n % i == 0) return 0;
    return 1;
}

The termination condition of i*i <= n is one way to test only the factors of integer. One could also start at sqrt(n) (as calculated by some math routine) and count backwards. I haven't done the tests to see if that's faster or not since the sqrt() takes a while to compute and most numbers are quickly disqualified with low factors.

Disassembling an integer into two pieces requires using the mod (%) and integer divide (/) operators and a power of ten. By way of example, consider the integer 1234567. Here is a table of some powers of ten and the result of mod and integer divide:

 Power      Divide    Mod
10         123456         7
100         12345        67
1000         1234       567
10000         123      4567
100000         12     34567
1000000         1    234567

You can see that the operations extract the digits of interest for a wonderprime. Thus candidate/power is the first digits of a candidate wonderprime while candidate%power is the final digits. It might also be clear that one can count the digits of a number by successively dividing by 10 until the number becomes 0.

Another brute force problem, basically the steps are:

For each possible partitioning of the wonderprime

Reset bottom digits (carefully -- top digit is '1' after reset) if top is to be incremented
Count bottom digits up to prime
Reset top digits carefully if they are too short
Count top digits up to prime (be careful of overflows!)
See if answer for this partitioning is the best

Richard Peng's code:

#include <stdio.h>

int d,n,ans;
int power[10]={1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
        100000000, 1000000000};

ndigits (int a) {
    int ans;
    for (ans=0; a!=0; a=a/10, ans++);
    return ans;
}

void testwonderprime (long pow) {
    long n1 = n;                                /* work copy of n */
    /**** get bottom digits right ****/
    if( (!prime(n1/pow)) || ndigits(n1/pow)<d)  /* top digits not prime? */
        n1 -= (n1%pow) + pow/10;                /* start over on bottom */
    for ( ; !(prime(n1%pow)) || ndigits(n1%pow)<d; n1++)
        ;                                       /* increment bottom digits until prime & long enough */

    /**** get top digits right ****/
    if (ndigits (n1/pow)<d)                  /* get enough digits on top */
        n1 = n1%pow + power[d-1]*pow;
    for(; !prime(n1/pow); n1+=pow)              /* make top prime */
        if (n1 > 2000000000 || n1 < 0) return;
    if (n1 < 0) return;
    if (n1 < ans)
        ans=n1;
}

main() {
    long i;
    FILE *fin=fopen("wpb.in","r");
    FILE *fout=fopen("wpb.out","w");
    fscanf(fin,"%d %d", &d, &n);
    ans = 2000000000;                           /* "infinity" */
    for(i=d; i<9; i++)
        testwonderprime (power[i]);
    fprintf (fout,"%d\n",ans);
    fclose (fin);
    fclose (fout);
}