Avoid9
TCO17 Pittsburgh · 2017-03-31 · by boba5551
Problem Statement
A set of integers is called 9-free if it has the following properties:
- It contains at least three elements.
- For every three distinct elements x, y, z in the set, the value (x+y+z) is not divisible by 9.
You are given a
Constraints
- A will contain between 3 and 200 integers, inclusive.
- Each element of A will be between 0 and 1,000,000, inclusive.
- All the elements of A will be distinct.
{6, 9, 5, 3}
Returns: 3
The whole four-element set A is not 9-free, because (6+9+3) is divisible by 9. The subset {9, 5, 3} is 9-free, because (9+5+3) is not divisible by 9. Thus, the size of the largest 9-free subset of A is 3.
{6, 9, 18, 3, 15, 12}
Returns: 4
Subset {6, 3, 15, 12} is 9-free. It is easy to verify that no larger subset of A is 9-free.
{1, 10, 7, 19, 16, 28, 9, 46, 0, 37}
Returns: 8
{3, 12, 30, 6, 21, 4, 15, 9}
Returns: 5
{600308, 404694, 939932, 748673, 891293, 706905, 978182, 625631, 708003, 977632, 828206, 972547,
184606, 929681, 237869, 610370, 559760, 939323, 272684, 162248, 168143, 753163, 302535, 153367,
568583, 750868, 735416, 97724, 620300, 509987, 129310, 993312, 323413, 676205, 629534, 894380, 1791,
499727, 751959, 456281}
Returns: 23
{993320, 112864, 892808, 821699, 227492, 901628, 467512, 142654, 810125}
Returns: 9
The whole set A can also be the desired 9-free subset.
Submissions are judged against all 53 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Avoid9 with a public method int maxSizeOf9Free(vector<int> A) · 53 test cases · 2 s / 256 MB per case