Artifact daf9553b63d995fb1bdfae81fdd9096a7ade68f0

• File SRM/399/1A.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
using namespace std;


struct AvoidingProduct
{
	vector<int> getTriple(vector<int> a, int n)
	{
		int best = 1000000000;
		vector<int> ans(3);

		set<int> as(a.begin(), a.end());
		for(int x=1;; ++x) if( !as.count(x) ) {
			for(int y=x;; ++y) if( !as.count(y) ) {
				for(int z=y;; ++z) if( !as.count(z) ) {
					int m = x*y*z;
					if( abs(m-n) < best ) {
						best = abs(m-n);
						ans[0] = x;
						ans[1] = y;
						ans[2] = z;
					}

					if( x*y*z>n ) break;
				}
				if( x*y*y>n ) break;
			}
			if( x*x*x>n ) break;
		}
			
		return ans;
	}
};