C/C++ Coding Exercise – 2025. Line Fighting – Timus Online Judge

The following puzzle is taken from Timus Online Judge and You can submit your solution at this URL: http://acm.timus.ru/problem.aspx?space=1&num=2025

acm-timus-2015-line-fighting-cplusplus-solution

We first compute the average size n/k so we can put the first n%k teams (n/k+1) and the rest n/k. For example, if n=8 and k=3, the first 8%3=2 teams will be size of 8/3+1=3 and the third team will be size of 2 so all add up to 8 = 3 + 3 + 2.

The next step is just to have nested loops (2-dimensional) to sum up each permutation. This way, we have the maximum number of fights.

#include <iostream>
// https://helloacm.com
using namespace std;

int fight(int n, int k) {
    int arr[k];
    int n1 = n % k;
    int n2 = n / k;
    // try to put (n2+1) - average size team as many as possible
    for (int i = 0; i < n1; i ++) {
        arr[i] = n2 + 1;
    }
    for (int i = n1; i < k; i ++) {
        arr[i] = n2;
    }
    int ans = 0;
    for (int i = 0; i < k - 1; i ++) {
        for (int j = i + 1; j < k; j ++) {
            ans += arr[i] * arr[j]; // permutation sum
        }
    }
    return ans;
}

int main()
{
    int t, n, k;
    cin >> t;
    for (int i = 0; i < t; i ++) {
        cin >> n >> k;
        cout << fight(n, k) << endl;
    }
    return 0;
}

–EOF (The Ultimate Computing & Technology Blog) —