#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


long long gcd(long long a, long long b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}


long long lcm(long long a, long long b) {
    return (a / gcd(a, b)) * b;
}


bool solveBinPacking(const vector<int>& pieces, vector<int>& bins, int target, int index) {
    if (index == pieces.size()) return true;
   
    for (int j = 0; j < bins.size(); ++j) {
        if (bins[j] + pieces[index] <= target) {
            bins[j] += pieces[index];
            if (solveBinPacking(pieces, bins, target, index + 1)) return true;
            bins[j] -= pieces[index];
        }
        if (bins[j] == 0) break;
    }
    return false;
}


bool canDivide(vector<int> pieces, int k, int target) {
    if (k == 1) return true;
   
    sort(pieces.rbegin(), pieces.rend());
    if (pieces[0] > target) return false;


    vector<int> bins(k, 0);
    return solveBinPacking(pieces, bins, target, 0);
}


// KHAI BÁO BIẾN LƯU TRỮ KẾT QUẢ TỔNG KẾT
vector<vector<int>> valid_configs;
long long total_checked = 0;


void generateAndFilterPartitions(int remaining, int current_min, vector<int>& current, int m, int n, int i_max) {
    int slots_left = m - current.size();
   
    int max_possible_piece = n / i_max;
    if (remaining > slots_left * max_possible_piece) return;


    if (slots_left <= 0 && remaining > 0) return;


    // KHI ĐÃ ĐIỀN ĐỦ M PHẦN TỬ VÀ TỔNG BẰNG N
    if (remaining == 0 && slots_left == 0) {
        total_checked++;
        bool isValid = true;
       
        // Kiểm tra điều kiện
        for (int k = i_max; k >= 2; --k) {
            if (!canDivide(current, k, n / k)) {
                isValid = false;
                break;
            }
        }
       
        // IN RA TERMINAL THEO THỜI GIAN THỰC
        cout << "(";
        for (size_t j = 0; j < current.size(); ++j) {
            cout << current[j];
            if (j < current.size() - 1) cout << ",";
        }
        cout << ") " << (isValid ? "NHAN GIA TRI NAY" : "") << "\n";
       
        // Nếu hợp lệ, lưu trữ lại để in tổng kết
        if (isValid) {
            valid_configs.push_back(current);
        }
        return;
    }


    int upper_bound = min(remaining, max_possible_piece);
    for (int val = current_min; val <= upper_bound; ++val) {
        current.push_back(val);
        generateAndFilterPartitions(remaining - val, val, current, m, n, i_max);
        current.pop_back();
    }
}


int main() {
    int i_max, m;
    cout << "Nhap so khach toi da i (tu 1 den i): ";
    if (!(cin >> i_max)) return 0;
   
    long long n = 1;
    for (int k = 1; k <= i_max; ++k) {
        n = lcm(n, k);
    }
    cout << "=> Da tinh Mau so chung (LCM) n = " << n << "\n";


    cout << "Nhap so manh banh m can kiem tra: ";
    if (!(cin >> m)) return 0;


    cout << "\nDang kiem tra tung phan hoach...\n";
    cout << "--------------------------------\n";
   
    vector<int> current;
    current.reserve(m);
   
    // Bắt đầu sinh và in real-time
    generateAndFilterPartitions(n, 1, current, m, n, i_max);


    // PHẦN TỔNG KẾT CUỐI CÙNG
    cout << "--------------------------------\n";
    cout << "Da kiem tra tong cong: " << total_checked << " cau hinh.\n";
    cout << "So cau hinh THOA MAN: " << valid_configs.size() << "\n\n";
   
    if (!valid_configs.empty()) {
        cout << "DANH SACH CAC CAU HINH NHAN:\n";
        for (size_t i = 0; i < valid_configs.size(); ++i) {
            cout << "Bo " << i + 1 << ": (";
            for (size_t j = 0; j < valid_configs[i].size(); ++j) {
                cout << valid_configs[i][j];
                if (j < valid_configs[i].size() - 1) cout << ",";
            }
            cout << ")\n";
        }
    } else {
        cout << "Khong co cau hinh nao thoa man!\n";
    }
   
    return 0;
}