fork download
copy 
  1. #pragma warning(disable:4018)
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cfloat>
  7. #include <map>
  8. #include <utility>
  9. #include <set>
  10. #include <iostream>
  11. #include <memory>
  12. #include <string>
  13. #include <vector>
  14. #include <algorithm>
  15. #include <functional>
  16. #include <sstream>
  17. #include <complex>
  18. #include <stack>
  19. #include <queue>
  20. using namespace std;
  21. static const double EPS = 1e-5;
  22. typedef long long ll;
  23.  
  24. int nn;
  25. vector<int> aa;
  26.  
  27. int minSearch(){
  28.  
  29. 	for(int i=0 ; i<aa.size() ; i++){
  30. 		if(aa[i]!=i+1) return i+1;
  31. 	}
  32. 	return aa.size()+1;
  33. }
  34.  
  35. int calc(int a, int b, int c){
  36. 	return abs((ll)nn - (ll)a*(ll)b*(ll)c);
  37. }
  38.  
  39. bool isMember(int n){
  40. 	for(int i=0 ; i<aa.size() ; i++){
  41. 		if(aa[i]==n) return true;
  42. 		if(aa[i]>n) break;
  43. 	}
  44. 	return false;
  45. }
  46.  
  47. bool isPlus(int a, int b, int c){
  48. 	return (nn - (ll)a*(ll)b*(ll)c) < 0;
  49. }
  50.  
  51. class AvoidingProduct {
  52. public:
  53.   vector <int> getTriple(vector <int> a, int n) {
  54. 	  nn = n;
  55.  
  56. 	  sort(a.begin(), a.end());      
  57. 	  aa = a;
  58.  
  59. 	  int mina = minSearch();
  60. 	  //cout << mina << endl;
  61.  
  62. 	  int ans = calc(mina, mina, mina);
  63. 	  int tmp;
  64. 	  int ii,jj,kk;
  65. 	  ii = jj = kk = mina;
  66.  
  67. 	  for(int i=mina ; i<=2*n ; i++){
  68. 		  if(isMember(i)) continue;
  69.  
  70. 		  if(isPlus(i,i,i) && calc(i,i,i)>ans) break;
  71.  
  72. 		  for(int j=i ; j<=2*n ; j++){
  73. 			  if(isMember(j)) continue;
  74.  
  75. 			  if(isPlus(i,j,j) && calc(i,j,j)>ans) break;
  76.  
  77. 			  for(int k=j ; k<=2*n ; k++){
  78. 				  if(isMember(k)) continue;
  79.  
  80. 				  tmp = calc(i,j,k); 
  81.  
  82. 				  if(isPlus(i,j,k) && tmp>ans) break;
  83.  
  84. 				  if(ans > tmp){
  85. 					  ans = tmp;
  86. 					  ii=i;
  87. 					  jj=j;
  88. 					  kk=k;
  89. 				  }
  90. 			  }
  91. 		  }
  92. 	  }
  93.  
  94. 	  vector<int> ret;
  95. 	  ret.clear();
  96. 	  ret.push_back(ii);
  97. 	  ret.push_back(jj);
  98. 	  ret.push_back(kk);
  99. 	  return ret;
  100.   }
  101.  
  102.  
  103. // BEGIN CUT HERE
  104. 	public:
  105. 	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
  106. 	private:
  107. 	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
  108. 	void verify_case(int Case, const vector <int> &Expected, const vector <int> &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } }
  109. 	void test_case_0() { int Arr0[] = {2,4}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 4; int Arr2[] = {1, 1, 3 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(0, Arg2, getTriple(Arg0, Arg1)); }
  110. 	void test_case_1() { int Arr0[] = {1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 10; int Arr2[] = {2, 2, 2 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(1, Arg2, getTriple(Arg0, Arg1)); }
  111. 	void test_case_2() { int Arr0[] = {1,2}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 10; int Arr2[] = {3, 3, 3 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(2, Arg2, getTriple(Arg0, Arg1)); }
  112. 	void test_case_3() { int Arr0[] = {1,3}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 12; int Arr2[] = {2, 2, 2 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(3, Arg2, getTriple(Arg0, Arg1)); }
  113. 	void test_case_4() { int Arr0[] = {1,3}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 13; int Arr2[] = {2, 2, 4 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(4, Arg2, getTriple(Arg0, Arg1)); }
  114. 	void test_case_5() { int Arr0[] = {1,15}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 90; int Arr2[] = {2, 5, 9 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(5, Arg2, getTriple(Arg0, Arg1)); }
  115.  
  116. // END CUT HERE
  117.  
  118. };
  119.  
  120. // BEGIN CUT HERE
  121. int main() {
  122.   AvoidingProduct ___test;
  123.   ___test.run_test(-1);
  124. }
  125. // END CUT HERE
  126.  
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1: warning: ignoring #pragma warning 
prog.cpp: In function ‘int minSearch()’:
prog.cpp:29: warning: comparison between signed and unsigned integer expressions
prog.cpp: In function ‘bool isMember(int)’:
prog.cpp:40: warning: comparison between signed and unsigned integer expressions
stdout
copy 
Standard output is empty
https://ideone.com/2xtiu
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!