Số cặp bạn bè tối thiểu/tối đa khi chia n người thành m nhóm C++

Đề bài

n người chia thành m nhóm (mỗi nhóm ≥ 1 người). Mọi cặp trong cùng nhóm trở thành bạn. Tìm min và max số cặp bạn có thể hình thành.

Công thức

• Max: Gom n-m+1 người vào 1 nhóm, các nhóm còn lại 1 người. Max = (n-m+1)(n-m)/2
• Min: Phân bố đều nhất có thể. Min = m × C(q+1,2) + r × (q+1) với q = (n-m)/m, r = (n-m)%m

Ví dụ minh họa

#include <iostream>
#include <cmath>
using namespace std;

void getPairs(int n, int m) {
    int maxPairs = ((n - m + 1) * (n - m)) / 2;
    int q = (n - m) / m;
    int r = (n - m) % m;
    int minPairs = m * (q + 1) * q / 2 + r * (q + 1);
    
    cout << "So cap toi thieu = " << minPairs << "\n";
    cout << "So cap toi da = " << maxPairs << "\n";
}

int main() {
    getPairs(3, 2);
    return 0;
}

Kết quả

So cap toi thieu = 1
So cap toi da = 1