Xếp số bằng que diêm 2 - LCOJ: Luyện Code Online Judge

XEPSO2 - Xếp số bằng que diêm 2

Đ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

Xét cách biểu diễn số bởi các que diêm:

Cho hai số ~l, r~, hãy tìm số que diêm ít nhất và số que diêm nhiều nhất để biểu diễn được một số trong đoạn ~[l, r]~.

Input

Dòng đầu ghi số nguyên dương ~T~ là số bộ test;
~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~l, r~.

Giới hạn:

~1≤T≤10^3,1≤l≤r≤10^{18},r-l≤10^5~

Output

Gồm ~T~ dòng, mỗi dòng gồm hai số nguyên dương ~a,b~ lần lượt là số que diêm ít nhất và số que diêm nhiều nhất biểu diễn được một số trong đoạn ~[l, r]~ (các số cách nhau bởi dấu cách).

Sample

Input #1

2
1 10
123 456

Output #1

2 8
7 19

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

Bình luận

Please read the guidelines before commenting.

Hint:

Số que cho mỗi chữ số: 0→6, 1→2, 2→5, 3→5, 4→4, 5→5, 6→6, 7→3, 8→7, 9→6.
Duyệt từ l đến r (tối đa 1e5 số).
Mỗi số: tách từng chữ số, tính tổng que, cập nhật min, max.
Độ phức tạp O((r-l+1)*log10(r)).

code tham khảo (c++):

#include <bits/stdc++.h>
using namespace std;
int que[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int tinh(long long x) {
    if (x == 0) return que[0];
    int s = 0;
    while (x > 0) {
        s += que[x % 10];
        x /= 10;
    }
    return s;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        long long l, r;
        cin >> l >> r;
        int mn = 1e9, mx = 0;
        for (long long i = l; i <= r; i++) {
            int cur = tinh(i);
            mn = min(mn, cur);
            mx = max(mx, cur);
        }
        cout << mn << " " << mx << "\n";
    }
    return 0;
}

0
congtyluuthaibao1978 đã bình luận lúc 26, Tháng 11, 2025, 4:55
include <bits/stdc++.h>

using namespace std;

int match[10] = {6,2,5,5,4,5,6,3,7,6};

int countMatch(long long num){ int res = 0; if(num == 0) return match[0]; while(num){ res += match[num % 10]; num /= 10; } return res; }

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

int t; cin >> t; while(t--){ long long L,R; cin >> L >> R; int mn = INT_MAX, mx = INT_MIN; for(long long i=L;i<=R;i++){ // dùng long long cho i int c = countMatch(i); mn = min(mn, c); mx = max(mx, c); } cout << mn << " " << mx << "\n"; }

}

0

311t_LeTruong đã bình luận lúc 15, Tháng 5, 2024, 4:49

cho mình xin đoạn code để tham khảo đk ạ