/*--------------------------------------------------------------------------- ENTRY: odomatic FROM: Vincent Goffin AT: mozart!vjg First, here's the original entry, with lines cut at position 80. If you want to compile it you must rejoin the last five lines. There are 2 lines altogether. It may not run correctly on some systems, because of v declared as int* ('cause it's shorter than char** !) #define u U[i]=U[j]=0 int B,L,H=1e4,g,i,j,n,T=10;char U[10],Y[4],K[5];main(x,v)int*v;{for(open(v[1],cl ose(0));scanf("%d%d",&n,&x)>0;printf("%d\n",x)){x=H+n-x;for(g=4;g--;x/=T)Y[g]=x% T;G(3,0);for(x=g++;B==H;x+=B-L)L=x+n,i=L/H/T%T,j=L/H%T,L%=H,i-j&&G(u+3,0),u;}}G( n,c){int i=(c+=Y[n])&&c=L?B=j:0,g)););} A much expanded version follows, and it's not that much slower. Things I like about this algorithm: 1. Odom() routine screens out all impossible cases AND generates all solutions when asked to. 2. Good use made of the problem's Y[] invariants (see code). 3. An all arithmetic approach best proceeds left to right, and an all symbolic (no /, % or + of large numbers) approach best proceeds right to left (because it still needs the single digit carry). These "pure" methods by themselves can be solve the problem, and lead to more compact code (25%), but they tend to be too slow (x10). This algorithm is a hybrid, using arithmetic for the first two digits of big odom and symbolic for the last 4 digits, where a "generate and match" method makes use of the Y[] invariants. Things I would have liked to improve but couldn't: 1. Proving the existence of a solution apparently generates no useful information that could make it easier to find the smallest solution (even when both problems use the same routine). 2. Apparently the fastest way to find the smallest solution involves exhausting ALL solutions for 2 given leading digits. -----------------------------------------------------------------------------*/ int T=10, H=10000, Existence, Exists, Best, Least; char U[10], /* 0/1 flag: is digit i already used? */ Y[4], /* last 4 digit of (big_odom - small_odom), an invariant */ K[5]; /* temp buffer for all solutions with same 2 leading digits */ main(argc, argv) int argc; char *argv[]; { int i, j, /* leading big odom digits */ big_o, /* big odom initial reading */ sml_o, miles, /* miles traveled in search for solution */ nbig_o; /* big_o + miles */ /* read from stdin to avoid explicit file structures */ close(0); /* close stdin */ open(argv[1],0); /* make v[1] stdin */ /* read input file of initial large & small odometer readings */ while (scanf("%d%d", &big_o, &sml_o) == 2) { /* the 4 Y invariants, used by Odom() algorithm */ sprintf(Y, "%04d", (H + big_o - sml_o)%H); /* verify existence of a solution */ Exists = 0; Existence = 1; Odom(3, 0); Existence = 0; /* if a solution exists, set up search for smallest */ if (Exists) miles = 0, Best = H; else miles = -1, Best = 0; /* if solution exists, search for the smallest one */ while (Best == H) { /* Increment 2 leading digits of big odometer, cautiously, until examination of the last 4 digits of the big odom and the 4 digits of the small odom shows a solution. We already know there is a solution, and this approach will eventually find the smallest one. */ /* i,j are the 2 leading digits of big odometer */ nbig_o = big_o + miles; i = nbig_o/H/T%T; j = nbig_o/H%T; Least = nbig_o%H; if (i != j) { U[i]=U[j]=1; /* mark i,j digits as used */ /* find all solutions, if any, and keep smallest. When Odom() finds a solution it sets Best < H, so we break out of the loop, cleanly */ Odom(3, 0); U[i]=U[j]=0; /* free the i,j digits */ } miles += Best - Least; } printf("%d\n", miles); } exit(0); } Odom(n, carry) /*----------------------------------------------------------------------- Odom() is used first to determine if a solution exists, and then to find the best solution if a solution exists. n starts at 3 and goes down to 0, as the algorithm examines the odometer digits from right to left, recursively. All big odom digits (i) are generated and tested in turn, from 9 to 0. For each i that passes the test, i.e. has not yet been used, the only possible corresponding small odom digit is calculated (from Y[n] and the carry) and tested. Y[n] is between '0' and '9', carry is 0 or 1. If both tests pass, we can proceed to the next digit to the left or record the solution (when n = 0). For the existence proof, Existence is set to 1 and we can exit as soon as the first solution is registered. Otherwise the algorithm exhausts all solutions and keeps the best one. ------------------------------------------------------------------------------*/ int n, carry; { int i, j, delta = carry + Y[n] - '0'; /* if delta = 0 or 10, i will = j and there can be no solution. So for these cases set i = 0 and avoid the while() loop */ i = (delta && delta < T)? T: 0; carry = 0; /* this is the next carry; the current carry was absorbed in delta */ while (i--) if (U[i] == 0) /* big odom digit must still be free */ { if (i < delta) /* carry needed */ { carry = 1; delta -= T; /* simulate effect of carry */ } j = i - delta; /* small odom digit... */ if (U[j] == 0) /* ...must also be free */ { K[n] = '0' + i; /* record digit as a char */ if (n > 0) { U[i]=U[j]=1; /* used */ Odom(n-1, carry); U[i]=U[j]=0; /* free */ } else if (Existence) Exists = 1; else /* record all, keep smallest */ { int new = atoi(K); if (new < Best && new >= Least) Best = new; } } if (Existence && Exists) break; } }