hihoCoder #1432 : JiLi Number（吉利数）
Description - 题目描述
Driver Ji likes the digit "1". He has an accumulator which shows the sum of input number. He lists all of positive number no more than N and starts counting from one, two, three...Every time he counts a number he will add the number of digit "1" in this number to accumulator at the same time. The amazing thing happens! At some times, when he finishes counting a number X, the number which on the accumulator is X exactly, he will regard X as "JiLi Number" which means lucky number. Now he wants to know the number of "JiLi Numbers" and the biggest "JiLi Number" no more than N.
Ji司机喜欢数字””。他有一个累加器可以显示输入数的和。他列出了所有不超过N的正整数，并且开始1，，...地数了起来。每当他数到一个数时，会顺手把其数字””的个数放入累加器。不可思议的事发生了！有时他数完一个数X，累加器中的数也恰好为X，他将X称作”吉利数”，表示十分幸运的数字。现在他想知道在不超过N的情况下”吉利数”的数量与最大”吉利数”。
CN
Input - 输入
There are several test cases and the each test case is a line contains an positive integer N.(1<N≤10)
多组数据，每组数据仅有一行，每行一个正整数N。（<N≤^）
CN
Output - 输出
For each test case, output two integers which donates the number of "JiLi Numbers" and the biggest "JiLi Number".
对于每个测试用例，输出两个整数分别表示”吉利数”的数量与最大的”吉利数”。
CN
Sample Input - 样例输入
1
100000000000
Sample Output - 样例输出
1 1
83 1111111110
题解
暴力枚举，样例刚刚好给出了最大与最小的情况……
至于证明，证不出来，似乎因为是十进制数所以不能超过十位数，到了后面累加器中的值的增长速度明显超过了数数速度，应该是没有交集了……
代码 C++
#include<cstdio>
#include <algorithm>
#define ll long long
#define mx 84
ll opt[mx] = {
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
0x7FFFFFFFFFFFFFFF
};
int main(){
char rd[];
int i;
ll tmp;
while (gets(rd)){
tmp = ;
for (i = ; i < && rd[i]; ++i) tmp = tmp * + rd[i] - '';
i = std::upper_bound(opt, opt + mx, tmp) - opt;
printf("%d %lld\n", i, opt[i - ]);
}
return ;
}