fork(7) download
copy 
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <lpsolve/lp_lib.h>
  5. using namespace std;
  6.  
  7. // the 21 candidates for the answer, encoded into bits
  8. const int CC = 21;
  9. const int candidates[CC] = { 57, 89, 99, 101, 105, 113, 135, 139, 141, 147, 149, 153, 163, 165, 169, 177, 195, 197, 201, 209, 225 };
  10.  
  11. void initialize_LP(lprec** LP) {
  12.     *LP = make_lp(0,8);             // 0 rows so far, 8 variables
  13.     set_verbose(*LP, IMPORTANT);    // shut up when solving
  14.     double coef[2]={-1.,+1.};       // add the constraints of the form w[i]+1 <= w[i+1]
  15.     int vars[2];
  16.     for (int i=1; i<=7; ++i) {      
  17.         vars[0]=i; vars[1]=i+1; 
  18.         add_constraintex(*LP,2,coef,vars,GE,1); 
  19.     }
  20.     coef[0]=1; vars[0]=8;           // add the objective function
  21.     set_obj_fnex(*LP,1,coef,vars); 
  22. }
  23.  
  24. void add_answer(lprec** LP, int lighter_set) {
  25.     // add the constraint that some set of bags is lighter than its complement
  26.     int heavier_set = 255 ^ lighter_set;
  27.     double coef[9];
  28.     for (int i=0; i<8; ++i) if (heavier_set & 1<<i) coef[i+1] = +1.;
  29.     for (int i=0; i<8; ++i) if (lighter_set & 1<<i) coef[i+1] = -1.;
  30.     add_constraint(*LP,coef,GE,1);
  31. }
  32.  
  33. void add_question(lprec** LP, int left_set) {
  34.     // add the constraint that some set of bags exactly as heavy as its complement
  35.     int right_set = 255 ^ left_set;
  36.     double coef[9];
  37.     for (int i=0; i<8; ++i) if (right_set & 1<<i) coef[i+1] = +1.;
  38.     for (int i=0; i<8; ++i) if (left_set  & 1<<i) coef[i+1] = -1.;
  39.     add_constraint(*LP,coef,EQ,0);
  40. }
  41.  
  42. bool solvable(int limit, const vector<int> lighter_sets) {
  43.     // <lighter_sets> contains the lighter set for each measurement we already did
  44.     // <solve> returns true iff we can guarantee a win within <limit> additional questions
  45.     vector<int> alive;
  46.     for (int c=0; c<CC; ++c) {
  47.         lprec *LP;
  48.         initialize_LP(&LP);
  49.         for (int ls:lighter_sets) add_answer(&LP,ls);
  50.         add_question(&LP,candidates[c]);
  51.         if (!solve(LP)) alive.push_back( candidates[c] ); // solve() returns 0 iff a solution was found
  52.         delete_lp(LP);
  53.     }
  54.     if (int(alive.size()) <= 1) return true;
  55.     // if (limit == 0) return 1234567; // multiple options && no questions left
  56.     if (int(alive.size()) > (1<<(limit+1))-1 ) return false; // too many candidates, too few questions
  57.  
  58.     for (int q:alive) {
  59.         vector<int> first  = lighter_sets; first.push_back(q); 
  60.         vector<int> second = lighter_sets; second.push_back(255^q); 
  61.         if (solvable(limit-1,first) && solvable(limit-1,second)) return true;
  62.     }
  63.     return false;
  64. }
  65.  
  66. int main() {
  67.     for (int q=1; ; ++q) {
  68.         printf("%d questions: ",q); fflush(stdout);
  69.         bool s = solvable(q,vector<int>());
  70.         printf("%ssolvable\n",s?"":"not ");
  71.         if (s) break;
  72.     }
  73. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:4:28: fatal error: lpsolve/lp_lib.h: No such file or directory
 #include <lpsolve/lp_lib.h>
                            ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/xnivHM
language:
C++14 (gcc 8.3)
created:
12 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!