DIGIT5 - Số chữ số 5

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hiếu Nguyễn
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho hai số nguyên dương ~M, N~. Hãy cho biết để biểu diễn các số trong phạm vi từ ~M~ đến ~N~ trong hệ đếm thập phân ta cần sử dụng bao nhiêu chữ số 5.

Input

  • Một dòng duy nhất chứa hai số nguyên dương ~M, N~

Giới hạn:

  • ~(1 ≤ M≤N≤10^9~
  • ~N - M≤10^5)~

Output

  • Một số nguyên duy nhất là số chữ số 5 được dùng để biểu diễn các số trong phạm vi từ ~M~ đến ~N~.

Sample

Input #1
1 20
Output #1
2
Input #2
50 60
Output #2
11

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.


  • 0
    skjafirjmm  đã bình luận lúc 3, Tháng 12, 2025, 17:26

    include <bits/stdc++.h>

    using namespace std; using ll = long long; int main() {

    ios::sync_with_stdio(false);
cin.tie(0);
ll m,n; cin>>m>>n;
int cnt=0;
for(int i=m; i<=n; i++){
    string tmp=to_string(i);
    for(auto x:tmp) if(x=='5') cnt++;
}
cout<&lt;cnt;

    }


  • 0
    congtyluuthaibao1978  đã bình luận lúc 27, Tháng 11, 2025, 5:31

    include <bits/stdc++.h>

    using namespace std;

    using ll = long long;

    int L, R; int digits[20]; long long memo[20][2][20];

    // Đếm số chữ số 5 trong các số từ 0 đến số được biểu diễn trong digits[0..pos] // tight = 1 nếu số đang xét chưa vượt giới hạn digits, cnt5 = số chữ số 5 đã xuất hiện long long dp(int pos, int tight, int cnt5) { if(pos == -1) return cnt5; if(memo[pos][tight][cnt5] != -1) return memo[pos][tight][cnt5];

    int limit = tight ? digits[pos] : 9;
long long res = 0;
for(int d = 0; d <= limit; d++) {
    res += dp(pos-1, tight && (d==limit), cnt5 + (d==5));
}
return memo[pos][tight][cnt5] = res;

    }

    // Hàm tính số chữ số 5 từ 0 đến x long long count5(int x) { int pos = 0; while(x) { digits[pos++] = x % 10; x /= 10; } memset(memo, -1, sizeof(memo)); return dp(pos-1, 1, 0); }

    int main() { ios::syncwithstdio(false); cin.tie(nullptr);

    int L, R;
cin >> L >> R;
long long ans = count5(R) - count5(L-1);
cout << ans << "\n";

    }