NOIP '18 P2 - Currency System

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

In a coin system (n,a), there are coins of n different values. The i-th coin in the system has value a_i, and you may assume each kind of coin has unlimited supply. Now you are given a coin system (n,a), and you need to find an equivalent coin system (m,b) such that m is minimized (i.e. the coin system having the minimum number of denominations). Here, "equivalent" means for any nonnegative value x, x can be expressed in one currency system if and only if it can be expressed in the other currency system.

Input Specification

The first line contains an integer T denoting the number of test cases.

For each test case, the first line contains an integer n. In the following line, there are n space-separated integers a_i denoting the values of the coins in the coin system.

Output Specification

The output contains T lines. For each test case, output a line containing an integer denoting the minimum m such that (m,b) is equivalent to coin system (n,a).

Sample Input 1

3 19 10 6
11 29 13 19 17

Sample Output 1



In the first test case, the currency system (2,[3,10]) is equivalent to the given currency system, and it is easy to see there are no equivalent currency systems with m < 2. As a result, the answer is 2.

In the second test case, it can be shown that there does not exist any equivalent currency system with m < n, so the answer is 5.

Additional Samples

Additional samples can be found here.


Test Case n a_i
1~3 =2 \le 1000
4-6 =3
7-8 =4
9-10 =5
11~13 \le 13 \le 16
14~16 \le 25 \le 40
17~20 \le 100 \le 25\,000

For all test cases, 1 \le T \le 20, n, a_i \ge 1.


There are no comments at the moment.