AvoidingProduct
SRM 399 · 2008-04-24 · by andrewzta
Problem Statement
You are given a set A of integers and a positive integer n. You must find positive integers x, y and z such that their product is as close to n as possible (minimize |n - x * y * z|), and none of them belongs to A. If there are several such triples, find the one with the smallest x. If there are still several such triples, minimize y. If there is still a tie, minimize z.
You are given the elements of A as a
Constraints
- a will contain between 0 and 50 elements, inclusive.
- Each element of a will be between 1 and 1000, inclusive.
- All elements of a will be distinct.
- n will be between 1 and 1000, inclusive.
{2,4}
4
Returns: {1, 1, 3 }
You can get 3=1*1*3 and 5=1*1*5. 3 is better.
{1}
10
Returns: {2, 2, 2 }
{1,2}
10
Returns: {3, 3, 3 }
{1,3}
12
Returns: {2, 2, 2 }
{1,3}
13
Returns: {2, 2, 4 }
Submissions are judged against all 287 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AvoidingProduct with a public method vector<int> getTriple(vector<int> a, int n) · 287 test cases · 2 s / 256 MB per case