本文共 2284 字,大约阅读时间需要 7 分钟。
题目来源:
Description
Hooray! Polycarp turned n years old! The Technocup Team sincerely congratulates Polycarp!
Polycarp celebrated all of his n birthdays: from the 1-th to the n-th. At the moment, he is wondering: how many times he turned beautiful number of years?
According to Polycarp, a positive integer is beautiful if it consists of only one digit repeated one or more times. For example, the following numbers are beautiful: 1, 77, 777, 44 and 999999. The following numbers are not beautiful: 12, 11110, 6969 and 987654321.
Of course, Polycarpus uses the decimal numeral system (i.e. radix is 10).
Help Polycarpus to find the number of numbers from 1 to n (inclusive) that are beautiful.
Input
The first line contains an integer t (1≤t≤104) — the number of test cases in the input. Then t test cases follow.
Each test case consists of one line, which contains a positive integer n (1≤n≤109) — how many years Polycarp has turned.
Output
Print t integers — the answers to the given test cases in the order they are written in the test. Each answer is an integer: the number of beautiful years between 1 and n, inclusive.
Sample Input
6
18 1 9 100500 33 1000000000Sample Output
10
1 9 45 12 81Note
In the first test case of the example beautiful years are 1, 2, 3, 4, 5, 6, 7, 8, 9 and 11.
AC代码1:
#includeusing namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'bool fun(string s,string ss,int len){ for(int i=0;i s[i]) return false; else if(ss[i] > T; while(T--) { string s; cin >> s; int len=s.size(),ans=0; ans+=(len-1)*9; string ss(len,s[0]); if(fun(s,ss,len)) ans+=s[0]-'0'; else ans+=s[0]-'0'-1; cout << ans << endl; } return 0;}
AC代码2:
#includeusing namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'int main(){ SIS; int n,m,T,ans; cin >> T; while(T--) { cin >> n; m=n; int len=0; while(m/10) len++,m/=10; ans=len*9; int num=1; while(len) num=num*10+1,len--; ans+=n/num; cout << ans << endl; } return 0;}
转载地址:http://gsyof.baihongyu.com/