Posted by : MCMASTER ACM Saturday, June 25, 2016

Codeforces 478B | Random Teams



Question:

Solution:
#include <iostream>
using namespace std;
int main(){
 
 
  long long n , m; // inputs
  cin >> n >> m;// grab em
  
  // maximum 
 long long  kmx  = n- m +1; // get the max number of people in one team so for 
example if 6 ppl and 3 teams the max is 4 since the other 2 teams will hv only one person 
         kmx=  kmx*(kmx-1)/2; // now match every one with his friends using the 
famous formula n*(n-1)/2 which accounts for each person as n and (n-1)/2 
are the relationships he/she might make with others (n-1) since relationships are 
undirected which means a loves b == b loves a we should divide by 2  
    
     //minimum ( real bad )
 long long kmn = ((n / m) * ((n / m) - 1)) / 2; // get possible pairings PER TEAM in 
uniform teams example 6 ppl 3 teams 6/3 is uniform number which is 2 per team 

  if(n % m == 0){
   kmn *= m; // special case 
  }else{
   kmn *= m - (n % m); // without leftovers ppl who got no uniform team
 ( n%m is the number of teams who hv no uniform number of ppl) since this is the 
remainder of a unifrom division right ?
   // now kmn accounts for pairings in uniform teams only 
   
   long long lft =(((n / m) + 1 ) * (n / m)) / 2; // now leftovers ! // lft has possible pairings 
   kmn += lft * (n % m); // multiply possible pairings per person by 
the number of lftovers and add them to kmn
  }
 cout << kmn << " " << kmx << endl; // print them !
 
 // we done boyzz 
 
 
} 
// ez@macacm.org -- 01:03AM 23-06-2016
// Ezzeldin Adel Tahoun || McMaster University




Video Explanation: 





If you want us to solve any certain question please leave it down in the comments or send it to us on facebook

Leave a Reply

Subscribe to Posts | Subscribe to Comments

Discover

Top 5 Posts

- Copyright © McMaster ACM Chapter | Protected by CloudFlare