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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #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; } |
#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) —
GD Star Rating
loading...
333 wordsloading...
Last Post: Review - Kingston USB 64 GB
Next Post: Disallow Multiple Instance of Applications on The Same Machine (Windows Server) by Other User Sessions (Both C# and C++ solution)
