I proposed a problem called “Problem A – Mehdi and the Box” which was on Scorify platform, and I would like to share its simple solution in this post. I am very happy because it was a clear and all the contestants solved it.
And the hero was my friend Mehdi Laziri. So, this problem was a gift for him.
Mehdi is a smart guy who want to put his pens in a 2D box. The problem is that he has N pens with different lengths, and he wants to check if he can put the pen Pi in the box.
The first line consists of T the number of testcases 1 <= T <= 100.
The second line has 3 integers 1 <= N <= 1000, 1 <= W <= 10000, and 1 <= H <= 10000, the number of pens, the width of the box, and the hight of the box followed by N lines with the length of the pen Pi.
For each pen Pi, if it can fit in the box output “YES” (without quotes). Otherwise, output “NO” (without quotes).
2 12 17
The first thing that should came to our heads is the idea that the diagonal is the longest part of a rectangle since we have just a 2D box. So, we should compare the length of each pen with the diagonal of the rectangle. Formally, the following relation should be satisfied H^2 + W^2 > L^2 .
We have N queries and since the answer of each query is O(1), the answer of N queries will be in O(N).