Proficient.
Put your skills to the test.

Problem summary

Recover N hidden integer lines f(x)=ax+b using queries for their maximum at integer x. Slopes are distinct, and each line attains the maximum at at least three integers in the allowed interval. Despite its title, this task is unrelated to greatest common divisors.

Constraints

1 ≤ N ≤ 100000; |a| ≤ 1000000000; |b| ≤ 1000000000000000000. Each line is maximal at ≥3 integer x values; slopes differ. Q > 5000000 or a wrong line gives zero. Otherwise score = min(0.25+0.75(4N/Q)^2,1).

Worked example

The official example is an illustrative interaction, not standard input/output. The implementation uses different query coordinates and may report the same lines in its own order.

solve(2)
query(1) -> 4
query(5) -> 0
query(6) -> 1

answer(-1, 5)
answer(1, -5)

Solution analysis

1. At the left boundary, the first line remains maximal at the next integer, because it has at least three integer support points. Two adjacent envelope values therefore give its slope and intercept. Cache all queries.
2. For a known line and a support coordinate s, equality between the envelope and this line holds on an interval. To its right, the predicate envelope(x)>line(x) is monotone. Binary search the first strict departure p. The next line is maximal at both p and p+1, allowing its coefficients to be recovered by another adjacent difference.
3. Ties do not break this argument. If the next line already tied at p−1, its three-integer guarantee still leaves p and p+1 as support points. A later line cannot take over before then without leaving that next line fewer than three support integers. In the example, the two lines meet at x=5; the strict departure from −x+5 is x=6.
4. Output each line and stop after N discoveries, avoiding a search beyond the final line. Each transition uses at most 31 bisection queries plus the final pair, so Q ≤ 2+33(N−1) < 5000000. This ensures validity of the query budget but does not guarantee maximum score.

Why it works

The maximum of lines is convex; its supported slopes occur in increasing order and each line has a single closed support interval. The first two coordinates lie in the first support interval. If the current line loses strict maximality at p, the following supported line is maximal at p. Integer support intervals of at least three points force it also to support p+1, even when the prior endpoint is a tie. Adjacent differences thus recover exactly that line. Induction recovers every supported line once, and all N lines are supported by assumption.

Watch out. Use 64-bit arithmetic for values and ax+b. Never query outside the permitted interval. A strict comparison is essential at crossings. Stop after exactly N answers.

Actual gcd5.h grader interface. This is a bounded full-domain recovery algorithm, not a 30-query numeric GCD method. It favors a straightforward proof over optimal query count.

#include"gcd5.h"
#include<map>
// Algorithm: At the left boundary, the first line remains maximal at the next integer, because
// it has at least three integer support points.
namespace{
std::map<int,long long>cache;
long long get(int x){
    auto found=cache.find(x);
    if(found!=cache.end()){
        return found->second;
    }
    long long value=query(x);
    cache[x]=value;
    return value;
}
} // namespace
void solve(int n){
    cache.clear();
    const int left=-1000000000;
    const int right=1000000000;
    int support=left;
    long long value=get(support);
    long long slope=get(support+1)-value;
    long long intercept=value-slope*support;
    for(int found=0;found<n;++found){
        answer(slope,intercept);
        if(found+1==n){
            break;
        }
        int low=support;
        int high=right;
        while(high-low>1){
            int middle=low+(high-low)/2;
            if(get(middle)>slope*middle+intercept){
                high=middle;
            }
            else{
                low=middle;
            }
        }
        support=high;
        value=get(support);
        slope=get(support+1)-value;
        intercept=value-slope*support;
    }
}