fork(1) download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <set>
  4. #include <vector>
  5.  
  6. //backtracking algorithm was taken from here:
  7. //http://e...content-available-to-author-only...a.org/wiki/Backtracking
  8.  
  9. std::vector<int> digitsFromInt(int num)
  10. {
  11.     if(num == 0)
  12.     {
  13.         return std::vector<int>(1, 0);
  14.     }
  15.  
  16.     std::vector<int> ret;
  17.  
  18.     while(num != 0)
  19.     {
  20.         ret.push_back(num % 10);
  21.         num /= 10;
  22.     }
  23.     std::reverse(ret.begin(), ret.end());
  24.  
  25.     return ret;
  26. }
  27.  
  28. template <typename T>
  29. class Backtrack
  30. {
  31. protected:
  32.     virtual T root(T) = 0;
  33.     virtual bool reject(T, T) = 0;
  34.     virtual bool accept(T, T) = 0;
  35.     virtual T first(T, T) = 0;
  36.     virtual T next(T, T) = 0;
  37.     virtual void output(T, T) = 0;
  38.  
  39. private:
  40.     T P;
  41.  
  42.     void bt(T c)
  43.     {
  44.         if(reject(P, c))
  45.         {
  46.             return;
  47.         }
  48.         if(accept(P, c))
  49.         {
  50.             output(P, c);
  51.         }
  52.         T s = first(P, c);
  53.         while(s.size() != 0)
  54.         {
  55.             bt(s);
  56.             s = next(P, s);
  57.         }
  58.     }
  59.  
  60. public:
  61.     void backtrack(T p)
  62.     {
  63.         bt(root(this->P = p));
  64.     }
  65. };
  66.  
  67. class Crypt : public Backtrack< std::vector<int> >
  68. {
  69. private:
  70.     int count;
  71.  
  72. public:
  73.     Crypt() : Backtrack< std::vector<int> >()
  74.     {
  75.         count = 0;
  76.     }
  77.  
  78.     std::vector<int> root(std::vector<int> P)
  79.     {
  80.         //return the empty set
  81.         return std::vector<int>(0);
  82.     }
  83.  
  84.     bool reject(std::vector<int> P, std::vector<int> c)
  85.     {
  86.         //we can only reject combinations that are larger than 5
  87.         //combinations less than 5 still need to be expanded
  88.         return (c.size() > 5);
  89.     }
  90.  
  91.     bool accept(std::vector<int> P, std::vector<int> c)
  92.     {
  93.         /** The following cryptarithm is a multiplication problem that can be solved by
  94.          *  substituting digits from a specified set of N digits into the positions marked with *.
  95.          *  If the set of prime digits {2,3,5,7} is selected, the cryptarithm is called a PRIME CRYPTARITHM.
  96.          *  
  97.          *    * * *
  98.          *  x   * *
  99.          *  -------
  100.          *    * * *         <-- partial product 1
  101.          *  * * *           <-- partial product 2
  102.          *  -------
  103.          *  * * * *
  104.          *  
  105.          *  Digits can appear only in places marked by `*'. Of course, leading zeroes are not allowed.
  106.          *  Note that the 'partial products' are as taught in USA schools. The first partial product is
  107.          *  the product of the final digit of the second number and the top number. The second partial
  108.          *  product is the product of the first digit of the second number and the top number.
  109.          */
  110.  
  111.         //the partial candidate c must have at least 5 elements to even be able to perform the multiplication
  112.         if(c.size() < 5)
  113.         {
  114.             return false;
  115.         }
  116.  
  117.         //the partial candidate has to result in a multiplication that consists of only digits from parameter P
  118.         int num1 = P[c[0]] * 100 + P[c[1]] * 10 + P[c[2]];
  119.         int num2 = P[c[3]] * 10 + P[c[4]];
  120.         int part1 = P[c[4]] * num1;
  121.         int part2 = P[c[3]] * num1;
  122.         int ans = num1 * num2;
  123.         // std::cerr << num1 << " * " << num2 << " = " << ans << std::endl;
  124.         // std::cerr << part1 << "   " << part2 << std::endl;
  125.  
  126.         //convert all numbers to digit lists
  127.         std::vector<int> dPart1 = digitsFromInt(part1);
  128.         std::vector<int> dPart2 = digitsFromInt(part2);
  129.         std::vector<int> dAns = digitsFromInt(ans);
  130.  
  131.         //part1 and part2 must be three digits
  132.         //ans must be four digits
  133.         if(dPart1.size() != 3 || dPart2.size() != 3 || dAns.size() != 4)
  134.         {
  135.             return false;
  136.         }
  137.  
  138.         //combine all the digit lists into one
  139.         std::vector<int> digits(3 + 3 + 4);
  140.         auto it = std::copy(dPart1.begin(), dPart1.end(), digits.begin());
  141.         it = std::copy(dPart2.begin(), dPart2.end(), it);
  142.         std::copy(dAns.begin(), dAns.end(), it);
  143.  
  144.         //then check to see that the digits in the set are all members of P
  145.         for(int digit : digits)
  146.         {
  147.             // std::cerr << digit << ", ";
  148.             if(std::find(P.begin(), P.end(), digit) == P.end())
  149.             {
  150.                 //a digit was found that was not in P
  151.                 return false;
  152.             }
  153.         }
  154.         // std::cerr << std::endl;
  155.  
  156.         //all digits were in P, so the solution is acceptable
  157.         return true;
  158.     }
  159.  
  160.     std::vector<int> first(std::vector<int> P, std::vector<int> c)
  161.     {
  162.         if(c.size() < 5)
  163.         {
  164.             c.push_back(0);
  165.             return c;
  166.         }
  167.  
  168.         return std::vector<int>(0);
  169.     }
  170.  
  171.     std::vector<int> next(std::vector<int> P, std::vector<int> s)
  172.     {
  173.         if(s.size() != 5)
  174.         {
  175.             return std::vector<int>(0);
  176.         }
  177.  
  178.         bool carry = false;
  179.         int max = P.size();
  180.         for(auto it = s.rbegin(); it != s.rend(); it++)
  181.         {
  182.             (*it) += 1;
  183.             carry = (*it >= max);
  184.             (*it) %= max;
  185.             if(!carry)
  186.             {
  187.                 break;
  188.             }
  189.         }
  190.  
  191.         if(carry)
  192.         {
  193.             return std::vector<int>(0);
  194.         }
  195.  
  196.         return s;
  197.     }
  198.  
  199.     void output(std::vector<int> P, std::vector<int> c)
  200.     {
  201.         count++;
  202.     }
  203.  
  204.     int getCount()
  205.     {
  206.         return count;
  207.     }
  208. };
  209.  
  210.  
  211. int main(int argc, char* argv[])
  212. {
  213.     try
  214.     {
  215.         int data_size;
  216.         //continuously request input for size of the set, until size of set is zero or less
  217.         while(std::cin >> data_size && data_size > 0)
  218.         {
  219.             //request inputs for members of the set
  220.             std::vector<int> numbers(data_size, 0);
  221.             for (int i = 0; i < data_size; i++)
  222.             {
  223.                 std::cin >> numbers[i];
  224.             }
  225.  
  226.             //since the numbers can be given out of order they must be sorted
  227.             std::sort(numbers.begin(), numbers.end());
  228.             // for(int num : numbers)
  229.             // {
  230.                 // std::cerr << num << ", ";
  231.             // }
  232.             // std::cerr << std::endl;
  233.  
  234.             Crypt crypt;
  235.             crypt.backtrack(numbers);
  236.  
  237.             std::cout << crypt.getCount() << std::endl;
  238.         }
  239.     }
  240.     catch(...)
  241.     {
  242.         std::cerr << "there was a problem" << std::endl;
  243.     }
  244.  
  245.     return 0;
  246. }
  247.  
Success #stdin #stdout 0.04s 3440KB
comments (?)
stdin
copy 
7
4 1 2 5 6 7 3
5
2 3 4 6 8
0
stdout
copy 
384
1
https://ideone.com/qenDWZ
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!