Số một số (Tin học trẻ A - Vòng Sơ khảo 2021)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small , dong3d , _minhduc
Dạng bài
Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Số một số là một số tự nhiên mà các chữ số của số đó giống nhau.

Ví dụ: \(1,8,111,555,99999,...\)

Cho một số tự nhiên \(N\). Hãy đếm số lượng số một số bé hơn hoặc bằng \(N\).

Input

  • Một dòng chứa một số tự nhiên \(N\) (\(N \le 10^9\)).

Output

  • Một số duy nhất là số lượng số thỏa mãn đề bài.

Example

Test 1
Input 
15
Output 
10
Note

Khi \(N=15\) thì có \(10\) số là \(1,2,3,4,5,6,7,8,9,11\).

Test 2
Input 
111
Output 
19
Note

Khi \(N = 111\) thì có \(19\) số là:

  • Có \(9\) số từ \(1\) đến \(9\).
  • Có \(9\) số \(11,22,33,...,99\).
  • Có \(1\) số \(111\).

Bình luận

  • v2manhvcl • 5:22 p.m. 4 Tháng 12, 2024 •

    include <bits/stdc++.h>

    using namespace std;

    define ll long long

    const ll MOD = 1e9 + 7;
    ll n;
    const ll N = 1e5 + 2 ;
    ll f[N][13] ;
    void inp() {
    cin >> n;
    }
    ll log(ll n){
    ll ans = 0 ;
    while(n > 0){
    ans++ ;
    n /= 10 ;
    }
    return ans ;
    }
    ll find(ll l , ll r){
    ll so_bi_chia = 0 ;
    for(ll i = 1 ; i <= r ; i++) so_bi_chia = so_bi_chia * 10 + 1 ;
    r = pow(10 , r) ;
    return r / so_bi_chia - (l - 1)/so_bi_chia ;
    }
    void sol() {
    ll new_s = log(n) , ans = 0 ;
    ans = 9 * new_s ;
    ll nums = find(n + 1 , new_s) ;
    cout <<ans - nums ;
    }

    int main() {
    inp();
    sol();
    }

    2
    Phản hồi
      • 5 bình luận nữa