Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <numeric>
- #include <limits>
- #include <stdexcept>
- #include <CGAL/QP_models.h>
- #include <CGAL/QP_functions.h>
- #include <CGAL/Gmpz.h>
- typedef CGAL::Gmpz IT;
- typedef CGAL::Gmpz ET;
- typedef CGAL::Quadratic_program<IT> Program;
- typedef CGAL::Quadratic_program_solution<ET> Solution;
- struct Cell
- {
- long X;
- long Y;
- long Z;
- };
- typedef std::vector<Cell> VC;
- typedef std::vector<IT> VI;
- typedef std::vector<VI> VII;
- void testcase()
- {
- int h, t; std::cin >> h >> t;
- VC healthy(h);
- VC tumor(t);
- for (int i = 0; i < h; ++i) {
- std::cin >> healthy[i].X >> healthy[i].Y >> healthy[i].Z;
- }
- for (int i = 0; i < t; ++i) {
- std::cin >> tumor[i].X >> tumor[i].Y >> tumor[i].Z;
- }
- VII f_h_X(h, VI(31, 1));
- VII f_h_Y(h, VI(31, 1));
- VII f_h_Z(h, VI(31, 1));
- VII f_t_X(t, VI(31, 1));
- VII f_t_Y(t, VI(31, 1));
- VII f_t_Z(t, VI(31, 1));
- // fill table
- for (size_t i = 0; i < h; i++)
- {
- for (size_t d = 1; d <= 30; d++)
- {
- f_h_X[i][d] = f_h_X[i][d-1] * healthy[i].X;
- f_h_Y[i][d] = f_h_Y[i][d-1] * healthy[i].Y;
- f_h_Z[i][d] = f_h_Z[i][d-1] * healthy[i].Z;
- }
- }
- for (size_t i = 0; i < t; i++)
- {
- for (size_t d = 1; d <= 30; d++)
- {
- f_t_X[i][d] = f_t_X[i][d-1] * tumor[i].X;
- f_t_Y[i][d] = f_t_Y[i][d-1] * tumor[i].Y;
- f_t_Z[i][d] = f_t_Z[i][d-1] * tumor[i].Z;
- }
- }
- Program lp(CGAL::SMALLER, false, 0, false, 0);
- CGAL::Quadratic_program_options options;
- options.set_pricing_strategy(CGAL::QP_BLAND);
- // exp search
- int lower_bound = 0;
- int upper_bound = 0;
- for (size_t d = 0; d <= 30; ++d)
- {
- // healthy cells:
- for (int i = 0; i < h; ++i) {
- //lp.set_a(0, i, -1);
- lp.set_b(i, -1);
- }
- // tumor cells:
- for (int i = 0; i < t; ++i) {
- //lp.set_a(0, i+h, 1);
- lp.set_b(i+h, -1);
- }
- int cur_col = 0;
- for (int x = 0; x <= d; ++x)
- {
- const int max_y = d-x;
- for (int y = 0; y <= max_y; ++y)
- {
- const int max_z = d - x - y;
- for (int z = 0; z <= max_z; z++)
- {
- ++cur_col;
- // coeff a^x*b^y*c^z:
- for (int i = 0; i < h; ++i) {
- lp.set_a(cur_col, i, f_h_X[i][x]*f_h_Y[i][y]*f_h_Z[i][z]);
- }
- for (int i = 0; i < t; ++i) {
- lp.set_a(cur_col, i+h, -f_t_X[i][x]*f_t_Y[i][y]*f_t_Z[i][z]);
- }
- }
- }
- }
- auto s = CGAL::solve_linear_program(lp, ET(), options);
- if(!s.is_infeasible())
- {
- std::cout << d << std::endl;
- return;
- }
- }
- std::cout << "Impossible!" << std::endl;
- }
- int main(int argc, char const *argv[]) {
- std::ios_base::sync_with_stdio(false);
- int N; std::cin >> N;
- for (int i = 0; i < N; ++i) {
- testcase();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement