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.

Problem Statement:

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.

Input:
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.

Output:
For each pen Pi, if it can fit in the box output “YES” (without quotes). Otherwise, output “NO” (without quotes).

Sample Input:
2 12 17
21
20

Sample Output:
NO
YES

Idea:

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 .

Time Complexity:

We have N queries and since the answer of each query is O(1), the answer of N queries will be in O(N).

A Solution in C++:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s