Advenam_Tacet

Two rectangles

Feb 6th, 2015
49
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <iterator>
  4. #include <vector>
  5. #include <cmath>
  6.  
  7. typedef std::tuple<unsigned long long, unsigned long long> rectangle;
  8. typedef std::tuple<rectangle, rectangle> answer;
  9.  
  10. rectangle best_permiter(const unsigned long long p) {
  11.     unsigned long long best = 2*(p + 1);
  12.     rectangle answer(1, p);
  13.     for(unsigned long long i = 2; i*i <= p; ++i) {
  14.         if(p % i == 0 && 2*(p/i+i) < best) {
  15.             answer = rectangle(p/i, i);
  16.             best = 2 * (p/i + i);
  17.         }
  18.     }
  19.     return answer;
  20. }
  21.  
  22. inline unsigned long long permiter(const rectangle& x) {
  23.     return 2 * (std::get<0>(x) + std::get<1>(x));
  24. }
  25.  
  26. std::vector<rectangle> make_cache() {
  27.     constexpr size_t cache_size = 1300U*1000U;
  28.     std::vector<rectangle> cache(cache_size + 1);
  29.     cache.emplace_back(0,0);
  30.     for(size_t i = 1; i < cache.size(); ++i) {
  31.         cache[i] = rectangle(1, i);
  32.     }
  33.     for(unsigned i = 2; i < cache_size; ++i) {
  34.         for(size_t j = i; j < cache.size(); j += i) {
  35.             if(permiter(cache[j]) > 2 * (i + j/i)) {
  36.                 cache[j] = rectangle(i, j/i);
  37.             }
  38.         }
  39.     }
  40.     return cache;          
  41. }
  42.  
  43. answer solve(const unsigned long long begin, const unsigned long long end,
  44.              const unsigned long long p) {
  45.     if(p == 2) {
  46.         return answer(rectangle(1,1), rectangle(1,1));
  47.     }
  48.     if(p < 100000) {
  49.            answer result;
  50.            unsigned long long square = sqrt(p), best = p*8;
  51.            for(unsigned long long i = 1; i <= square; ++i) {
  52.              for(unsigned long long j = 1; j * i < p; ++j) {
  53.                auto temp = best_permiter(p - i*j);
  54.                if(permiter(temp) + 2*(i+j) < best) {
  55.                  result = answer(temp, rectangle(i, j));
  56.                  best = permiter(temp) + 2 * (i + j);
  57.                 }
  58.               }
  59.             }
  60.            return result;
  61.           }
  62.     const static std::vector<rectangle> cache = make_cache();
  63.     answer result;
  64.     unsigned long long best = 0;
  65.     bool first = true;
  66.     unsigned long long square = sqrt(p);
  67.     if(p < 100) {
  68.         square = p-1;
  69.     }
  70.     for(unsigned long long i = begin; i <= end && i < square; ++i) {
  71.         const auto first_side = square - i;
  72.         const auto second_side = p / first_side;
  73.         if(second_side == 0 || first_side * second_side == p) {
  74.             continue;
  75.         }
  76.         auto first_rectangle = rectangle(first_side, second_side);
  77.         auto rest = p - first_side * second_side;
  78.         if(rest > cache.size()) {
  79.             continue;
  80.         }
  81.         auto second_rectangle = rest < cache.size() ? cache[rest] :
  82.                                         best_permiter(rest);
  83.         auto sum_of_sides = std::get<0>(second_rectangle) +
  84.                             std::get<1>(second_rectangle) +
  85.                             std::get<0>(first_rectangle)  +
  86.                             std::get<1>(first_rectangle);                      
  87.         if(first == true || sum_of_sides < best) {
  88.             result = answer(first_rectangle, second_rectangle);
  89.             best = sum_of_sides;
  90.             first = false;
  91.         }
  92.     }
  93.     return result;
  94. }
  95.  
  96. int main() {
  97.     std::ios_base::sync_with_stdio(false);
  98.     std::cin.tie(NULL);
  99.     unsigned t;
  100.     std::cin >> t;
  101.     for(unsigned counter = 0; counter < t; ++counter) {
  102.         unsigned long long p;
  103.         std::cin >> p;
  104.         unsigned long long begin = 0, end = 1000000;
  105.         auto result = solve(begin, end, p);
  106.         auto sum_of_permiter = permiter(std::get<0>(result)) +
  107.                               permiter(std::get<1>(result));
  108.         std::cout << sum_of_permiter << '\n';
  109.         std::cout << std::get<0>(std::get<0>(result)) << ' '
  110.                   << std::get<1>(std::get<0>(result)) << '\n'
  111.                   << std::get<0>(std::get<1>(result)) << ' '
  112.                   << std::get<1>(std::get<1>(result)) << '\n';
  113.     }
  114. }
RAW Paste Data