fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5.  
  6. using namespace std;
  7.  
  8.  
  9. long long gcd(long long a, long long b) {
  10.     while (b) { a %= b; swap(a, b); }
  11.     return a;
  12. }
  13.  
  14.  
  15. long long lcm(long long a, long long b) {
  16.     return (a / gcd(a, b)) * b;
  17. }
  18.  
  19.  
  20. bool solveBinPacking(const vector<int>& pieces, vector<int>& bins, int target, int index) {
  21.     if (index == pieces.size()) return true;
  22.  
  23.     for (int j = 0; j < bins.size(); ++j) {
  24.         if (bins[j] + pieces[index] <= target) {
  25.             bins[j] += pieces[index];
  26.             if (solveBinPacking(pieces, bins, target, index + 1)) return true;
  27.             bins[j] -= pieces[index];
  28.         }
  29.         if (bins[j] == 0) break;
  30.     }
  31.     return false;
  32. }
  33.  
  34.  
  35. bool canDivide(vector<int> pieces, int k, int target) {
  36.     if (k == 1) return true;
  37.  
  38.     sort(pieces.rbegin(), pieces.rend());
  39.     if (pieces[0] > target) return false;
  40.  
  41.  
  42.     vector<int> bins(k, 0);
  43.     return solveBinPacking(pieces, bins, target, 0);
  44. }
  45.  
  46.  
  47. // KHAI BÁO BIẾN LƯU TRỮ KẾT QUẢ TỔNG KẾT
  48. vector<vector<int>> valid_configs;
  49. long long total_checked = 0;
  50.  
  51.  
  52. void generateAndFilterPartitions(int remaining, int current_min, vector<int>& current, int m, int n, int i_max) {
  53.     int slots_left = m - current.size();
  54.  
  55.     int max_possible_piece = n / i_max;
  56.     if (remaining > slots_left * max_possible_piece) return;
  57.  
  58.  
  59.     if (slots_left <= 0 && remaining > 0) return;
  60.  
  61.  
  62.     // KHI ĐÃ ĐIỀN ĐỦ M PHẦN TỬ VÀ TỔNG BẰNG N
  63.     if (remaining == 0 && slots_left == 0) {
  64.         total_checked++;
  65.         bool isValid = true;
  66.  
  67.         // Kiểm tra điều kiện
  68.         for (int k = i_max; k >= 2; --k) {
  69.             if (!canDivide(current, k, n / k)) {
  70.                 isValid = false;
  71.                 break;
  72.             }
  73.         }
  74.  
  75.         // IN RA TERMINAL THEO THỜI GIAN THỰC
  76.         cout << "(";
  77.         for (size_t j = 0; j < current.size(); ++j) {
  78.             cout << current[j];
  79.             if (j < current.size() - 1) cout << ",";
  80.         }
  81.         cout << ") " << (isValid ? "NHAN GIA TRI NAY" : "") << "\n";
  82.  
  83.         // Nếu hợp lệ, lưu trữ lại để in tổng kết
  84.         if (isValid) {
  85.             valid_configs.push_back(current);
  86.         }
  87.         return;
  88.     }
  89.  
  90.  
  91.     int upper_bound = min(remaining, max_possible_piece);
  92.     for (int val = current_min; val <= upper_bound; ++val) {
  93.         current.push_back(val);
  94.         generateAndFilterPartitions(remaining - val, val, current, m, n, i_max);
  95.         current.pop_back();
  96.     }
  97. }
  98.  
  99.  
  100. int main() {
  101.     int i_max, m;
  102.     cout << "Nhap so khach toi da i (tu 1 den i): ";
  103.     if (!(cin >> i_max)) return 0;
  104.  
  105.     long long n = 1;
  106.     for (int k = 1; k <= i_max; ++k) {
  107.         n = lcm(n, k);
  108.     }
  109.     cout << "=> Da tinh Mau so chung (LCM) n = " << n << "\n";
  110.  
  111.  
  112.     cout << "Nhap so manh banh m can kiem tra: ";
  113.     if (!(cin >> m)) return 0;
  114.  
  115.  
  116.     cout << "\nDang kiem tra tung phan hoach...\n";
  117.     cout << "--------------------------------\n";
  118.  
  119.     vector<int> current;
  120.     current.reserve(m);
  121.  
  122.     // Bắt đầu sinh và in real-time
  123.     generateAndFilterPartitions(n, 1, current, m, n, i_max);
  124.  
  125.  
  126.     // PHẦN TỔNG KẾT CUỐI CÙNG
  127.     cout << "--------------------------------\n";
  128.     cout << "Da kiem tra tong cong: " << total_checked << " cau hinh.\n";
  129.     cout << "So cau hinh THOA MAN: " << valid_configs.size() << "\n\n";
  130.  
  131.     if (!valid_configs.empty()) {
  132.         cout << "DANH SACH CAC CAU HINH NHAN:\n";
  133.         for (size_t i = 0; i < valid_configs.size(); ++i) {
  134.             cout << "Bo " << i + 1 << ": (";
  135.             for (size_t j = 0; j < valid_configs[i].size(); ++j) {
  136.                 cout << valid_configs[i][j];
  137.                 if (j < valid_configs[i].size() - 1) cout << ",";
  138.             }
  139.             cout << ")\n";
  140.         }
  141.     } else {
  142.         cout << "Khong co cau hinh nao thoa man!\n";
  143.     }
  144.  
  145.     return 0;
  146. }
  147.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Nhap so khach toi da i (tu 1 den i):
https://ideone.com/AOvkxB
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!