A Coin Problem (Online Version)

View as PDF

Submit solution

Points: 15
Time limit: 2.0s
Memory limit: 32M

Problem type

Credit for the problem idea goes to Plasmatic.

Angie is going shopping!

She has N different types of coins in her pocket, with the i^{th} type of coin being worth d_i dollars, and she's going to V stores. From the j^{th} store, she wants to buy c_j dollars worth of stuff from store j, but store j only accepts the first l_j types of coins in her pocket!

Can you help her figure out the minimum number of coins to pay for each transaction in exact change?

Note that because she is rich for the purpose of this problem, Angie has an infinite number of each type of coin.


1 \le l_j \le N \le 2 \times 10^3

1 \le V \le 10^5

1 \le d_i, c_j \le 10^4

Input Specification

The first line of input consists of N and V, separated by a space.

The next line contains N space separated integers containing the values d_i (d_1, d_2, d_3, ... d_N).

The next V lines of input each contain the space separated encoded integers c_j' and l_j'.

To decode c_j' and l_j', consider the answer to the previous query. If the previous query did not exist, or had an answer of -1, then no decoding needs to be done. Otherwise, XOR both numbers with the answer to the previous query.

Output Specification

There are V lines of output, with each line containing the minimum amount of coins needed to satisfy the payment in the j^{th} transaction.

If the j^{th} transaction cannot be satisfied however, print -1.

Sample Input 1

6 3
7 10 15 2 3 24
107 3
4 12
26 0

Sample Output 1



Transaction 1: 6 coins with $15, 1 coin with $10, and 1 coin worth $7.

Transaction 2: 1 coin worth $10, and 1 coin worth $2.

Transaction 3: 1 coin worth $10, and 2 coins worth $7.

All that needs to be noted here is that for the third transaction, even though she has a coin worth $24 the third store won't accept it.

Sample Input 2

4 3
11 15 3 1
6 2
15 1
7 4

Sample Output 2



Transactions 1 and 2: Not possible.

Transaction 3: 2 coins worth $3, and 1 coin worth $1.

Note that the first transaction cannot be completed without the third type of coin and the second one cannot be completed without the second type of coin.]


  • 18
    Plasmatic  commented on May 4, 2019, 11:57 p.m. edited

    shouldn't this be called A Coin Problem (Online Version) ?

    Edit: Fixed as of Oct 20, 2019