First of all, we need to understand which number of teams x (from 2 to k) we need to pick to distribute our fighters into.

Through intuition we might get the idea that the bigger the K **the more the fights** (which is what is required).
It can be proven that our intuition is correct; the more you divide n the better the result, therefore we will need to divide n by k.
Proof: assuming we have n = 3, now let us assume we will distribute them to 1 team where the first team is of 3 fighters, there will be 0 fights, let us now assume we will distribute them to 2 teams where the first is of 2 and second is of 1 fighters, there will be 2 fights, lastly let us assume that we will distribute them to 3 teams where each team has a fighter, there will be 3 fights, we can then deduce that for each fighter you divide into a new group more fights are formed.
Conclusion: It is always the best choice to divide by the biggest possible number you can divide by, thus we will always divide by K.


To solve the problem we can then deduce that there will always be two cases:
Case 1 (k divides n): here we simply divide fighters into k groups, each group (composed of (n/k) fighters) will fight some other group (composed of (n/k) fighters) thus the equation for the first case is simply:
(k * (k - 1) / 2) * (n / k)^2

Case 2 (k doesn't divide n): here we notice that n will be composed of x count of floor(n / k) and y count of ceil(n / k) meaning floor(n/k)*x + ceil(n/k)*y = n, and that obviously, x + y = k, through these equations we can deduce algebraically the values of x and y, and from it form our equation.
Our equation will have x groups of floor (n / k) fighters which within them will form a specific number of fights, we will also have y groups of ceil (n / k) fighters which within them will form a specific number of fights, then we will also need an to find an equation that calculates the number of fights that happens between the x groups and the y groups, through observation and deduction you will find that this will be the equation of the second case:
((x * (x - 1) / 2) * (floor(n/k))^2) +
((y * (y - 1) / 2) * (ceil(n/k))^2) +
(floor(n/k) * ceil(n/k)) * x * y



Code:
```
#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;    std::cin >> t;
    while (t--) {
        int n, k;    std::cin >> n >> k;
        if (n % k == 0) {
            int count = k * (k - 1) / 2;
            std::cout << count * (n / k) * (n / k) << '\n';
        } else {
            int x = n - ((n + k - 1) / k) * k;
            x = x / ((n / k) - ((n + k - 1) / k));
            int y = k - x;

            int part1 = (x * (x - 1) / 2) * (n / k) * (n / k);
            int part2 = (y * (y - 1) / 2) * ((n + k - 1) / k) * ((n + k - 1) / k);
            int part3 = (n / k) * ((n + k - 1) / k) * x * y;
            std::cout << part1 + part2 + part3 << '\n';
        }
    }

    return 0;
}
```

Edited by author 18.10.2025 15:04

Edited by author 18.10.2025 15:06

Edited by author 30.10.2025 12:18

So we must try to make teams have equal size. Why?
Consider two teams with x and y members respectively, and consider x > y. Sending a member from first team to second team will only affect matches between these two teams. At first we have x*y different matches between the teams. If we send a player to the second team, there are now x-1 and y+1 members in each team. The matches are now
(x-1)*(y+1) = x*y + (x-y) - 1
As we said x > y, x-y > 0, so x-y-1 >= 0 and our change can't reduce the total number of matches, so it is an optimal change.
This also shows that nothing changes when x = y+1, so if we can't make all teams equal size, just add each of the ones remaining into a different team, making a difference of at most 1 in the sizes of teams.

Now it's your job to compute the number of matches, I won't show that, but it can be done with a one line formula. Good luck :)

Edited by author 03.02.2021 23:21

Edited by author 03.02.2021 23:21

Edited by author 03.02.2021 23:21

t = int(input())
for i in range(t):
    m = []
    kv = 0
    n,k = map(int,input().split())
    ok =k
    for i in range (k):
        if i == 0:
            m.append(n//ok)
            kv += m[i]
            n-=n//ok
            ok-=1
        else:
            if i == k-1:
                m.append(n)
            else:
                m.append(n//ok)
                kv+=m[i]
                n-=n//ok
                ok-=1
    otr,ans = 0,0
    l,l1 = 0,0
    m.sort()
    m.reverse()
    ss = sum(m)
    for i in range(k-1):
        l += m[i]
        l1 = m[i]
        ans += (ss-l)*l1
    print(ans)

#include<stdio.h>

int main(){
    int N, n, k, i, a, b, x, res;
    scanf("%d\n", &N);
    for(i=0; i<N; i++){
        scanf("%d %d", &n, &k);
        if(n%k==0){
            x=n/k;
            res=n*(n-x)/2;
            printf("%d\n", res);
        }
        else {
            x=n/k;
            b=n-k*x;
            a=k-b;
            res=((n-x)*a*x+(n-x-1)*(x+1)*b)/2;
            printf("%d\n", res);
        }
    }
    return 0;
}

hEdited by author 19.07.2019 12:15


Edited by author 19.07.2019 12:16

qalesan

You have to divide the participants into equal teams (rounded)
For example, for "15 10" test - (1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
Good luck :)

You have to divide the participants into equal teams (rounded)
For example, for "15 10" test - (1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
Good luck :)

maximize amount of teams, but minimize max amount of fighters in a team.
For example, if n=9, k=5, you should make 5 teams this way: (2, 2, 2, 2, 1)
Tests:
Input:
3
7 4
9 4
12 5
Output:
18
30
57

Edited by author 23.12.2015 22:42

What's in test 2?
As I understand, it's not necessary that number of people in each team is the same.