The answer and the source code

来源: mascotwu 2009-05-10 23:48:53 [] [旧帖] [给我悄悄话] 本文已被阅读: 次 (5705 bytes)
本文内容已被 [ mascotwu ] 在 2009-05-12 06:10:53 编辑过。如有问题,请报告版主或论坛管理删除.
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- 给 mascotwu 发送悄悄话 (90 bytes) () 05/11/2009 postreply 00:07:00

没看你的code,但是可以更小 -康MM- 给 康MM 发送悄悄话 康MM 的博客首页 (32 bytes) () 05/11/2009 postreply 04:51:30

请您先登陆,再发跟帖!

发现Adblock插件

如要继续浏览
请支持本站 请务必在本站关闭/移除任何Adblock

关闭Adblock后 请点击

请参考如何关闭Adblock/Adblock plus

安装Adblock plus用户请点击浏览器图标
选择“Disable on www.wenxuecity.com”

安装Adblock用户请点击图标
选择“don't run on pages on this domain”