2014
03-30

# Integers’ Weight

The weight of a positive integer is the sum of its digits. For example, weight(12097) = 1+2+0+9+7 = 19. For any positive integer x, f(x) = 1 if weight(x) = x, and f(x) = f(weight(x))+1 otherwise. For example, f(2) = 1 and f(654) = f(15)+1 = f(6)+1+1 = 3.
Find the smallest number x that f(x) = n. The answer may be huge, just output the remainder after divided by 100007.

There are several test cases in the input.

Each test case begin with an integer n (1 <= n <= 1000000000).

The input terminates by end of file marker.

There are several test cases in the input.

Each test case begin with an integer n (1 <= n <= 1000000000).

The input terminates by end of file marker.

2
3

10
19

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;

const int mod=100007;
int dp[30];
int succ[mod],cycle;

void get_T(int m)
{
int cnt=1;
memset(succ,-1,sizeof(succ));
succ[0]=0;
int now=0;
while(1)
{
now=(now*10+2)%m;
if (succ[now]!=-1)
{
cycle=cnt-succ[now];
break;
}
succ[now]=cnt++;
}
}

int cal(int x,int m)
{
if (x==1) return 1;
get_T(m);
int tmp=cal(x-1,cycle);
int now=0;
while(tmp--)
{
now=now*10+2;
if (now>=m)
{
int t=(now-mod)/m;
now=now-t*m;
}
}
return now;
}

int main()
{
for (int i=1;i<10;i++)
{
dp[i]=(9*cal(i,mod)+1)%mod;
//printf("%d\n",dp[i]);
}
int n;
while(scanf("%d",&n)!=EOF)
{
int ans;
if (n<=9)
ans=n==1?1:dp[n-1];
else
if (n%2==1)
ans=dp[8];
else ans=dp[7];
printf("%d\n",ans);
}
return 0;
}

1. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.

2. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

3. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮