T-Shirt Pockets
Autumn Tournament (2007)
Submission name: t-shirt.cpp
Problem summary
Cut identical x by y rectangular pockets from an a by b rectangle of fabric. All pockets must share one orientation: mixing rotated and unrotated pockets is forbidden. Find the maximum number and the total unused area.
Source clarification. No dimension bounds are printed in the source; this solution uses signed 64-bit arithmetic for dimensions and areas. The prose specifies two output lines; the PDF sample table places the two values side by side.
Input
Four positive integer dimensions a, b, x, y.
Output
Maximum pocket count on the first line; unused fabric area on the second.
Constraints
The original statement supplies no numerical bounds.
Worked example
Original statement sample.
Input
6 8 2 3
Output
8 0
Solution analysis
- In one orientation, floor(a/x) pockets fit across and floor(b/y) fit along the fabric. Their product is the count.
- Rotate every pocket to obtain floor(a/y) × floor(b/x). These are the two allowed choices, so keep their maximum. Unused area is a × b minus the count times x × y.
- For 6 × 8 fabric and 2 × 3 pockets, the orientations give 3 × 2 = 6 and 2 × 4 = 8 pockets. Eight pockets use all 48 square units.
Why it works
For a fixed orientation each row and column can contain at most the corresponding integer quotient, and a rectangular grid attains their product. The maximum over the two permitted orientations is therefore optimal. Subtracting the used pocket area gives exactly the unused area.
Watch out. Do not mix orientations. Use integer division for counts and subtract the area of all pockets, not just one.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a,b,x,y;
cin>>a>>b>>x>>y;
// Compare the two uniform orientations.
long long pockets=max((a/x)*(b/y),(a/y)*(b/x));
cout<<pockets<<'\n';
cout<<a*b-pockets*x*y<<'\n';
}