hihoCoder 1432 : JiLi Number（吉利数）

本文主要是介绍hihoCoder 1432 : JiLi Number（吉利数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

hihoCoder #1432 : JiLi Number（吉利数）

时间限制:1000ms

单点时限:1000ms

内存限制:256MB

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司机喜欢数字”1”。他有一个累加器可以显示输入数的和。他列出了所有不超过N的正整数，并且开始1，2，3...地数了起来。每当他数到一个数时，会顺手把其数字”1”的个数放入累加器。不可思议的事发生了！有时他数完一个数X，累加器中的数也恰好为X，他将X称作”吉利数”，表示十分幸运的数字。现在他想知道在不超过N的情况下”吉利数”的数量与最大”吉利数”。

Input - 输入

There are several test cases and the each test case is a line contains an positive integer N.(1<N≤10¹⁰⁰)

多组数据，每组数据仅有一行，每行一个正整数N。（1<N≤10^100）

Output - 输出

For each test case, output two integers which donates the number of "JiLi Numbers" and the biggest "JiLi Number".

对于每个测试用例，输出两个整数分别表示”吉利数”的数量与最大的”吉利数”。

Sample Input - 样例输入

1
100000000000

Sample Output - 样例输出

1 1
83 1111111110

题解

　　暴力枚举，样例刚刚好给出了最大与最小的情况……
　　至于证明，证不出来，似乎因为是十进制数所以不能超过十位数，到了后面累加器中的值的增长速度明显超过了数数速度，应该是没有交集了……

代码 C++

  1 #include<cstdio>
  2 #include <algorithm>
  3 #define ll long long
  4 #define mx 84
  5 ll opt[mx] = {
  6     1,
  7     199981,
  8     199982, 
  9     199983,
 10     199984,
 11     199985, 
 12     199986,
 13     199987, 
 14     199988, 
 15     199989,
 16     199990,
 17     200000, 
 18     200001,
 19     1599981,
 20     1599982,
 21     1599983,
 22     1599984, 
 23     1599985,
 24     1599986,
 25     1599987,
 26     1599988,
 27     1599989,
 28     1599990,
 29     2600000, 
 30     2600001,
 31     13199998,
 32     35000000, 
 33     35000001,
 34     35199981,
 35     35199982, 
 36     35199983, 
 37     35199984,
 38     35199985, 
 39     35199986, 
 40     35199987, 
 41     35199988, 
 42     35199989,
 43     35199990,
 44     35200000, 
 45     35200001,
 46     117463825,
 47     500000000,
 48     500000001,
 49     500199981,
 50     500199982,
 51     500199983, 
 52     500199984, 
 53     500199985,
 54     500199986, 
 55     500199987, 
 56     500199988,
 57     500199989,
 58     500199990,
 59     500200000, 
 60     500200001,
 61     501599981, 
 62     501599982, 
 63     501599983, 
 64     501599984, 
 65     501599985, 
 66     501599986, 
 67     501599987, 
 68     501599988, 
 69     501599989, 
 70     501599990,
 71     502600000, 
 72     502600001,
 73     513199998,
 74     535000000, 
 75     535000001,
 76     535199981, 
 77     535199982, 
 78     535199983,
 79     535199984, 
 80     535199985, 
 81     535199986,
 82     535199987,
 83     535199988, 
 84     535199989, 
 85     535199990,
 86     535200000, 
 87     535200001,
 88     1111111110,
 89     0x7FFFFFFFFFFFFFFF
 90 };
 91 int main(){
 92     char rd[200];
 93     int i;
 94     ll tmp;
 95     while (gets(rd)){
 96         tmp = 0;
 97         for (i = 0; i < 15 && rd[i]; ++i) tmp = tmp * 10 + rd[i] - '0';
 98         i = std::upper_bound(opt, opt + mx, tmp) - opt;
 99         printf("%d %lld\n", i, opt[i - 1]);
100     }
101     return 0;
102 }