Connection Status:
Competition Arena > CoinsQuery

CoinsQuery

SRM 713 · 2017-02-20 · by cgy4ever

SRM 713 · 2017-02-20 · by cgy4ever · Advanced Math
Class Name: CoinsQuery
Return Type: long[]
Method Name: query
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Fox Ciel has n types of coins. The types are numbered from 0 to n-1. Each coin of type i has weight w[i] and value v[i]. Coins of the same type are considered identical. Coins of different types are always distinct, even if they have the same weight and the same value. Ciel has an unlimited supply of coins of each type.

You are given the int[]s w and v. You are also given a int[] query. Each element of query is a query you have to process.

For each integer S in query, solve the following problem: Ciel wants to find a sequence of coins with total weight exactly equal to S. If there is no such sequence, the answer is {-1, -1}. If there are such sequences, Ciel wants to maximize the total value of the coins in the list. Let X be the maximum total value that can be achieved. Let Y be the number of sequences of coins with total weight S and total value X. Then, the answer is {X, Y modulo (10^9 + 7)}.

Note that the order of coins in the sequence matters. For example, the sequences {coin1, coin1, coin2} and {coin1, coin2, coin1} differ.

Return the concatenation of answers to all the queries. (Thus, the number of elements in the return value should be twice the number of elements in query.)

Constraints

  • n will be between 1 and 100, inclusive.
  • w will contain exactly n elements.
  • v will contain exactly n elements.
  • Each element in w will be between 1 and 100, inclusive.
  • Each element in v will be between 1 and 1,000,000,000, inclusive.
  • query will contain between 1 and 100 elements, inclusive.
  • Each element in query will be between 1 and 1,000,000,000, inclusive.
Examples
0)
{2,3,5}
{20,30,50}
{1,2,3,4,5,6}
Returns: {-1, -1, 20, 1, 30, 1, 40, 1, 50, 3, 60, 2 }

For each coin in this test case we have value = 10*weight. Hence, any sequence of coins with total weight S has the same total value 10*S. Thus, all sequences that achieve the given total weight also achieve the maximum possible value. There is no way to get a total weight of 1. Ways to get a total weight of 2: {coin0}. Ways to get a total weight of 3: {coin1}. Ways to get a total weight of 4: {coin0, coin0}. Ways to get a total weight of 5: {coin0, coin1}, {coin1, coin0}, {coin2}. Ways to get a total weight of 6: {coin0, coin0, coin0}, {coin1, coin1}.

1)
{7,4,3,8}
{10,20,17,13}
{10,100,1000,100000}
Returns: {54, 3, 564, 33, 5664, 333, 566664, 33333 }
2)
{2,3,5}
{1,10,100}
{1,2,3,4,5,6}
Returns: {-1, -1, 1, 1, 10, 1, 2, 1, 100, 1, 20, 1 }

This time the values are different enough, so for each query there is only 1 optimal solution.

3)
{1,1}
{1,1}
{10,20,30,40,50}
Returns: {10, 1024, 20, 1048576, 30, 73741817, 40, 511620083, 50, 898961331 }

Don't forget to mod.

4)
{1}
{1000000000}
{1,1000000000}
Returns: {1000000000, 1, 1000000000000000000, 1 }

Return the exact value of X, not the remainder it gives modulo 10^9 + 7. Only the value Y should be computed modulo 10^9 + 7.

Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CoinsQuery with a public method vector<long long> query(vector<int> w, vector<int> v, vector<int> query) · 107 test cases · 2 s / 256 MB per case

Submitting as anonymous