| ENG RUS | Timus Online Judge |
Discussion of Problem 2025. Line FightingJohn SPOILER: My proof on why solution idea works // Problem 2025. Line Fighting 14 Jan 2022 16:36 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 :) [MAI] do_v_5_strok No subject // Problem 2025. Line Fighting 3 Feb 2021 21:49 Edited by author 03.02.2021 23:21 Edited by author 03.02.2021 23:21 Edited by author 03.02.2021 23:21 ivan pasechnik`~ AC on python 3.6 [1] // Problem 2025. Line Fighting 18 Dec 2018 19:24 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) Mapu AC on python 3.6 // Problem 2025. Line Fighting 19 Aug 2019 22:05 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 против всех оставшихся и, поскольку учли каждый бой по два раза (для обоих участников), делим пополам =) Ntstharen AC Visual C // Problem 2025. Line Fighting 17 Aug 2019 21:01 #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; } ∭Andreyka∭ No subject // Problem 2025. Line Fighting 14 Jul 2019 12:16 hEdited by author 19.07.2019 12:15 Edited by author 19.07.2019 12:16 Anti Sirius SIRIUS [3] // Problem 2025. Line Fighting 25 Oct 2014 16:34 qalesan v1rus_uz Re: SIRIUS [1] // Problem 2025. Line Fighting 5 Nov 2014 01:58 yaxshi :) Nodir NAZAROV [TUIT-Karshi] Re: SIRIUS // Problem 2025. Line Fighting 8 Dec 2014 19:14 hormela! egardoz🔥 Re: SIRIUS // Problem 2025. Line Fighting 1 Mar 2019 21:45 nima uchun o'zbek tilida gapirasiz? Evgeny Shulgin hint [1] // Problem 2025. Line Fighting 1 Mar 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 :) Volodymyr Sharayenko Re: hint // Problem 2025. Line Fighting 23 Oct 2018 06:32 And how to calculate the amount of combinations after I have the team distribution list? Thank you Alibi Can you help me!? Why this approach is correct? [1] // Problem 2025. Line Fighting 13 Nov 2015 13:36 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 :) dustbite Re: Can you help me!? Why this approach is correct? // Problem 2025. Line Fighting 7 Nov 2016 22:50 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 mberdyshev Hint and some tests // Problem 2025. Line Fighting 23 Dec 2015 22:31 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 kzSysadmin Test 2 WA // Problem 2025. Line Fighting 1 Feb 2015 17:42 What's in test 2? As I understand, it's not necessary that number of people in each team is the same.
|