The answer and the source code

I had to be helped by the computer... Here are all the numbers satisfying 1 and 2:, in decreasing order:

$ time ./a.out

# of trailing 9's = 223, prefix = 11000
Num = 110009999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

# of trailing 9's = 222, prefix = 31052
Num = 31052999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

# of trailing 9's = 221, prefix = 39314
Num = 3931499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

# of trailing 9's = 220, prefix = 67691
Num = 676919999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

# of trailing 9's = 219, prefix = 459947
Num = 459947999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

# of trailing 9's = 218, prefix = 2899865
Num = 289986599999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

# of trailing 9's = 217, prefix = 18999866
Num = 189998669999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

# of trailing 9's = 216, prefix = 98996996
Num = 98996996999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

# of trailing 9's = 215, prefix = 868989998
Num = 86898999899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

Failed to find a smaller number.

real 0m1.598s
user 0m1.520s
sys 0m0.004s

The source code:#include
#include

using namespace std;

int findNum(int n9, int prev_tot);
void printNum(int tot, int n9);

main(int argc, char **argv)
{
int init_n9 = 2009 / 9;
if (argc >= 2) {
int n = atoi(argv[1]);
if (n >= 1 && n <= init_n9)
init_n9 = n;
else
cout << "Ignore bad input." << endl;
}

// find the first good n9
int good_n9 = 0;
int good_tot = 0;
while (good_n9 == 0) {
if ((good_tot = findNum(init_n9, INT_MAX)) > 0) {
good_n9 = init_n9;
} else {
init_n9 --;
}
}

printNum(good_tot, good_n9);
// try to find a better n9 resulting in a smaller number
int ratio = 1;
int next_n9 = good_n9;
int next_tot = good_tot;
while (next_tot > 0) {
ratio *= 10;
next_n9 --;
if ((next_tot = findNum(next_n9, good_tot*ratio+(ratio-1))) > 0) {
ratio = 1;
good_tot = next_tot;
good_n9 = next_n9;
printNum(good_tot, good_n9);
} else {
cout << "Failed to find a smaller number." << endl;
}
}
}

int
findNum(int n9, int prev_tot) {
int tot = 2009;
for (int i = 1; i < n9; i ++) {
tot /= 10;
int l = tot%10;
int a = 9 - l;
int m = 0;
switch (a) {
case 0: m = 0; break; // 0 * 9 = x0, x means dont care
case 1: m = 9; break; // 9 * 9 = x1, x means dont care
case 2: m = 8; break; // 8 * 9 = x2, x means dont care
case 3: m = 7; break; // 7 * 9 = x3, x means dont care
case 4: m = 6; break; // 6 * 9 = x4, x means dont care
case 5: m = 5; break; // 5 * 9 = x5, x means dont care
case 6: m = 4; break; // 4 * 9 = x6, x means dont care
case 7: m = 3; break; // 3 * 9 = x7, x means dont care
case 8: m = 2; break; // 2 * 9 = x8, x means dont care
case 9: m = 1; break; // 1 * 9 = x9, x means dont care
default: break;
}
tot += m*2009;
}
tot /= 10;

int r = 2009 - n9*9;
assert (r > 0);

//cout << "r = " << r << endl;

int k = 0;
int sum = 0, num = tot;
while (tot < prev_tot && sum != r) {
tot += 2009;
k ++;
sum = 0;
num = tot;
while (num > 0) {
sum += num%10;
num /= 10;
}
//cout << "sum = " << sum << endl;
}

if (sum == r) {
return tot;
} else {
return 0;
}
}
void
printNum(int tot, int n9) {
cout << "# of trailing 9's = " << n9 << ", prefix = " << tot << endl;
cout << "Num = " << tot;
for (int i = 0; i < n9; i ++)
cout << 9;
cout << endl;
cout << endl;
}

所有跟帖： 

• 回复：The answer and the source code -mascotwu- ♀ (90 bytes) () 05/11/2009 postreply 00:07:00

• 没看你的code，但是可以更小 -康MM- ♀ (32 bytes) () 05/11/2009 postreply 04:51:30