Codeforces 536A - Tavas and Karafs

Problem Statement:
536A - Tavas and Karafs


Solution (from the official editorial, which is more succinctly written. I'm placing it here for my self reference.):
Given a sequence \(s_i\), we are only allowed to perform m-operation: choose at most m numbers in the sequence and decrease them by 1. Then it is provable that by performing at most t m-operation, we can reduce all \(s_i\) to 0, if and only if \( \max s_i \leq t\) and \( \sum_i s_i \leq tm \).
Proof:
Forward direction: if we can reduce all \(s_i\) using t operations, then it is clear that the biggest \(s_i\) must not exceed t, and that the total sum of \(s_i\) will not be more than \(mt\). The interesting part is to prove that this conditions are sufficient.


Backward direction: given that we have \(max s_i \leq t\) and \( \sum_i s_i \leq mt\), we will prove that we can reduce all \(s_i\) to 0. The proof is due to mathematical induction on the total sum of \(s_i\). Suppose that for all \(s_i\) such that \(\sum s_i \leq K\) satisfying the above conditions for all possible (m,t) are all reducible to 0. We will show that it is also true for all \(\sum s_i = K+1\). We have two possibilities:
1. There are at least m \(s_i\) which are non-zero, hence there are at most m \(s_i\) which are equal to t (otherwise, if there are more than m \(s_i\) equal to t, then their sum will be more than mt, a contradiction). We perform one m-operation on these m numbers containing all \(s_i\) with value equals to t. The resulting \(s_i\) will have maximum of t-1, with sum at most K. By induction definition, the resulting \(s_i\) can be reduced to 0 using at most t-1 m-operation, and therefore the original \(s_i\) can be reduced to 0 using at most t m-operation.
2. There are less than m \(s_i\) which are non-zero. We perform one m-operation on these numbers, hence the resulting \(s_i\) will have a maximum of t-1, with sum at most K. Hence similar to case 1, we conclude that the original \(s_i\) is reducible using at most t m-operation.

The base case would be K = 0, where the sum of \(s_i\) must be equal to 0, hence maximum \(s_i\) is 0, and it requires 0 time of m-operation to reduce all \(s_i\) to 0.

With this results, the problem can be solved using a binary search as follows:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int a, b, n;
int l, t, m;
int main(){
    scanf("%d%d%d",&a,&b,&n);
    for(int i=0;i<n;++i){
        scanf("%d%d%d",&l,&t,&m);
        int lo = l, hi = (int)1e9, mid;
        while(lo<=hi){
            mid = (lo+hi)/2;
            long long val = 1LL*(2LL*a + 1LL*(l+mid-2)*b)*(mid-l+1)/2LL;
            if(1LL*a+1LL*b*(mid-1) > t ||
                val > 1LL*m*t) {
                hi = mid-1;
            } else {
                lo = mid+1;
            }
        }
        if(hi >= l) printf("%d\n",hi);
        else printf("-1\n");
    }
    return 0;
}