INTCOMB - Combination Of Integers
You will be given n positive integers a1, a2 ... an. We say that a non-negative integer combination of these numbers is of the form a1*b1 + a2*b2 + ... + an*bn where each of b1, b2 ... bn is a non-negative integer. You are to determine how many positive integers cannot be expressed as a non-negative integer combination of a1, a2 ... an.
Input
The first line contains a single integer denoting the number of test cases (about 30). Each test case consists of a single line. The first integer on the line is n, between 1 and 30, which indicates the number of integers a1, a2 ... an. Then n integers follow each between 1 and 100, 000. The i'th such integer is ai. All integers on this line are separated by a space.
Output
For each test case you are to output a single line. If there are only a finite number of positive integers that cannot be expressed as a non-negative integer combination of a1, a2 ... an, then you are to output this number. Otherwise, simply output the text "Infinite" (without quotes).
Constraints
1 <= n <= 30
1 <= ai <= 100000
Example
Input: 3 2 2 4 2 4 5 3 11 12 13 Output: Infinite 6 30
Explanation
Sample Test 2:
You cannot express 1, 2, 3, 6, 7 and 11 using only the integers 4 and 5.
Added by: | Kunal Jain |
Date: | 2011-02-07 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | CodeCraft 11 |