Problem F
Treasure Packing
A dragon has terrorized the region for decades, breathing fire and stealing treasures. A hero has decided steal back the treasures and return them to the community. However, they drastically underestimated the size of the dragon’s hoard, bringing only a single $25$ liter bag, only strong enough to hold $20$ kg, to carry out the treasures. The hero has decided to try to return as much value as possible. The dragon has $12$ different types of items of different values, masses, and volumes: crowns, figurines, jeweled goblets, gold helms, etc., where each item of the same type has the same mass and volume. For example, all goblets have the same mass and volume. Write a program helping the hero determine what items they should put in the bag so as to maximize value accounting for the constraints on the bag.
Input
The input is JSON keyed by treasure category name, such as “goblet”. Every category has a unique name composed of at most $100$ lowercase ASCII characters. There are exactly twelve treasure categories. Each corresponding value is a list with one integer $q$ ($1 \leq q \leq 10\, 000$) and three integers $v$ ($0 < v \leq 10^6$), $m$ ($0 < m \leq 20 \cdot 10^6$), and $l$ ($0 < l \leq 25\cdot 10^6$), where $q$ is the maximum number of treasures of this category that can be looted, $v$ is the value of one item, $m$ is the mass (in mg) of one item, and $l$ the volume (in $\mu $liters) of one item. (There are one million mg per kg and $\mu $liters per liter.)
Please see the sample input for an example of how the JSON is formatted.
Output
Print a JSON with the same keys as the input, but with single nonegative integer values giving the numbers of items of that category added to the bag in your solution.
Scoring
Producing an algorithm that always generates optimal solutions is very difficult, so your solution only needs to be “good enough”. We will compare your output to a baseline heuristic provided by the NSA, and to a best effort to compute the true optimum. You must beat the NSA heuristic to receive points; after that, the better your solution, the higher your score. Specifically, your score on this problem is your average of the per-test-case score
\[ 100 \cdot \operatorname {clamp}\left(\frac{\textrm{your value} - \textrm{baseline value}}{\textrm{best value} - \textrm{baseline value}}, 0, 1\right). \]| Sample Input 1 | Sample Output 1 |
|---|---|
{
"circlet": [
19,
113005,
146800,
514247
],
"coppercoin": [
887,
6171,
12593,
18081
],
"crown": [
13,
726439,
1079353,
1212213
],
"dagger": [
21,
279513,
558367,
522344
],
"figurine": [
18,
26272,
1488281,
2295986
],
"goblet": [
22,
300053,
698590,
986387
],
"goldcoin": [
129,
14426,
82176,
27597
],
"helm": [
3,
974983,
2470209,
882803
],
"jewelry": [
23,
272450,
171396,
262226
],
"plate": [
22,
98881,
246257,
363420
],
"silvercoin": [
288,
12587,
53480,
28654
],
"torc": [
17,
244957,
388222,
500000
]
}
|
{
"circlet": 2,
"coppercoin": 8,
"crown": 13,
"dagger": 0,
"figurine": 0,
"goblet": 0,
"goldcoin": 0,
"helm": 0,
"jewelry": 23,
"plate": 0,
"silvercoin": 1,
"torc": 4
}
|
| Sample Input 2 | Sample Output 2 |
|---|---|
{
"circlet": [
14,
298021,
152342,
569655
],
"coppercoin": [
885,
4586,
28242,
37721
],
"crown": [
35,
558194,
700000,
1384817
],
"dagger": [
1,
221618,
568063,
91185
],
"figurine": [
15,
495235,
1543411,
333761
],
"goblet": [
10,
164562,
545496,
752137
],
"goldcoin": [
100,
3342,
113852,
41618
],
"helm": [
27,
959377,
2179441,
1841497
],
"jewelry": [
21,
434910,
65575,
358743
],
"plate": [
11,
88742,
52026,
617095
],
"silvercoin": [
77,
7876,
64410,
24295
],
"torc": [
37,
380210,
328752,
333342
]
}
|
{
"circlet": 7,
"coppercoin": 0,
"crown": 0,
"dagger": 1,
"figurine": 3,
"goblet": 0,
"goldcoin": 0,
"helm": 0,
"jewelry": 21,
"plate": 0,
"silvercoin": 2,
"torc": 37
}
|
| Sample Input 3 | Sample Output 3 |
|---|---|
{
"circlet": [
4,
443418,
209428,
423652
],
"coppercoin": [
295,
8660,
7719,
14065
],
"crown": [
15,
598207,
491881,
813066
],
"dagger": [
2,
153956,
283756,
184358
],
"figurine": [
15,
820843,
1000000,
2428478
],
"goblet": [
13,
799643,
209002,
441602
],
"goldcoin": [
127,
50863,
68660,
25903
],
"helm": [
14,
917543,
1907181,
2542347
],
"jewelry": [
30,
559571,
157362,
249831
],
"plate": [
19,
321098,
356640,
709027
],
"silvercoin": [
317,
12186,
21466,
17865
],
"torc": [
19,
290912,
186313,
209472
]
}
|
{
"circlet": 4,
"coppercoin": 40,
"crown": 4,
"dagger": 0,
"figurine": 0,
"goblet": 13,
"goldcoin": 86,
"helm": 0,
"jewelry": 30,
"plate": 0,
"silvercoin": 0,
"torc": 19
}
|
| Sample Input 4 | Sample Output 4 |
|---|---|
{
"circlet": [
29,
247959,
341955,
419367
],
"coppercoin": [
312,
6018,
4278,
29843
],
"crown": [
17,
926260,
861367,
1597635
],
"dagger": [
13,
297169,
509838,
235145
],
"figurine": [
17,
295296,
1000000,
2730724
],
"goblet": [
10,
290042,
41932,
401162
],
"goldcoin": [
100,
33893,
50000,
20000
],
"helm": [
10,
822082,
1012394,
2593164
],
"jewelry": [
31,
540091,
131618,
115981
],
"plate": [
16,
166014,
257198,
417937
],
"silvercoin": [
144,
15803,
35054,
13718
],
"torc": [
29,
207777,
233392,
1104699
]
}
|
{
"circlet": 3,
"coppercoin": 5,
"crown": 8,
"dagger": 5,
"figurine": 0,
"goblet": 10,
"goldcoin": 100,
"helm": 0,
"jewelry": 31,
"plate": 0,
"silvercoin": 0,
"torc": 0
}
|
