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;
}