Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | 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. |
|
|