Stock Allocation
Limits: 4 sec., 1024 MiB
There are \(n\) types of product offerings in a store. All products are stored in a warehouse, and there are \(c_i\) products of type \(i\) currently in the warehouse (for each \(i\) between 1 and \(n\), inclusive).
Each of the \(n\) offering types is described by exactly \(p\) attributes. Each of the attributes can be described by a set (possibly empty) of integer values between 1 and \(q\), inclusive.
There are also \(m\) orders placed at the store. To fulfill the \(j\)-th order you must provide a set of products that fulfill the following three requirements:
Quantity. There must be exactly \(a_j\) products in the order.
Maximum single-type. There must be at most \(f_j\) products of the same type in the order. If \(f_j\) is 0, there is no limit.
Product attribute. For each attribute \(k\) (between 1 and \(p\), inclusive) you are given a list of attribute values \(r_{j,k}\). Each list indicates that each order product must have at least one of the attribute values from the given list for the corresponding attribute. An empty list indicates that there’s no restriction on the corresponding attribute. For example, consider the following attribute requirements: \(r_{1,1} = [3], r_{1,2} = [2, 4, 7], r_{1,3} = []\). They mean that only products that contain value 3 at the first attribute, and at least one of the values 2, 4, or 7 at the second attribute can be included in the order.
Your task is to fulfill a set of orders in such a way that the total number of served warehouse products is maximized.
Input
The first line contains three integers \(n\), \(p\), and \(q\) – the number of product types, the number of product attributes, and the maximum attribute value, respectively.
The next \(n\) blocks describe product types. The first line of each block contains a single integer \(c_i\) – the number of products of \(i\)-th type currently available at the warehouse. A block then contains \(p\) lines, describing attribute values of the \(i\)-th product type. The first integer of each line is \(l_{i, k}\) – the number of attribute values of the \(i\)-th product type, followed by \(l_{i, k}\) distinct space-separated integers \(b_{i,k,t}\) describing attribute values.
The next line contains a single integer \(m\) – the number of orders placed.
The next \(m\) blocks describe orders. Each block starts with two integers \(a_j\) and \(f_j\) – the number of ordered products and the maximum allowed number of products of the same type, respectively. This is followed by \(p\) lines describing attribute requirements of the \(j\)-th order. The first integer of each line is \(w_{j,k}\) – the number of attribute requirement values for the \(k\)-th attribute, followed by \(w_{j,k}\) distinct space-separated integers describing requirement list \(r_{j,k}\).
Output
In \(m\) lines print product
allocations for each order. Each allocation is described by \(n\) space-separated non-negative integers.
The \(j\)-th integer of the \(i\)-th line describes how many products of
type \(j\) are added to the \(i\)-th order. If the order is not
fulfilled, print \(n\) integers
0.
Constraints
\(1 \le n \le 2000\),
\(1 \le p, q \le 25\),
\(1 \le m \le 400\),
\(0 \le c_i \le 1000\),
\(1 \le b_{i, k, t}, r_{j, k, t} \le q\),
\(1 \le a_j \le 5000\),
\(0 \le f_j \le 100\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 2 5 1 5 1 2 3 4 5 5 1 2 3 4 5 2 3 1 2 3 3 2 3 4 8 3 1 3 5 3 2 4 5 3 3 2 3 1 3 5 3 1 4 5 3 1 3 1 2 5 3 1 2 4 5 0 3 2 3 5 3 3 4 5 | 1 0 2 0 0 0 0 2 3 |
Notes
The sample test case contains 3 product types, each represented by 2 attributes with the following values:
| Product type | Attribute 1 values | Attribute 2 values | Inventory |
|---|---|---|---|
| 1 | \([1, 2, 3, 4, 5]\) | \([1, 2, 3, 4, 5]\) | 1 |
| 2 | \([1, 2, 3]\) | \([2, 3, 4]\) | 2 |
| 3 | \([1, 3, 5]\) | \([2, 4, 5]\) | 8 |
There is one product of type 1, two products of type 2, and eight products of type 3.
There are also 3 product orders represented by the following requirements:
| Order | Quantity requirement | Maximum single-type requirement | Attribute 1 requirement | Attribute 2 requirement |
|---|---|---|---|---|
| 1 | 3 | 2 | \([1, 3, 5]\) | \([1, 4, 5]\) |
| 2 | 3 | 1 | \([1, 2, 5]\) | \([1, 2, 4]\) |
| 3 | 5 | 0 | \([2, 3, 5]\) | \([3, 4, 5]\) |
The first order is fulfilled by a single product of type 1 and two products of type 3. Note that both products types are compatible with the first order requirements.
The third order is fulfilled by two products of type 2 and three products of type 3. Note that the third order has no limit on the number of products of the same type used.
The remaining three products are all of type 3, and cannot be allocated to the second order as the order requires at most one product of each type.
In such product allocation, a total of 8 products are used out of 11 products available. Note that a better product allocation exists for the given sample.
Scoring
Your score for a test case is \[\left\lfloor \frac{allocated}{total} \cdot 10^7 \right\rfloor.\] Here \(allocated\) is the number of products among all fulfilled orders, and \(total\) is the total number of products in the warehouse. Finally, your overall score is the sum of your scores over all test cases.
Submissions
The execution time limit is 4 seconds per test case and the memory limit is 1024 mebibytes.
The code size limit is 64 kibibytes.
The compilation time limit is 1 minute.
There are 50 provisional test cases. Your submissions will be evaluated on the provisional set during the submission phase.
You can submit your code once per 10 minutes and you will get feedback with your normalized score for each of the provisional tests.
There will be 500 test cases in the final testing after the submission phase is over. The final results will be announced within two weeks.
Quick start
Check the sample solution which simply iterates over all products and allocates them to appropriate orders. The source code is available for some of the contest programming languages:
Tests
All test cases including provisional and final sets are generated by the generator. Please, check the generator source code and feel free to use it for local testing.
In order to generate tests, compile the generator source code using a GCC compiler and run the executable with a single command line integer parameter, which represents the seed of the generator. Parameter 0 will generate the sample test case provided above.
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|