CPP   26
get brief step limit
Guest on 20th September 2023 12:16:07 AM


  1. // ? --  PROBLEM: UVa Online Judge, 529, Addition Chains
  2. // TLE, IDDFS, Iterative Deepen DFS Search
  3.  
  4. #include <iostream>
  5. #include <vector>
  6.  
  7. #include <cstdlib>
  8. #include <climits>
  9. #include <cmath>
  10.  
  11. using namespace std;
  12.  
  13.  
  14.  
  15.  
  16. int  acute_count[10000];
  17.  
  18.  
  19.  
  20.  
  21. int  get_brief_step_limit(int number);
  22. void find_addition_chain_ids(vector<int> &, int);
  23. void find_addition_chain(vector<int> &, vector<int> &, int, int);
  24.  
  25.  
  26.  
  27.  
  28.  
  29. int
  30. main()
  31. {
  32.     int num = 0;
  33.  
  34.     while (cin >> num)
  35.     {
  36.         if (num == 0)
  37.         {
  38.             break;
  39.         }
  40.  
  41.  
  42.         vector<int> result;
  43.         find_addition_chain_ids(result, num);
  44.  
  45.         for (int i = 0; i < result.size(); ++i)
  46.         {
  47.             if (i > 0)
  48.             {
  49.                 cout << ' ';
  50.             }
  51.  
  52.             cout << result[i];
  53.         }
  54.  
  55.         cout << endl;
  56.     }
  57.  
  58.     return EXIT_SUCCESS;
  59. }
  60.  
  61.  
  62.  
  63.  
  64.  
  65. int
  66. get_brief_step_limit(int num)
  67. {
  68.     if (num == 1)
  69.     {
  70.         return 1;
  71.     }
  72.     else
  73.     {
  74.         if (num & 0x1)
  75.         {
  76.             return get_brief_step_limit(num >> 1) + 2;
  77.         }
  78.         else
  79.         {
  80.             return get_brief_step_limit(num >> 1) + 1;
  81.         }
  82.     }
  83. }
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90. void
  91. find_addition_chain_ids(vector<int> &result, int target)
  92. {
  93.     int limit = get_brief_step_limit(target);
  94.  
  95.     for (int i = 1; i <= limit; ++i)
  96.     {
  97.         vector<int> S;
  98.         find_addition_chain(result, S, target, i);
  99.  
  100.         if (result.size() != 0)
  101.         {
  102.             return;
  103.         }
  104.     }
  105. }
  106.  
  107.  
  108.  
  109. void
  110. find_addition_chain(vector<int> &result,
  111.                     vector<int> &S,
  112.                     int target,
  113.                     int limit)
  114. {
  115.     if (S.size() >= limit)
  116.     {
  117.         return;
  118.     }
  119.  
  120.     if (S.size() == 0)
  121.     {
  122.         S.push_back(1);
  123.  
  124.         if (target == 1)
  125.         {
  126.             result = S;
  127.             return;
  128.         }
  129.         else
  130.         {
  131.             find_addition_chain(result, S, target, limit);
  132.         }
  133.     }
  134.     else
  135.     {
  136.         for (int i = 0; i < S.size(); ++i)
  137.         {
  138.             for (int j = 0; j < S.size(); ++j)
  139.             {
  140.                 int next_num = S[i] + S[j];
  141.  
  142.                 if (next_num == target)
  143.                 {
  144.                     result = S;
  145.                     result.push_back(next_num);
  146.                     return;
  147.                 }
  148.                 else if (next_num > target)
  149.                 {
  150.                     continue;
  151.                 }
  152.                 else
  153.                 {
  154.                     S.push_back(next_num);
  155.  
  156.                     int promissing_max =
  157.                         ((INT_MAX >> (limit - S.size())) > next_num)?
  158.                             (next_num << (limit - S.size())):
  159.                             (INT_MAX);
  160.  
  161.                     if (promissing_max >= target)
  162.                     {
  163.                         find_addition_chain(result, S, target, limit);
  164.                     }
  165.  
  166.                     S.pop_back();
  167.                 }
  168.             }
  169.         }
  170.     }
  171. }
  172.  
  173.  
  174.  
  175.  
  176.  
  177. // -- eof --------
Raw Paste

Login or Register to edit or fork this paste. It's free.