Placing Plates
Time limit1sMemory limit1024 MB
Given an a by b grid and p plates of size 1 by s, decide whether every plate can be placed horizontally or vertically without overlapping.
- Level
Medium6 of 10
- Topics
- Backtracking, Matrix, Brute force
- Solved
- No attempts yet
Problem
The restaurant you work for has recently changed management. It will close, renovate and remodel, and reopen under a new name with a new menu. The executive chef has asked you to help redesign the kitchen so it is more efficient and fits the new vision. Management knows you are a computer science student, so they expect you to focus on efficiency.
While designing the dishwasher area, management wants the outgoing side for clean plates to be divided so that each plate has its own designated spot. Each spot is separated from the others by a horizontal or vertical divider, so a new employee can learn the system easily.
To keep costs low, you need to know whether all the plates fit in the space you have laid out.
Input
You are given the number of test cases c (1 ≤ c ≤ 100). Each test case gives two integers a and b (2 ≤ a ≤ b ≤ 100) that describe the size of the clean plate area. The next line gives the number of plates p (1 ≤ p ≤ 15). Each of the next p lines gives a size s (1 ≤ s ≤ 1000) for one plate, which occupies a space of size 1 x s.
Adjacent test cases are separated by a blank line.
Output
For each test case, print one line. Print Yes if every plate can be placed in the rectangular area without overlapping. Otherwise, print See management.