SHARE
TWEET

Untitled

a guest Nov 22nd, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <limits>
  6. #include <stdexcept>
  7.  
  8. #include <CGAL/QP_models.h>
  9. #include <CGAL/QP_functions.h>
  10. #include <CGAL/Gmpz.h>
  11.  
  12. typedef CGAL::Gmpz IT;
  13. typedef CGAL::Gmpz ET;
  14. typedef CGAL::Quadratic_program<IT> Program;
  15. typedef CGAL::Quadratic_program_solution<ET> Solution;
  16.  
  17. struct Cell
  18. {
  19.     long X;
  20.     long Y;
  21.     long Z;
  22. };
  23.  
  24. typedef std::vector<Cell> VC;
  25. typedef std::vector<IT> VI;
  26. typedef std::vector<VI> VII;
  27.  
  28. void testcase()
  29. {
  30.     int h, t; std::cin >> h >> t;
  31.     VC healthy(h);
  32.     VC tumor(t);
  33.  
  34.     for (int i = 0; i < h; ++i) {
  35.         std::cin >> healthy[i].X >> healthy[i].Y >> healthy[i].Z;
  36.     }
  37.  
  38.     for (int i = 0; i < t; ++i) {
  39.         std::cin >> tumor[i].X >> tumor[i].Y >> tumor[i].Z;
  40.     }
  41.  
  42.     VII f_h_X(h, VI(31, 1));
  43.     VII f_h_Y(h, VI(31, 1));
  44.     VII f_h_Z(h, VI(31, 1));
  45.     VII f_t_X(t, VI(31, 1));
  46.     VII f_t_Y(t, VI(31, 1));
  47.     VII f_t_Z(t, VI(31, 1));
  48.  
  49.     // fill table
  50.     for (size_t i = 0; i < h; i++)
  51.     {
  52.         for (size_t d = 1; d <= 30; d++)
  53.         {
  54.             f_h_X[i][d] = f_h_X[i][d-1] * healthy[i].X;
  55.             f_h_Y[i][d] = f_h_Y[i][d-1] * healthy[i].Y;
  56.             f_h_Z[i][d] = f_h_Z[i][d-1] * healthy[i].Z;
  57.         }
  58.        
  59.     }
  60.     for (size_t i = 0; i < t; i++)
  61.     {
  62.         for (size_t d = 1; d <= 30; d++)
  63.         {
  64.             f_t_X[i][d] = f_t_X[i][d-1] * tumor[i].X;
  65.             f_t_Y[i][d] = f_t_Y[i][d-1] * tumor[i].Y;
  66.             f_t_Z[i][d] = f_t_Z[i][d-1] * tumor[i].Z;
  67.         }
  68.        
  69.     }
  70.    
  71.     Program lp(CGAL::SMALLER, false, 0, false, 0);
  72.     CGAL::Quadratic_program_options options;
  73.     options.set_pricing_strategy(CGAL::QP_BLAND);
  74.  
  75.     // exp search
  76.  
  77.     int lower_bound = 0;
  78.     int upper_bound = 0;
  79.  
  80.     for (size_t d = 0; d <= 30; ++d)
  81.     {
  82.  
  83.         // healthy cells:
  84.         for (int i = 0; i < h; ++i) {
  85.             //lp.set_a(0, i, -1);
  86.             lp.set_b(i, -1);
  87.         }
  88.  
  89.         // tumor cells:
  90.         for (int i = 0; i < t; ++i) {
  91.             //lp.set_a(0, i+h, 1);
  92.             lp.set_b(i+h, -1);
  93.         }
  94.  
  95.         int cur_col = 0;
  96.        
  97.         for (int x = 0; x <= d; ++x)
  98.         {
  99.             const int max_y = d-x;
  100.             for (int y = 0; y <= max_y; ++y)
  101.             {
  102.                 const int max_z = d - x - y;
  103.                 for (int z = 0; z <= max_z; z++)
  104.                 {
  105.                     ++cur_col;
  106.  
  107.                     // coeff a^x*b^y*c^z:
  108.                     for (int i = 0; i < h; ++i) {
  109.                         lp.set_a(cur_col, i, f_h_X[i][x]*f_h_Y[i][y]*f_h_Z[i][z]);
  110.                     }
  111.                     for (int i = 0; i < t; ++i) {
  112.                         lp.set_a(cur_col, i+h, -f_t_X[i][x]*f_t_Y[i][y]*f_t_Z[i][z]);
  113.                     }
  114.                 }
  115.             }
  116.         }
  117.  
  118.         auto s = CGAL::solve_linear_program(lp, ET(), options);
  119.         if(!s.is_infeasible())
  120.         {
  121.             std::cout << d << std::endl;
  122.             return;
  123.         }
  124.     }
  125.  
  126.     std::cout << "Impossible!" << std::endl;
  127. }
  128.  
  129. int main(int argc, char const *argv[]) {
  130.     std::ios_base::sync_with_stdio(false);
  131.     int N; std::cin >> N;
  132.     for (int i = 0; i < N; ++i) {
  133.         testcase();
  134.     }
  135. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top