PrimeSums
TCO08 Qual 1 · 2008-01-21 · by misof
Problem Statement
The
Given two bags A and B, we say that A is a sub-bag of B if A can be obtained by erasing zero or more elements from B.
The weight of a bag is the sum of its elements.
Examples:
The bags (1,2,1,3,1) and (3,1,1,1,2) are the same, but different from the bag (1,2,3,3).
Bags (1,2) and (3,1,1) are sub-bags of the bag (1,2,1,3,1), but bag (1,2,2) is not.
The weight of the bag (1,2,1,3,1) is 1+2+1+3+1=8.
Write a method that will compute how many sub-bags of bag have a prime weight.
Notes
- A prime number is a positive integer with exactly two positive integer divisors.
- Zero (0) and one (1) are not prime numbers.
Constraints
- bag will contain between 1 and 50 elements, inclusive.
- Each element in bag will be between 0 and 10,000, inclusive.
{1,1,2,7}
Returns: 5
This bag has 12 different sub-bags: (1,1,2,7), (1,2,7), (2,7), (1,1,7), (1,7), (7), (1,1,2), (1,2), (2), (1,1), (1), and (). Out of these 12, 5 have prime weights: (1,1,2,7) has weight 11, (7) has weight 7, (1,2) has weight 3, and both (2) and (1,1) have weight 2.
{1,1,1,1,1,1,1,1,1,1}
Returns: 4
This bag has eleven different sub-bags. Out of them four have prime weights (2, 3, 5, and 7).
{4,6,8,10,12,14}
Returns: 0
The empty sub-bag has weight zero, and any other sub-bag has an even weight greater than 2.
{1,2,4,8,16,32,64,128}
Returns: 54
{1234,5678,9012,3456,7890,2345,6789,123,4567,8901}
Returns: 97
Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrimeSums with a public method long long getCount(vector<int> bag) · 96 test cases · 2 s / 256 MB per case