| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | SPOILER: My proof on why solution idea works | John | 2025. Стенка на стенку | 14 янв 2022 16:36 | 1 | 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 :) | | No subject | [MAI] do_v_5_strok | 2025. Стенка на стенку | 3 фев 2021 21:49 | 1 | Edited by author 03.02.2021 23:21
Edited by author 03.02.2021 23:21
Edited by author 03.02.2021 23:21 | | AC on python 3.6 | ivan pasechnik`~ | 2025. Стенка на стенку | 19 авг 2019 22:05 | 2 | 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) t = int(input())
for i in range(t):
n, k = [int(i) for i in input().split()]
m = n // k
q = n % k
s = (m * (n - m) * (k - q) + (m + 1) * (n - m - 1) * q) // 2
print(s)
#распределяем максимально равномерно и "деремся" команда из m против всех оставшихся + команда из m + 1 против всех оставшихся и, поскольку учли каждый бой по два раза (для обоих участников), делим пополам =) | | AC Visual C | Ntstharen | 2025. Стенка на стенку | 17 авг 2019 21:01 | 1 | #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;
} | | No subject | ∭Andreyka∭ | 2025. Стенка на стенку | 14 июл 2019 12:16 | 1 | hEdited by author 19.07.2019 12:15
Edited by author 19.07.2019 12:16 | | SIRIUS | Anti Sirius | 2025. Стенка на стенку | 1 мар 2019 21:45 | 4 | SIRIUS Anti Sirius 25 окт 2014 16:34 Re: SIRIUS Nodir NAZAROV [TUIT-Karshi] 8 дек 2014 19:14 nima uchun o'zbek tilida gapirasiz? | | hint | Evgeny Shulgin | 2025. Стенка на стенку | 23 окт 2018 06:32 | 2 | hint Evgeny Shulgin 1 мар 2015 18:05 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 :) Re: hint Volodymyr Sharayenko 23 окт 2018 06:32 And how to calculate the amount of combinations after I have the team distribution list?
Thank you | | Can you help me!? Why this approach is correct? | Alibi | 2025. Стенка на стенку | 7 ноя 2016 22:50 | 2 | 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 :) Well I don't understand this topic CLEARLY but I can trace some steps towards the final solution.
Let's fix a possible team distribution i.e. number of teams
Then, we need to find the best possible distribution to maximize the product
For eg for 4 teams a1,a2,a3,a4 will be the team distribution
a1+a2+a3+a4=n
now we need to maximize the function f(a1,a2,a3,a4)=a1a2+a1a3+a1a4+a2a3+a2a4+a3a4
under the constraint a1+a2+a3+a4=n, which can be done using lagrangian multiplier.
g(a1,a2,a3,a4)=f(a1,a2,a3,a4)+p(n-a1-a2-a3-a4)
lets take derivative of the function g at a1
g'(a1) = a2+a3+a4 -p
g'(a2) = a1+a3+a4 -p
g'(a3) = a1+a2+a4 - p
g'(a4) = a1+a2+a3 - p
Equate all of them to zero
a1+a2+a3=a2+a3+a4=a1+a3+a4=a1+a2+a4=p
from 1st and second we find a1=a4
from 2nd and 3rd a2=a1
similarly we find a1=a2=a3=a4, all a's must be equal
so a1+a2+a3+a4=n
a1=n/4
In general
a1=n/p, where p is the number of teams.
When p is not divisible, we need to make all of them as equal as possible by distributing n % p.
I don't understand lagrangian multiplier by heart(I have not tried to). But the tool works here.
We can try bruteforcing all possible team numbers from 2 to k and find which is best.
Edited by author 07.11.2016 22:51 | | Hint and some tests | mberdyshev | 2025. Стенка на стенку | 23 дек 2015 22:31 | 1 | 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 | | Test 2 WA | kzSysadmin | 2025. Стенка на стенку | 1 фев 2015 17:42 | 1 | What's in test 2?
As I understand, it's not necessary that number of people in each team is the same. |
|
|
