ConstructionFromMatches
TCCC07 Qual 1 · 2007-07-30 · by ivan_metelsky
Problem Statement
There is a shop in your city, in which matches of different integer thicknesses from 1 to N, inclusive, are sold. All matches in the shop have the same length. The (i-1)-th element of cost is the cost of one match with thickness i.
You wish to buy some matches and use them to construct a 2xM rectangle. For example, if M=5, then the rectangle will look as follows (characters '|' and '-' correspond to matches):
_ _ _ _ _ | | | | | | _ _ _ _ _ | | | | | | _ _ _ _ _
You are given two int[]s, top and bottom, each containing exactly M elements. top and bottom contain the required thicknesses of the squares in the top and bottom rows of the rectangle, respectively, from left to right. The thickness of a square is the sum of the thicknesses of its four sides. Return the minimum total cost of matches needed to construct the required rectangle, or -1 if it's not possible.
Constraints
- cost will contain between 1 and 12 elements, inclusive.
- Each element of cost will be between 1 and 100000, inclusive.
- Elements of cost will be in strictly ascending order.
- top will contain between 1 and 50 elements, inclusive.
- bottom will contain the same number of elements as top.
- Each element of top and bottom will be between 4 and 48, inclusive.
{1638,3631,21834,23257,32573,33361,35554,56818,60066,60102,69211,80348}
{8,41,30,47,15,12,37,10,34,36,29,32,42,15,8,19,32,27,8,34,22,7,24,41,32,32,36,45,4,22,9,28,16,20,24,26,25,28,30,24,15,48,22,13,30,17,7,37,29,19}
{14,22,12,44,17,9,29,42,26,23,21,15,42,27,39,22,48,10,44,30,20,6,24,24,31,6,39,34,28,25,5,43,22,15,22,11,42,14,21,8,9,38,21,40,38,8,14,12,19,35}
Returns: -1
{10665,19996,22429,31085,43854,45183,52066,63045,65723,68213,81907,97519}
{20,26,33,39,25,25,26,29,18,25,23,27,22,18,23,33,34,17,30,23,22,27,28,22,33,28,20,31,42,30,33,17,21,27,25,25,30,32,29,28,31,18,12,15,24,26,27,26,20,14}
{25,29,28,29,17,39,30,27,33,30,17,27,39,27,29,27,17,16,37,32,25,22,27,21,18,21,33,23,14,21,26,18,25,37,25,21,24,27,23,35,40,19,27,17,12,30,36,19,23,20}
Returns: 10238433
{100000}
{4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4}
{4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4}
Returns: 25200000
{1}
{4}
{4}
Returns: 7
{7675,9857,12637,39508,53411,68010,69118,70753,75819,83052,85228,87250}
{48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48}
{48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48,48}
Returns: 21987000
{1, 2}
{7}
{5}
Returns: 10
The cheapest solution contains 3 matches of thickness 2 and 4 matches of thickness 1. It may look as follows (each digit d denotes a single match of thickness d): 1 2 2 2 1 1 1
{1}
{5}
{5}
Returns: -1
Obviously we can't get a square with thickness 5 using only matches of thickness 1.
{1, 5, 9}
{7, 10}
{8, 9}
Returns: 56
One of the optimal solutions looks as follows (each digit d denotes a single match of thickness d): 1 3 1 3 1 2 3 1 3 1 2 2
Submissions are judged against all 66 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ConstructionFromMatches with a public method int minimumCost(vector<int> cost, vector<int> top, vector<int> bottom) · 66 test cases · 2 s / 256 MB per case