# 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;
}
```