In this HackerEarth Three rectangles problem solution, You are given a rectangle of height H and width W. You must divide this rectangle exactly into three pieces such that each piece is a rectangle of integral height and width. You are required to minimize Area(max) - Area(min) where Area(max) is the area of the largest rectangle and Area(min) is the area of the smallest rectangle, among all three rectangle pieces.
HackerEarth Three rectangles problem solution.
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define fix fixed<<setprecision(10)
#define rep(i,a,b) for(int i=int(a);i<=int(b);i++)
#define repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define FastIO ios_base::sync_with_stdio(0),cin.tie(0)
typedef double db;
typedef long long ll;
const int N=2e5+5;
const int mod=1e9+7;
void solve(){
ll h,w;
cin>>h>>w;
ll ans=1e18;
rep(i,1,h-1){
ll nh=h-i,nw=w;
ll maxi=max({i*nw,nh/2*nw,(nh-nh/2)*nw});
ll mini=min({i*nw,nh/2*nw,(nh-nh/2)*nw});
ans=min(ans,maxi-mini);
maxi=max({i*nw,nw/2*nh,(nw-nw/2)*nh});
mini=min({i*nw,nw/2*nh,(nw-nw/2)*nh});
ans=min(ans,maxi-mini);
}
rep(i,1,w-1){
ll nw=w-i,nh=h;
ll maxi=max({i*nh,nw/2*nh,(nw-nw/2)*nh});
ll mini=min({i*nh,nw/2*nh,(nw-nw/2)*nh});
ans=min(ans,maxi-mini);
maxi=max({i*nh,nh/2*nw,(nh-nh/2)*nw});
mini=min({i*nh,nh/2*nw,(nh-nh/2)*nw});
ans=min(ans,maxi-mini);
}
cout<<ans<<'\n';
}
signed main(){
FastIO;
int t;
cin>>t;
while(t--) solve();
return 0;
}
Second solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 14;
int solve(int h, int w) {
int ans = INT_MAX;
for (auto x : {(ll) w * h / (3 * h / 2), (ll) w * h / (3 * h / 2) + 1})
ans = min<ll>(ans, max({abs(x * ll(h / 2) - ll(w - x) * h), x * ll((h + 1) / 2) - ll(w - x) * h, h % 2 * x}));
return ans;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
int h, w;
cin >> h >> w;
cout << min({h % 3 == 0 || w % 3 == 0 ? 0 : min(h, w), solve(h, w), solve(w, h)}) << '\n';
}
}
0 Comments