WeddingDanceFloor
SRM 853 · 2024-02-21 · by misof
Problem Statement
Maurice is planning a new business: running a hall which one can rent for a wedding reception. He understands that people have two basic needs when renting such a hall: you need to cram as many people as possible in it, and there has to be a large-enough dance floor for them.
The hall Maurice rents is a H by H square.
For a hall this big, the minimum size of a suitable dance floor is a D by D square.
Maurice just found a great deal to make a bulk purchase of dinner tables. Each of these tables (along with room for chairs around it) will exactly cover a 1 by T rectangle. (Each rectangle can be placed either "horizontally" or "vertically".)
Help Maurice: find out whether it's possible to arrange his hall so that there is exactly one dance floor of the smallest possible size, and the rest of the hall is completely covered with tables.
If no such arrangement exists, return an empty
If multiple such arrangements exists, you may pick any one of them. Return a
(All unit square cells that belong to the same table should have the same character. Each pair of tables that are adjacent must have different characters. You may reuse the same character for multiple mutually non-adjacent tables.)
Notes
- Tables with the same letter can touch at a corner. Tables only count as adjacent if a cell covered by the first table shares a side with a cell covered by the second table.
- For the constraints given below, if a solution exists, it is always possible to assign characters to tables in a valid way.
Constraints
- H will be between 1 and 70, inclusive.
- D will be between 1 and H, inclusive.
- T will be between 1 and H, inclusive.
- T will not exceed 25.
17
4
8
Returns: { }
Sometimes it is very obvious that Maurice cannot fill his hall optimally. For example, here the total area of his hall is odd but the total area covered by the dance floor and any number of tables is always even.
8
4
4
Returns: {"DDDD0101", "DDDD0101", "DDDD0101", "DDDD0101", "01012323", "01012323", "01012323", "01012323" }
Sometimes the solution is easy to construct, you just fill the hall greedily. One dance floor, twelve tables.
7
5
6
Returns: {"0000001", "1DDDDD1", "1DDDDD1", "1DDDDD1", "1DDDDD1", "1DDDDD1", "1000000" }
4
2
4
Returns: { }
Sometimes the areas look like everything should fit, but it still doesn't. Poor Maurice.
5
5
3
Returns: {"DDDDD", "DDDDD", "DDDDD", "DDDDD", "DDDDD" }
Having zero tables is valid.
6
2
2
Returns: {"012334", "012DD4", "566DD7", "589907", "18220A", "144zzA" }
The dance floor can be anywhere in the hall. In particular, it doesn't have to be in the corner of the hall.
Submissions are judged against all 269 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WeddingDanceFloor with a public method vector<string> cover(int H, int D, int T) · 269 test cases · 2 s / 256 MB per case