CodeForces 1277 A Happy Birthday, Polycarp!
Description:
Hooray! Polycarp turned n years old! The Technocup Team sincerely congratulates Polycarp!
Polycarp celebrated all of his n birthdays: from the to the . 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: and . The following numbers are not beautiful: and
Of course, Polycarpus uses the decimal numeral system (. radix is ).
Help Polycarpus to find the number of numbers from to (inclusive) that are beautiful.
Input
The first line contains an integer — the number of test cases in the input. Then test cases follow.
Each test case consists of one line, which contains a positive integer — 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 and , inclusive.
Example
input
6
18
1
9
100500
33
1000000000
output
10
1
9
45
12
81
Note
In the first test case of the example beautiful years are and .
题意: 给出让你求前个数中有多少个漂亮数字,就是这样的数字,只有一个数字,前个数里有9个,往后每扩大倍就会多个。
AC代码:
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <queue>
using namespace std;
#define sd(n) scanf("%d", &n)
#define sdd(n, m) scanf("%d%d", &n, &m)
#define sddd(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define pd(n) printf("%d\n", n)
#define pc(n) printf("%c", n)
#define pdd(n, m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n, m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld", &n)
#define sldd(n, m) scanf("%lld%lld", &n, &m)
#define slddd(n, m, k) scanf("%lld%lld%lld", &n, &m, &k)
#define sf(n) scanf("%lf", &n)
#define sc(n) scanf("%c", &n)
#define sff(n, m) scanf("%lf%lf", &n, &m)
#define sfff(n, m, k) scanf("%lf%lf%lf", &n, &m, &k)
#define ss(str) scanf("%s", str)
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define mem(a, n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mod(x) ((x) % MOD)
#define gcd(a, b) __gcd(a, b)
#define lowbit(x) (x & -x)
typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
inline int read()
{
int ret = 0, sgn = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
sgn = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
return ret * sgn;
}
inline void Out(int a)
{
if (a > 9)
Out(a / 10);
putchar(a % 10 + '0');
}
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b)
{
return a * b / gcd(a, b);
}
///快速幂m^k%mod
ll qpow(int m, int k, int mod)
{
ll res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
// 快速幂求逆元
int Fermat(int a, int p) //费马求a关于b的逆元
{
return qpow(a, p - 2, p);
}
///扩展欧几里得
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int g = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return g;
}
///使用ecgcd求a的逆元x
int mod_reverse(int a, int p)
{
int d, x, y;
d = exgcd(a, p, x, y);
if (d == 1)
return (x % p + p) % p;
else
return -1;
}
///中国剩余定理模板
ll china(int a[], int b[], int n) //a[]为除数,b[]为余数
{
int M = 1, y, x = 0;
for (int i = 0; i < n; ++i) //算出它们累乘的结果
M *= a[i];
for (int i = 0; i < n; ++i)
{
int w = M / a[i];
int tx = 0;
int t = exgcd(w, a[i], tx, y); //计算逆元
x = (x + w * (b[i] / t) * x) % M;
}
return (x + M) % M;
}
int n, t;
int ans, res, cnt, temp;
int main()
{
sd(t);
while (t--)
{
ans = 0;
sd(n);
if (n <= 9)
{
cout << n << endl;
continue;
}
int len = log10(n) + 1; //长度
//cout << len << endl;
ans = (len - 1) * 9;
res = n / pow(10, len - 1); //取出最高位数字
//cout<<res<<endl;
int sum = 0;
rep(i, 1, len)
{
sum = sum * 10 + res;
}
if (n >= sum)
ans += res;
else
ans += res - 1;
pd(ans);
}
return 0;
}