In Tất Cả Số "Tốt" Trong Khoảng Cho Trước Trong C++

Trong bài toán này, chúng ta được cho ba giá trị L, R và d. Nhiệm vụ là in tất cả số tốt (good numbers) trong khoảng L đến R không chứa chữ số d.

Số tốt là số mà mọi chữ số đều lớn hơn tổng các chữ số bên phải nó (tất cả bit kém quan trọng hơn). Ví dụ: 732 là số tốt vì 7 > 3+2 và 3 > 2.

Ví dụ để hiểu vấn đề:

Đầu vào: L = 400, R = 500, k = 3 → Đầu ra: 410, 420, 421

Giải thích – Các số tốt từ 400 đến 500: 410, 420, 421, 430, nhưng không dùng 3 nên 430 không in.

Để giải quyết, kiểm tra tất cả số trong khoảng L đến R. Nếu số là số tốt và không có chữ số nào bằng k thì in ra.

Kiểm tra số tốt – Duyệt số từ phải sang trái, giữ tổng tích lũy. Tại bất kỳ điểm nào nếu tổng > chữ số tiếp theo thì trả về false.

Ví Dụ

Chương trình minh họa thuật toán:

#include<bits/stdc++.h>
using namespace std;

bool isvalidNumber(int n, int d) {
    int digit = n % 10;
    int sum = digit;
    if (digit == d)
        return false;
    n /= 10;
    while (n) {
        digit = n % 10;
        if (digit == d || digit <= sum)
            return false;
        else {
            sum += digit;
            n /= 10;
        }
    }
    return 1;
}

void printGoodNumbersLtoR(int L, int R, int d) {
    for (int i = L; i <= R; i++) {
        if (isvalidNumber(i, d))
            cout << i << " ";
    }
}

int main() {
    int L = 400, R = 600, d = 3;
    cout << "Tất cả số tốt từ " << L << " đến " << R << " không chứa " << d << " là:\n";
    printGoodNumbersLtoR(L, R, d);
    return 0;
}

Đầu Ra

Tất cả số tốt từ 400 đến 600 không chứa 3 là: 410 420 421 510 520 521 540