Nguồn: Giải Tứ Lanqiao Cup Nhóm C++

Thuật toán: Quay lui và tối ưu

Mô tả bài toán

Số 100 có thể biểu diễn dưới dạng phân số như sau: 100 = 3 + 69258/714

Cũng có thể biểu diễn là: 100 = 82 + 3546/197

Lưu ý đặc điểm: trong biểu diễn phân số, các chữ số từ 1 đến 9 xuất hiện chính xác một lần (không chứa số 0).

Loại biểu diễn phân số như vậy, số 100 có 11 cách biểu diễn khác nhau.

Địnhnhập

Một số nguyên dương.

Địnhnhập

Xuất ra số lượng cách biểu diễn số đầu vào bằng các chữ số 1~9 không trùng lặp không bỏ sót để tạo thành biểu diễn phân số.

Phạm vi dữ liệu

`1≤N<106`

Ví dụ đầu vào 1:

`100`

Ví dụ đầu ra 1:

`11`

Ví dụ đầu vào 2:

`105`

Ví dụ đầu ra 2:

`6`

Phương pháp giải

Từ bài toán, ta thấy `trong biểu diễn phân số, các chữ số 1~9 xuất hiện chính xác một lần`

Và đặc điểm của biểu diễn phân số là `n=a+b/c`, hay nói cách khác `n*c=a*c+b;`

Phương pháp trực tiếp nhất là có thể liệt kê tất cả các hoán vị của 1-9 và giới hạn mỗi chữ số chỉ xuất hiện một lần, sau đó kiểm tra xem có thỏa mãn `n*c=a*c+b;` hay không.

Mã nguồn C++

#include <iostream>

using namespace std;

const int MAX_N = 1e6 + 10;
bool used[MAX_N]; // Kiểm tra xem số đã được sử dụng chưa
int target, digits[10], count_solutions;

// Tính giá trị từ mảng chữ số từ vị trí l đến r
int calculate_value(int l, int r) {
    int result = 0;
    for (int i = l; i <= r; i++)
        result = result * 10 + digits[i];
    return result;
}

// Hàm quay lui để tạo tất cả các hoán vị
void generate_permutations(int pos) {
    if (pos > 9) {
        // Đã điền đủ 9 chữ số, kiểm tra tất cả cách chia thành 3 phần
        for (int i = 1; i <= 9; i++) {
            for (int j = i + 1; j <= 9; j++) {
                int a = calculate_value(1, i);
                int b = calculate_value(i + 1, j);
                int c = calculate_value(j + 1, 9);
                
                // Kiểm tra điều kiện của biểu diễn phân số
                if (target * c == a * c + b)
                    count_solutions++;
            }
        }
        return;
    }
    
    // Thử tất cả các chữ số từ 1 đến 9
    for (int num = 1; num <= 9; num++) {
        if (!used[num]) {
            used[num] = true; // Đánh dấu đã sử dụng
            digits[pos] = num; // Đặt chữ số vào vị trí hiện tại
            generate_permutations(pos + 1); // Tiếp tục cho vị trí tiếp theo
            used[num] = false; // Bỏ đánh dấu để thử các số khác
            digits[pos] = 0; // Reset giá trị
        }
    }
}

int main() {
    cin >> target;
    generate_permutations(1); // Bắt đầu từ vị trí 1
    cout << count_solutions; // Xuất ra số lượng giải pháp
    return 0;
}

Mã nguồn C++ (Phiên bản khác)

#include <iostream>

using namespace std;

const int LIMIT = 1e6 + 10;
bool visited[LIMIT];
int number, sequence[10], result;

// Hàm tính giá trị từ dãy số
int get_value(int left, int right) {
    int value = 0;
    for (int i = left; i <= right; i++) {
        value = value * 10 + sequence[i];
    }
    return value;
}

// Hàm đệ quy để tạo hoán vị
void backtrack(int current) {
    if (current > 9) {
        // Tạo tất cả các cách chia thành 3 phần
        for (int split1 = 1; split1 <= 9; split1++) {
            for (int split2 = split1 + 1; split2 <= 9; split2++) {
                int part_a = get_value(1, split1);
                int part_b = get_value(split1 + 1, split2);
                int part_c = get_value(split2 + 1, 9);
                
                // Kiểm tra xem có thỏa mãn điều kiện của biểu diễn phân số
                if (number * part_c == part_a * part_c + part_b)
                    result++;
            }
        }
        return;
    }
    
    // Thử các số từ 1 đến 9
    for (int digit = 1; digit <= 9; digit++) {
        if (!visited[digit]) {
            visited[digit] = true;
            sequence[current] = digit;
            backtrack(current + 1);
            visited[digit] = false;
            sequence[current] = 0;
        }
    }
}

int main() {
    cin >> number;
    backtrack(1);
    cout << result << endl;
    return 0;
}