欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

codeforces 606A. Happy Birthday, Polycarp!

程序员文章站 2022-05-09 22:01:27
...

链接:codeforces 606A. Happy Birthday, Polycarp!

题目要求

Hooray! Polycarp turned nn years old! The Technocup Team sincerely congratulates Polycarp!

Polycarp celebrated all of his nn birthdays: from the 11-th to the nn-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, 44and 99999. 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 11 to nn (inclusive) that are beautiful.

Input
The first line contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases in the input. Then tt test cases follow.

Each test case consists of one line, which contains a positive integer nn (1≤n≤1091≤n≤109) — how many years Polycarp has turned.

Output
Print tt 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 11 and nn, 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 1, 2, 3, 4, 5, 6, 7, 8, 9 and 11.

解题思路

刚开始做的时候,题目没有看明白。这一题要你找n以内的美丽数:就是1~9和11,22,33,44,55,66,77,88,99,111,222,333,444,555,666,777,…11111,22222,33333…。先求出n的位数num,再将n放在数组里——这样方便查询每一位上的数字——再遍历n,只要找到比a[1](n最高位上的数字)大或者小的数,就停止遍历。如果先找到了比a[1]小的,就在原基础上多减个1。

正确代码

#include <iostream>
#include<bits/stdc++.h>
#include<algorithm>
#define ll long long
using namespace std;
int a[20];

int main()
{
    int t;
    cin>>t;
    while(t--){
        ll n;
        int num=0;
        int flag=0;
        cin>>n;
        if(n<10)
           {
               cout<<n<<endl;continue;
           }
        else{
        ll m;
        m=n;
        memset(a,0,sizeof(a));
        while(m>0){
            num++; //n是几位数;
            m/=10;
        }
        for(int i=num;i>=1;--i){
            a[i]=n%10;
            n/=10;
        }
        for(int i=2;i<=num;++i){
            if(a[i]==a[1])
                continue;  
            else if(a[i]>a[1]){
                break;
            }
            else{
                flag=1;
                break;
            }
        }
        num--;
        if(flag==0)
            cout<<a[1]+9*num<<endl;
        else
            cout<<a[1]+9*num-1<<endl;
        }
    }
    return 0;
}