Real problems.
Your next challenge.

Problem summary

Arrange N baskets into any number of piles at positions 1,2,... . Reaching pile i costs iA seconds; reaching its j-th basket from the top costs iA+(j−1)B. Minimize the largest access time over all baskets.

Constraints

1 ≤ T ≤ 20; 1 ≤ N,A,B ≤ 2000000000.

Worked example

Original statement sample.

4
3 1 2
10 2 5
200 27 42
200 42 27

3
12
666
681

Solution analysis

1. For a proposed time X, pile i can hold 1+floor((X−iA)/B) accessible baskets when iA≤X; later piles hold none. Summing these capacities tells whether N baskets fit. Capacities only increase with X, so binary-search the smallest feasible X.
2. Do not scan up to N piles for every check: N can be two billion. Put M=floor(X/A), reverse the pile order, and write capacity=M+Σ(j=0..M−1) floor((Aj+X−MA)/B). The helper floorSum computes this arithmetic-progression floor sum by Euclidean division, repeatedly removing whole quotients and exchanging the numerator slope with the denominator.
3. For N=10,A=2,B=5 and X=12, the six pile capacities are 3,2,2,1,1,1, totaling10. At X=11 they total only8, so12 is optimal. An upper bound is min(NA,A+(N−1)B), obtained by putting all baskets in separate piles or one pile.

Why it works

A pile’s capacity is exactly the number of its access times not exceeding X. Therefore total capacity≥N is necessary and sufficient: fill any N available places. The floor-sum helper removes quotient contributions exactly, and its exchange counts the same lattice points with the axes interchanged. Monotonic feasibility then makes binary search return the optimum.

Watch out. The top basket costs iA, not iA+B. All arithmetic needs long long. Within the chosen search bound, at most N piles and at most N positions per pile are counted, so total capacity≤N²≤4·10^18 and the shown arithmetic fits signed64-bit.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
using namespace std;
// Sum floor((a*i+b)/m) for 0 <= i < n, using Euclidean reduction.
long long floorSum(long long n,long long m,long long a,long long b){
    long long answer=0;
    while(true){
        if(a>=m){
            answer+=(n*(n-1)/2)*(a/m);
            a%=m;
        }
        if(b>=m){
            answer+=n*(b/m);
            b%=m;
        }
        long long height=a*n+b;
        if(height<m){
            break;
        }
        n=height/m;
        b=height%m;
        swap(m,a);
    }
    return answer;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin>>tests;
    while(tests--){
        long long n,travel,lift;
        cin>>n>>travel>>lift;
        long long low=travel;
        long long high=min(n*travel,travel+(n-1)*lift);
        while(low<high){
            long long middle=low+(high-low)/2;
            long long piles=middle/travel;
            long long remainder=middle-piles*travel;
            long long capacity=piles+floorSum(piles,lift,travel,remainder);
            if(capacity>=n){
                high=middle;
            }
            else{
                low=middle+1;
            }
        }
        cout<<low<<'\n';
    }
}