Intermediate.
Put your skills to the test.

Problem summary

Use all1×1 squares and horizontal1×L bars to make a solid rectangle with every internal vertical cut crossed by a bar. List all dimensions.

Constraints

0≤A,B≤10^9;A+B>0;2≤L≤10.

Worked example

Input and output for the worked example discussed below.

6 3 2

3
2 6
3 4
4 3

Solution analysis

1. Area S=A+LB fixes height for every divisor width. Width1 needs no bars; height1 must contain a single block. For greater height, widthL works if a bar exists; narrower widths above1 cannot bridge cuts.
2. For W>L, bars must cover W−1 cuts, requiring B≥ceil((W−1)/(L−1)). If r=W mod L>0, each row requires at least r squares, so A≥height×r. If r=0, at least L squares are needed to shift one row off the common joints.
3. These conditions also permit a staggered packing: use available squares to shift bar rows and distribute crossing bars over successive groups of cuts; remaining blocks fill row capacity. For6,3,2, area12 permits widths2,3,4 and heights6,4,3.

Why it works

Divisibility, cut coverage, and row remainder/offset capacity are necessary. Apart from the separately handled single-row and narrow-width cases, staggered rows using these squares let the required bars cover every internal cut; the residual row capacity accommodates all remaining blocks. Thus the stated criterion exactly characterizes feasible dimensions.

Watch out. Bars cannot rotate vertically. Width and height therefore differ. Avoid duplicate square-area divisor pairs and use64-bit arithmetic.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
// Divisibility, cut coverage, and row remainder/offset capacity are necessary.
bool possible(long long w,long long h,long long a,long long b,long long l){
    if(h==1){
        return (w==1&&a==1&&b==0)||(w==l&&a==0&&b==1);
    }
    if(w==1){
        return b==0;
    }
    if(w==l){
        return b>0;
    }
    if(w<l){
        return false;
    }
    if(b<(w+l-3)/(l-1)){
        return false;
    }
    return w%l==0?a>=l:a>=h*(w%l);
}
int main(){
    long long a,b,l;
    cin>>a>>b>>l;
    long long area=a+b*l;
    vector<pair<long long,long long>>answers;
    for(long long d=1;d*d<=area;d++){
        if(area%d){
            continue;
        }
        long long other=area/d;
        if(possible(d,other,a,b,l)){
            answers.push_back({d,other});
        }
        if(d!=other&&possible(other,d,a,b,l)){
            answers.push_back({other,d});
        }
    }
    sort(answers.begin(),answers.end());
    cout<<answers.size()<<'\n';
    for(auto[w,h]:answers){
        cout<<w<<' '<<h<<'\n';
    }
}