PowersOfTwo
SRM 612 · 2013-12-22 · by ltaravilse
SRM 612 · 2013-12-22 · by ltaravilse · Greedy, Math
Problem Statement
Problem Statement
Fox Ciel likes powers of two.
She has a bag with some positive powers of two.
Note that some powers may occur multiple times in the bag.
You are given a long[] powers.
Each element of powers is one of the numbers in Ciel's bag.
Ciel likes each non-negative integer that can be written as the sum of some numbers from her bag.
For example, suppose that her bag contains the numbers 2, 4, 4, and 64. In this case, Ciel likes 10 (because 10=2+4+4), 64 (because 64=64), and also 0 (the sum of no numbers). She does not like 1, and she does not like 12 (note that 12=4+4+4 is not valid, as she only has two 4s; 12=4+4+2+2 is also not valid, as she only has one 2).
Return the number of integers Ciel likes.
Ciel likes each non-negative integer that can be written as the sum of some numbers from her bag.
For example, suppose that her bag contains the numbers 2, 4, 4, and 64. In this case, Ciel likes 10 (because 10=2+4+4), 64 (because 64=64), and also 0 (the sum of no numbers). She does not like 1, and she does not like 12 (note that 12=4+4+4 is not valid, as she only has two 4s; 12=4+4+2+2 is also not valid, as she only has one 2).
Return the number of integers Ciel likes.
Constraints
- powers will contain between 1 and 50 elements, inclusive.
- Each element of powers is a power of two between 1 and 2^50, inclusive.
Examples
0)
{1,2}
Returns: 4
Fox Ciel likes 0, 1, 2 and 3.
1)
{1,1,1,1}
Returns: 5
Fox Ciel likes 0, 1, 2, 3 and 4.
2)
{1,2,2,2,4,4,16}
Returns: 32
3)
{1,32,1,16,32}
Returns: 18
4)
{1048576,1073741824,549755813888,70368744177664,4398046511104,262144,1048576,2097152,8796093022208,
1048576,1048576,35184372088832,2097152,256,256,256,262144,1048576,1048576,70368744177664,262144,1048576}
Returns: 18432
Submissions are judged against all 62 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PowersOfTwo with a public method long long count(vector<long long> powers) · 62 test cases · 2 s / 256 MB per case