519C - A and B Team Training

Solution:

Nice problem, in fact the problems for this round are good stuff.

Let's express the groups as tuples (1, 2) and (2, 1), in the form of (number_of_experts, number_of_newbies). We have the following constraints :

\( a (1, 2) + b (2, 1) \leq (n, m) \)

where a and b denotes the number of groups of the respective arrangements. We want to maximize \(X = a+b \), and we can search for the maximum possible X using binary search. Rewrite the constraints in term of X and a, we have \( 2X - a \leq n\) and \( a + X \leq m \). Additionally, a must be non negative and cannot be bigger than X.

Hence for a given X, if there exist \(a\) such that \(a\) fulfils the above inequalities. If there is such \(a\), we can try bigger X. This is because for a given X, if there exists \(a\) that satisfies the inequalities, automatically all X smaller than the current X will also have that property. Very nice.

Implementation:

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int main(){ int N, M; scanf("%d%d",&N,&M); int lo = 0, hi = (N+M), mid; while(lo <= hi){ mid = (lo+hi)/2; int lower = max(0, 2*mid - N); int upper = min(mid, M-mid); if(lower <= upper) { lo = mid+1; } else { hi = mid-1; } } printf("%d\n",hi); return 0; }