PROBLEM LINK:
Author: Rahul Sharma
Tester: Sumukh Bhardwaj
Editorialist: Rahul Sharma
DIFFICULTY:
Easy
PREREQUISITES:
gcd, observation
PROBLEM:
Given a hollow cuboid L_h,B_h,H_h and an interger K. You need to select and fill it with solid cuboid such that each solid cuboid satisfy following conditions
L_s == B_s == A
1 \leq A \leq min(L_h, B_h)
1 \leq H_s \leq K
Find minimum number of solid cuboids required
QUICK EXPLANATION:
Make use of Euclidean GDC algorithm to find number of squares required to fill rectangle L_h, b_h and multiply that with number of minimum slabs of height H_s required.
EXPLANATION:
Subtask #1:
Since L_h==B_h for this subtask, therefore it is clear we need solid cuboids whose L_s == B_s == L_h == B_h. We only need to check the height parameter to get minimum count.
minimumSolidCuboids = ceil(H_h / K)
Subtask #2:
For this subtask, We will first solve the subpart,
Count minimum number of squares required to fill a rectangle L_h, B_h. We will count the number of squares with side length A = min(L_h, B_h) and update the L_h and B_h accordingly.
In case L_h > B_h then L_s = B_h, minSquares+=L_h/B_h
L_h = L_h \mod B_h
Similarly if L_h < B_h. This process is continued till L_h \mod B_h is zero or vica versa. Thus we get the count of minimum squares.
Let us consider an example where lenght and breadth of rectangle are as follows
L_h=9, B_h=4
We would need 6 squares to fill it up
2 squares with side length 4
4 squares with side lenght 1
Note: This is also the way gcd is calculated
For the second part since we need to calculate solid cuboids
We will now focus on height part i.e. H_s Minimum solid cuboids required to fill volume L_h*B_h*H_s is minSquares count.
Thus finally to fill complete hollow cuboid with minimum solid cuboid is given as
minimumSolidCuboids = minSquares*ceil(H_h / K)
Euclidean algorithm is used to solve this problem.
COMPLEXITIES:
Time Complexity: O(log(min(L_h, B_h)) for each test case
Space Complexity: O(1) for each test case
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
long long int minSquares(long long int l, long long int b)
{
if(b == 0)
return 0;
return l/b + minSquares(b, l%b);
}
int main()
{
long long int l, b, h, k;
cin >> l >> b >> h;
cin >> k;
long long int minSquaresCount = minSquares(l,b);
long long minSolidCuboids = 0;
if(h%k == 0)
minSolidCuboids = (h/k)*minSquaresCount;
else
minSolidCuboids = (h/k + 1)*minSquaresCount;
cout << minSolidCuboids;
}