Advenam_Tacet

Two rectangles

Feb 6th, 2015
55
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×