Fighting Over Outlets (Written by @python660)
This is not a Code Help question, but a programming challenge of algorithmic nature. Feel free to propose Solutions, Test Cases, and Improvements to this question.
Problem Statement
This puzzle is inspired by “What Else Can I Plug In? - Level 1” by RomanSmoll.
You just ordered the parts for your dream gaming setup, but after attempting to plug in your n devices into your 2 vertically-stacked wall outlets, you realize that they won’t fit. However, you manage to find an old extension cord which allows x additional devices to be plugged in horizontally, at the expense of one wall outlet.
Each device comes with a rectangle-shaped plug with integer dimensions width in. x height in. Outlets have dimensions 5 in. x 5 in. and are separated with a gap of 5 in. Some plugs might cover up adjacent outlets, so plan carefully.
How many devices will you be able to plug in?
For example, the configuration of outlets and plugs in the first test case is valid because there are enough outlets for each plug, and, when arranged with the 9in. x 6in. plug directly connected to the wall outlet, each plug does not cover up adjacent plugs.
Input Format (arrives from stdin)
Line 1: Two space separated integers n and x, for the number of devices need to plug in and the number of outlets on your extension cord, respectively.
Next n lines: Two space separated integers width and height, for the dimensions of that device.
Test Case 1
INPUT
3 2
8 6
5 8
9 6
OUTPUT
3
Test Case 2
INPUT
4 3
5 7
9 5
5 5
7 7
OUTPUT
4
Test Case 3
Feel free to create your own test cases!